基于队列式分支限界法的一般解空间算法求解给定布线区域内的最短路径问题。
5星
- 浏览量: 0
- 大小:None
- 文件类型：None
简介：
本研究提出了一种基于队列式分支限界法的新颖算法，用于探索和解决限定布线区域内寻找最短路径的问题。该方法通过优化搜索过程中的解空间效率地找到了最优解。
设计一个使用队列式分支限界法搜索一般解空间的函数，并将其应用于布线问题。
印刷电路板将布线区域划分成n×m个方格阵列（如图a所示）。精确的电路布线问题是确定连接方格a的中点到方格b 的中点的最短路径方案。在进行线路布置时，只能沿直线或直角方向铺设电线，具体布局方式参考图b。为了避免不同线路间的交叉干扰，已经完成布线的部分会被标记为封锁区域。
给定一个具体的电路板布线问题实例，请编写程序计算出从起始方格到目标方格的最短布线路径长度以及该路径所经过的所有坐标位置。如果不存在可行解，则输出No Solution!。
输入数据由文件input.txt提供，其中第一行包括三个正整数n、m和k，分别代表电路板区域划分成多少行与列及封锁标记的数量；接下来的k 行中每一行包含两个数字表示被封锁方格所在的行列位置。最后两行为起始点(p, q) 和终点(r, s) 的坐标信息。
程序应将结果输出至文件output.txt，首先给出最短布线路径长度值，在此之后每行记录一个通过的方格坐标（直到到达目标节点）；当不存在解时则显示No Solution!。
示例输入：
8 8 3
3 4
5 6
2 17
输出结果：
11
从起点至终点最短路径长度为：11。
各步经过的坐标依次是（此处仅展示一部分）: (1,7)
全部评论 (0)
还没有任何评论哟~
