一道算法期末应用题及解答
1．印刷电路板布线区划分成为n m 个方格，确定连接方格a 到方格b 的最短布线方案。
在布线时，只能沿直线或者直角布线，为避免交叉，已经布线的方格做了封锁标记，其他线路不允许穿过被封锁的方格，某待布线电路板如下图所示，灰色方格为已封锁位置：
(1)描述求解该问题的算法策略和解题步骤；
（2）针对方格中数据，求得从方格a 到方格b 的最短布线方案，并说明求解的全过程。
解答：
(1)、每个结点最多有4 个扩展方向，搜索的方向比较盲目，因此求最短布线比较适合采用FIFO 分枝搜索策略。
步骤：
- 开始时，唯一的活结点是a，进入活结点队；
- 从活结点队中取出队头成为E- 结点；
3、对E- 结点寻找可行位置入队；
4、重复该过程直到b 结点或者队为空；
5、如果b 结点终止则倒推输出路径，否则输出失败
(2)、活结点的扩展轮次如下图中编号所示：
布线路径如图中箭头所示。
原文地址：https://blog.csdn.net/m0_54748666/article/details/143888210
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！