6.6 布线问题

6.6 布线问题算法设计思想：采用分支限界法求解。首先将问题转化为一颗解空间树：树根为线头，树高为线头到线尾的格数，每个节点有4个孩子，代表下一格可以朝4个方向。这样，布线问题就是搜索从树根到代表线尾节点的一条最短路径。分支限界法的本质是对解空间树的BFS（广度优先）搜索，即每进一格就将状态入队，而后再依次将出队的每个状态的子状态入队，直到到达所求的状态节点即线尾。该问题的剪枝条件显而易见，即当遇到电路板上的封锁标记时进行剪枝。为了方便剪枝，算法开始进行了预处理，在电路板周围加上了一圈“围墙”（虚拟的封锁标记），使搜索路径时对边界的处理与对封锁标记的处理统一。因为该问题BFS的队列中，并没有明显的优先级，所以该算法采用普通队列式。除了上述三点之外，程序对鲁棒性做了增强，对非法输入和文件错误进行了检测。程序设计代码： /*头文件 布线问题.h*/#ifndef KNAP_H#define KNAP_H#include #include #include using namespace std;class position/位置类public:int row;/行坐标int column;/列坐标bool operator=(const position &b) const/重载运算符=，表示位置相同if(row = b.row & column = b.column)return true;elsereturn false;position& operator=(const position &b)/重载运算符=，位置赋值this-row = b.row;this-column = b.column;return *this;position operator+(const position &b)const/重载运算符+，表示移动一格position temp;temp.row = row + b.row;temp.column = column + b.column;return temp;class Wiring/布线类public:Wiring(char *in, char *out);/构造函数Wiring();/析构函数void Solve();/输出结果到文件protected:bool FindPath();/找出布线方案void PrintPath();/输出结果布线方案void PrintFail();/输出没有路径信息private:int n, m;/电路板行列数int *grid;/电路板格子position start, finish;/起点和终点position *nextstep;/下一步四个方向ofstream fout;/输出结果文件;#endif/*函数实现文件 布线问题.cpp*/#include 布线问题.hWiring:Wiring(char *in, char *out) : fout(out)ifstream fin(in);if( !fin )cerr 文件 in 无法打开! n m;/初始化电路板大小n*mgrid = new int*n+2;for(int i = 0; i = n+1; i+)gridi = new intm+2;if(i = 0 | i = n+1)/加上下围墙for(int j = 0; j = m+1; j+)gridij = 1;elsegridi0 = gridim+1 = 1;/加左右围墙for(int j = 1; j gridij;fin start.row start.column;/初始化起点和终点fin finish.row finish.column;fin.close();nextstep = new position4;nextstep0.row = 0; nextstep0.column = 1;/右nextstep1.row = 1; nextstep1.column = 0;/下nextstep2.row = 0; nextstep2.column = -1;/左nextstep3.row = -1; nextstep3.column = 0;/上if( !fout )cerr 文件 out 无法打开! endl;exit(1);Wiring:Wiring()if(fout)fout.close();for(int i = 0; i = n+1; i+)if(gridi)delete gridi;if(grid)delete grid;void Wiring:Solve()if(FindPath()PrintPath();/输出路径elsePrintFail();/无路径bool Wiring:FindPath()if(start = finish)/如果起点和终点重合return 0;position here, near;/当前位置和相邻的一个位置gridstart.rowstart.column = 2;/开始点步数记为2list Queue;/辅助队列Queue.push_back(start);/初始位置是起点while(1)here = Queue.front();/取队尾位置Queue.pop_front();for(int i = 0; i 0; i-)/找前趋位置gridhere.rowhere.column = -1;/表示在路径上for(int j = 0; j 4; j+)near = here + nextstepj;if(gridnear.rownear.column = i+1)/找到前趋break;here = near;/向前移动for(int i = 1; i = n; i+)int j;for(j = 1; j = m; j+)if(gridij = -1)/表示路径fout *tt;elsefout gridij tt;fout endl;void Wiring:PrintFail()fout No Path! endl;/*主函数文件 test.cpp*/#include