0035算法笔记-布线问题

1、问题描述印刷电路板将布线区域划分成nxm个方格如图a所示。精确的电路 布线问题要求确定连接方格a的中点到方格b的中点的最短布线方案。 在布线时，电路只能沿直线或直角布线，如图b所示。为了避免线路相 交，已布了线的方格做了封锁标记，其它线路不允穿过被封锁的方格。肋沿览戦即Mi fi就一个布线的例子：图中包含障碍。起始点为a，目标点为bo算法思想解此问题的队列式分支限界法从起始位置a开始将它作为第一个扩展结点。与该扩展结点相邻并且可达的方格成为可行结点被加入到活结点队列中，并且将这些方格标记为1,即从起始方格a到这些方格的距离为1。接着，算法从活结点队列中取出队首结点作为下一个扩展结点，并 将与当

2、前扩展结点相邻且未标记过的方格标记为2,并存入活结点队列。 这个过程一直继续到算法搜索到目标方格b或活结点队列为空时为止。 即加入剪枝的广度优先搜索。算法具体代码如下：1、Queue.hcpp view plain copy#includeusing namespace std;3.template class Queuepublic:Queue(int MaxQueueSize=50);Queue()delete queue;boolIsEmpty()constreturn front=rear;bool IsFull()return ( ( (rear+1) %MaxSize=front

3、)?1:0);T Top() const;T Last() const;Queue& Add(const T& x);Queue& AddLeft(const T& x);Queue& Delete(T &x);voidOutput(ostream& out)const;int Length()return (rear-front);private:intfront;intrear;intMaxSize;T *queue;24.25.26.27.28.29.30.31.32.33.34.35.36.37.38.39.40.41.42.43.44.45.46.47.48.49.50.51.52.

4、53.54.55.56.57.58.59.60.61.62.63.64.65.66.67.；templateQueue:Queue(int MaxQueueSize)MaxSize=MaxQueueSize+1;queue=new TMaxSize; front=rear=0;templateT Queue:Top()constif(IsEmpty()coutqueue:no element,no!endl; return 0;else return queue(front+1) % MaxSize;templateT Queue :Last()constif(IsEmpty()coutque

5、ue:no elementendl; return 0;else return queuerear;templateQueue& Queue:Add(const T& x)if(IsFull()coutqueue:no memoryendl;elserear=(rear+1)% MaxSize; queuerear=x;return *this;templateQueue& Queue:AddLeft(const T& x) TOC o 1-5 h z if(IsFull()coutqueue:no memoryendl;elsefront=(front+MaxSize-1)% MaxSize

6、;queue(front+1)% MaxSize=x;return*this;79.templateQueue& Queue :Delete(T & x)if(IsEmpty()coutqueue:no element(delete)endl;elsefront=(front+1) % MaxSize;x=queuefront;return*this;91.92.templatevoid Queue :Output(ostream& out)constfor(int i=rear%MaxSize;i=(front+1)%MaxSize;i-)outqueuei;99.templateostre

7、am& operator (ostream& out,const Queue& x)x.Output(out);return out;2、6d4.cppcpp view plain copy1.布线问题队列式分支限界法求解2.#include stdafx.h3.#includeQueue.h4.#include5.#include6. using namespace std;7.8.9.10.11.12.13.14.15.16.17.18.19.20.21.22.23.24.25.26.27.28.29.30.31.32.33.34.35.36.37.38.39.40.41.42.43.44

8、.45.46.47.48.49.ifstream fin(6d4.txt”)； const int n = 7;const int m = 7;int gridn+2m+2;struct Positionint row;int col;bool FindPath(Position start,Position finish, int& PathLen,Position *&path);int main()int PathLen;Position start,finish,*path;start.row = 3;start.col = 2;finish.row = 4;finish.col =

9、6;cou t布线起点endl;coutstart.col start.rowendl;cou t布线结束点endl;coutfinish.col finish.rowendl;cout布线方格阵列如下(0表示允许布线，1表示不允许布线)：endl;for(int i=1; i=m; i+)for(int j=1; jgridij;coutgridijcoutendl;50.51.52.53.54.55.56.57.58.59.60.61.62.63.64.65.66.67.68.69.70.71.72.73.74.75.76.77.78.79.80.81.82.83.84.85.86.87.

10、88.89.90.91.92.93.FindPath(startfinish,PathLen,path);cou t布线长度为:Pa thLenendl;cou t布线路径如下：endl;for(int i=0; iPathLen; i+)coutpathi.col pathi.rowendl;return 0;bool FindPath(Position start,Position finish, int& PathLen,Position *&path)/计算从起始位置st ar t到目标位置finish的最短布线路径if(start.row = finish.row) & (start

11、.col = finish.col)PathLen = 0;return true;设置方格阵列“围墙”for(int i=0; i= m+1; i+)grid0i=gridn+1i=1; /顶部和底部for(int i=0; i= n+1; i+)gridi0=gridim+1=1; /左翼和右翼/初始化相对位移Position offset4;offset0.row=0;offset0.col=1;/右offset1.row=1;offset1.col=0;/下offset2.row=0;offset2.col=-1;/左offset3.row=-1;94.95.96.97.98.99.1

12、00.101.102.103.104.105.106.107.108.109.110.111.112.113.114.115.116.117.118.119.120.121.122.123.124.125.126.127.128.129.130.131.132.133.134.135.136.137.offset3.col=0;/上int Num0fNbrs=4;/相邻方格数Position here,nbr;here.row=start.row;here.col=start.col;grids tart .rows tar t.col=2; /标记可达方格位置Queue Q;do /标记相邻可达方格for(int i=0; i=0; j-)pat hj=here; /找前驱位置 for(int i=0; iNumOfNbrs; i+) nbr.row=here.row+offseti.row