算法设计与分析中的分支限界法应用在布线问题上

印刷电路板的布线区域被划分为n×m个网格，如图a所示。精确的电路布线问题需要确定从方格a中心点至方格b中心点的最短路径方案。在进行布线过程中，线路仅允许沿直线或直角方向延伸，具体示例如图b所示。为防止线路交叉，已被布线的方格将被设置为封锁状态，其余线路不得穿越这些被封锁的网格区域。

一个布线示例展示于图中，其中存在障碍物。该示例的起点设定为a，而终点则为b。

算法原理：

解决该问题所采用的队列式分支限界法，首先以起始位置a作为初始扩展节点展开处理。与该扩展节点相邻且可抵达的网格被判定为可行节点，并被纳入活结点队列之中，同时对这些网格进行标记，标记值为1，表示从起始网格a到这些网格的距离为1。

随后，算法从活结点队列中取出首项节点作为新的扩展节点，并将与当前扩展节点相邻且尚未标记的网格进行标记，标记值设为2，并将其存入活结点队列。上述操作持续执行，直至找到目标