问题描述印刷电路板将布线区域划分成n×m个方格如图a所示。
精确的电路布线问题要求确定连接方格a的中点到方格b的中点的最短布线方案。
在布线时，电路只能沿直线或直角布线，如图b所示。
为了避免线路相交，已布了线的方格做了封锁标记，其它线路不允穿过被封锁的方格。
一个布线的例子：图中包含障碍。
起始点为a，目标点为b。
算法思想解此问题的队列式分支限界法从起始位置a开始将它作为第一个扩展结点。
与该扩展结点相邻并且可达的方格成为可行结点被加入到活结点队列中，并且将这些方格标记为1，即从起始方格a到这些方格的距离为1。
接着，算法从活结点队列中取出队首结点作为下一个扩展结点，并将与当前扩展结点相邻且未标记过的方格标记为2，并存入活结点队列。
这个过程一直继续到算法搜索到目标方格b或活结点队列为空时为止。
即加入剪枝的广度优先搜索。
算法具体代码如下：1、Queue.h[cpp]view plain copy1.#include<iostream>ing namespace std;3.4.template <class T>5.class Queue6.{7.public:8. Queue(int MaxQueueSize=50);9. ~Queue(){delete [] queue;}10.bool IsEmpty()const{return front==rear;}11.bool IsFull(){return ( ( (rear+1) %MaxSize==front )?1:0);}12. T Top() const;13. T Last() const;14. Queue<T>& Add(const T& x);15. Queue<T>& AddLeft(const T& x);16. Queue<T>& Delete(T &x);17.void Output(ostream& out)const;18.int Length(){return (rear-front);}19.private:20.int front;21.int rear;22.int MaxSize;23. T *queue;24.};25.26.template<class T>27.Queue<T>::Queue(int MaxQueueSize)28.{29. MaxSize=MaxQueueSize+1;30. queue=new T[MaxSize];31. front=rear=0;32.}33.34.template<class T >35.T Queue<T>::Top()const36.{37.if(IsEmpty())38. {39. cout<<"queue:no element,no!"<<endl;40.return 0;41. }42.else return queue[(front+1) % MaxSize];43.}44.45.template<class T>46.T Queue<T> ::Last()const47.{48.if(IsEmpty())49. {50. cout<<"queue:no element"<<endl;51.return 0;52. }53.else return queue[rear];54.}55.56.template<class T>57.Queue<T>& Queue<T>::Add(const T& x)58.{59.if(IsFull())cout<<"queue:no memory"<<endl;60.else61. {62. rear=(rear+1)% MaxSize;63. queue[rear]=x;64. }65.return *this;66.}67.68.template<class T>69.Queue<T>& Queue<T>::AddLeft(const T& x)70.{71.if(IsFull())cout<<"queue:no memory"<<endl;72.else73. {74. front=(front+MaxSize-1)% MaxSize;75. queue[(front+1)% MaxSize]=x;76. }77.return *this;78.}79.80.template<class T>81.Queue<T>& Queue<T> ::Delete(T & x)82.{83.if(IsEmpty())cout<<"queue:no element(delete)"<<endl;84.else85. {86. front=(front+1) % MaxSize;87. x=queue[front];88. }89.return *this;90.}91.92.93.template<class T>94.void Queue <T>::Output(ostream& out)const95.{96.for(int i=rear%MaxSize;i>=(front+1)%MaxSize;i--)97. out<<queue[i];98.}99.100.template<class T>101.ostream& operator << (ostream& out,const Queue<T>& x) 102.{x.Output(out);return out;}2、6d4.cpp[cpp]view plain copy1.//布线问题队列式分支限界法求解2.#include "stdafx.h"3.#include "Queue.h"4.#include <fstream>5.#include <iostream>ing namespace std;7.8.ifstream fin("6d4.txt");9.10.const int n = 7;11.const int m = 7;12.int grid[n+2][m+2];13.14.struct Position15.{16.int row;17.int col;18.};19.20.bool FindPath(Position start,Position finish,int& PathLen,Position *&path);21.22.int main()23.{24.int PathLen;25.26. Position start,finish,*path;27.28. start.row = 3;29. start.col = 2;30.31. finish.row = 4;32. finish.col = 6;33.34. cout<<"布线起点"<<endl;35. cout<<start.col<<" "<<start.row<<endl;36. cout<<"布线结束点"<<endl;37. cout<<finish.col<<" "<<finish.row<<endl;38.39. cout<<"布线方格阵列如下(0表示允许布线，1表示不允许布线)："<<endl;40.for(int i=1; i<=m; i++)41. {42.for(int j=1; j<=n; j++)43. {44. fin>>grid[i][j];45. cout<<grid[i][j]<<" ";46. }47. cout<<endl;48. }49.50. FindPath(start,finish,PathLen,path);51.52. cout<<"布线长度为:"<<PathLen<<endl;53. cout<<"布线路径如下："<<endl;54.for(int i=0; i<PathLen; i++)55. {56. cout<<path[i].col<<" "<<path[i].row<<endl;57. }58.59.return 0;60.}61.62.bool FindPath(Position start,Position finish,int& PathLen,Position *&path)63.{64.//计算从起始位置start到目标位置finish的最短布线路径65.if((start.row == finish.row) && (start.col == finish.col))66. {67. PathLen = 0;68.return true;69. }70.71.//设置方格阵列“围墙”72.for(int i=0; i<= m+1; i++)73. {74. grid[0][i]=grid[n+1][i]=1; //顶部和底部75. }76.for(int i=0; i<= n+1; i++)77. {78. grid[i][0]=grid[i][m+1]=1; //左翼和右翼79. }80.81.//初始化相对位移82. Position offset[4];83.84. offset[0].row=0;85. offset[0].col=1;//右86.87. offset[1].row=1;88. offset[1].col=0;//下89.90. offset[2].row=0;91. offset[2].col=-1;//左92.93. offset[3].row=-1;94. offset[3].col=0;//上95.96.int NumOfNbrs=4;//相邻方格数97. Position here,nbr;98. here.row=start.row;99. here.col=start.col;100.101. grid[start.row][start.col]=2;//标记可达方格位置102. Queue<Position> Q;103.104.do {//标记相邻可达方格105.for(int i=0; i<NumOfNbrs; i++)106. {107. nbr.row=here.row + offset[i].row;108. nbr.col=here.col+offset[i].col;109.110.if(grid[nbr.row][nbr.col]==0)//该方格未被标记111. {112. grid[nbr.row][nbr.col]=grid[here.row][here.col]+1; 113.if((nbr.row==finish.row) && (nbr.col==finish.col)) 114. {115.break; //完成布线116. }117. Q.Add(nbr);118. }119. }120.//是否到达目标位置finish？121.if((nbr.row==finish.row) && (nbr.col==finish.col))122. {123.break;//完成布线124. }125.126.//活结点队列是否非空？127.if(Q.IsEmpty())128. {129.return false;//无解130. }131. Q.Delete(here);//取下一个扩展结点132. }while(true);133.134.//构造最短布线路径135. PathLen=grid[finish.row][finish.col]-2;136. path=new Position[PathLen];//从目标位置finish开始向起始位置回溯137. here=finish;138.for(int j=PathLen-1; j>=0; j--)139. {140. path[j]=here;//找前驱位置141.for(int i=0; i<NumOfNbrs; i++) 142. {143. nbr.row=here.row+offset[i].row; 144. nbr.col=here.col+offset[i].col; 145.if(grid[nbr.row][nbr.col]==j+2) 146. {147.break;148. }149. }150. here=nbr;//向前移动151. }152.return true;153.}程序运行结果如图：。