.6.6 布线问题算法设计思想：采用分支限界法求解。首先将问题转化为一颗解空间树：树根为线头，树高为线头到线尾的格数，每个节点有4个孩子，代表下一格可以朝4个方向。这样，布线问题就是搜索从树根到代表线尾节点的一条最短路径。分支限界法的本质是对解空间树的BFS（广度优先）搜索，即每进一格就将状态入队，而后再依次将出队的每个状态的子状态入队，直到到达所求的状态节点即线尾。该问题的剪枝条件显而易见，即当遇到电路板上的封锁标记时进行剪枝。为了方便剪枝，算法开始进行了预处理，在电路板周围加上了一圈“围墙”（虚拟的封锁标记），使搜索路径时对边界的处理与对封锁标记的处理统一。因为该问题BFS的队列中，并没有明显的优先级，所以该算法采用普通队列式。除了上述三点之外，程序对鲁棒性做了增强，对非法输入和文件错误进行了检测。程序设计代码： /*头文件 布线问题.h*/#ifndef KNAP_H#define KNAP_H#include #include #include using name
