分支限界法 求电路布线的最短路径.doc

#include#include#includeusing namespace std;/import the grid data;ifstream fin(map.txt);/这个map是7行7列，请以这个为例子来理解这个程序typedef struct Positionint row;int col; Posi;/find the shortest path for the gridbool FindPath(Posi start,Posi finish,int & PathLen,int *&grid,Posi *& path,int n,int m)/if the start position is the finish positionif(start.row = finish.row) & (start.col = finish.col)PathLen = 0;return true;Position offset4;offset0.row = -1;/upoffset0.col = 0;offset1.row = 1;/downoffset1.col = 0;offset2.row = 0;/leftoffset2.col = -1;offset3.row = 0;/rightoffset3.col = 1;Posi here,nbr;here.row = start.row;here.col = start.col;int NumOfNbrs = 4;/ajacent position;gridstart.rowstart.col = 2;/init the start positions length with value 2,queue Q;dofor(int firdex = 0;firdex =0;firdex-)pathfirdex = here;for(int secdex = 0;secdex NumOfNbrs;secdex+)nbr.row = here.row + offsetsecdex.row;nbr.col = here.col + offsetsecdex.col;if(gridnbr.rownbr.col = firdex+2)/It is the nbrs grid that why the gridnbr.rownbr.col can give index of firdex+2break;here =nbr;/move to the previous nodereturn true;/allocate memory for the gridvoid InitGrid(int *&grid,int n,int m)grid = new int*n+2;for(int firdex = 0;firdex n+2;firdex+)gridfirdex = new intm+2;/set the boundfor(int index = 0;index m+2;index+)/top an bottomgrid0index = gridn+1index =1;for(int index = 0;index n+2;index+)gridindex0 = gridindexm+1 = 1;for(int firdex = 1;firdex n+1;firdex+)for(int secdex = 1;secdex gridfirdexsecdex;/destroy the resource for the gridvoid Destroy(int * &grid,int n,int m)if(grid != NULL)for(int firdex = 0;firdex n+2;firdex+)delete gridfirdex;gridfirdex = NULL;delete grid;grid = NULL;int main(void)int m = 0,n = 0;Posi start,finish;int PathLength = 0;Posi * path = NULL;int * grid = NULL;coutPlease input the m and n of the grid:nm;coutPlease input the start position:endl;coutstart.row;coutstart.col;coutPlease input the finish position:endl;coutfinish.row;coutfinish.col;InitGrid(grid,n,m);coutthe map resource:endl;for(int firdex = 1;firdex n+1;firdex+)for(int secdex = 1;secdex m+1;secdex+)coutgridfirdexsecdex ;coutendl;coutendl;FindPath(start,finish,PathLength,grid,path,n,m);coutThe shortest path of wiring is :PathLengthendl;coutThe path if follow:endl;for(int index = 0;index PathLength;index+)cout(pathindex.row,pathindex.col);if(index PathLength-1)cout;coutendl;