0039算法笔记——【分支限界法】电路板排列问题

五大常用算法之五：分支限界法五大常用算法之五：分支限界法分支限界法一、基本描述类似于回溯法，也是一种在问题的解空间树T上搜索问题解的算法。

但在一般情况下，分支限界法与回溯法的求解目标不同。

回溯法的求解目标是找出T中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。

（1）分支搜索算法所谓“分支”就是采用广度优先的策略，依次搜索E-结点的所有分支，也就是所有相邻结点，抛弃不满足约束条件的结点，其余结点加入活结点表。

然后从表中选择一个结点作为下一个E-结点，继续搜索。

选择下一个E-结点的方式不同，则会有几种不同的分支搜索方式。

1）FIFO搜索2）LIFO搜索3）优先队列式搜索（2）分支限界搜索算法二、分支限界法的一般过程由于求解目标不同，导致分支限界法与回溯法在解空间树T上的搜索方式也不相同。

回溯法以深度优先的方式搜索解空间树T，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树T。

分支限界法的搜索策略是：在扩展结点处，先生成其所有的儿子结点（分支），然后再从当前的活结点表中选择下一个扩展对点。

为了有效地选择下一扩展结点，以加速搜索的进程，在每一活结点处，计算一个函数值（限界），并根据这些已计算出的函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地找出一个最优解。

分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。

问题的解空间树是表示问题解空间的一棵有序树，常见的有子集树和排列树。

在搜索问题的解空间树时，分支限界法与回溯法对当前扩展结点所使用的扩展方式不同。

在分支限界法中，每一个活结点只有一次机会成为扩展结点。

活结点一旦成为扩展结点，就一次性产生其所有儿子结点。

在这些儿子结点中，那些导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被子加入活结点表中。

分支限界法是一种常用的解决组合优化问题的算法，它通过不断扩展当前解空间的分支节点，并通过限界函数对分支节点进行剪枝，最终找到最优解。

在本文中，我们将使用C++语言实现分支限界法来解决电路板排列问题。

电路板排列问题是一个经典的组合优化问题，其目标是将给定数量的电路板排列在一个给定大小的板子上，使得每块电路板之间不发生重叠。

假设每块电路板都是矩形形状，那么问题就是确定每块电路板在板子上的位置和角度，使得它们不重叠，并尽可能地节省空间。

现在让我们通过C++语言来实现分支限界法来解决电路板排列问题。

1. 设计电路板类我们首先需要设计一个电路板类，用来表示每块电路板的属性，包括长度、宽度、位置和角度等。

以下是电路板类的定义：```cppclass CircuitBoard {public:int length; // 电路板长度int width; // 电路板宽度int x; // 电路板左上角x坐标int y; // 电路板左上角y坐标float angle; // 电路板旋转角度};```2. 实现分支限界法接下来，我们需要实现分支限界法来解决电路板排列问题。

我们将通过递归的方式来搜索最优解，具体步骤如下：- 初始化一个优先队列，用来存储待扩展的分支节点。

- 将初始节点加入优先队列中。

- 当优先队列不为空时，循环执行以下步骤：- 从优先队列中取出一个节点。

- 判断该节点是否为叶子节点，如果是则更新最优解。

- 否则，对该节点进行扩展，计算每个子节点的限界值，并将其加入优先队列中。

- 继续循环直到找到最优解或者遍历完所有节点。

3. 编写C++代码现在让我们编写C++代码来实现上述算法。

```cpp#include <iostream>#include <vector>#include <queue>using namespace std;class CircuitBoard {public:int length; // 电路板长度int width; // 电路板宽度int x; // 电路板左上角x坐标int y; // 电路板左上角y坐标float angle; // 电路板旋转角度};bool isOverlap(const CircuitBoard board1, const CircuitBoard board2) {// 判断两块电路板是否重叠// ...}int boundingFunction(const vector<CircuitBoard>currentSolution, const vector<CircuitBoard> rem本人ningBoards) {// 计算限界值// ...}void branchAndBound(const vector<CircuitBoard> initialBoards, int boardCount, int boardWidth, int boardLength) {priority_queue<vector<CircuitBoard>,vector<vector<CircuitBoard>>,pare> pq;vector<CircuitBoard> currentSolution;vector<CircuitBoard> rem本人ningBoards = initialBoards;int bestSolution = INT_MAX;pq.push(initialBoards);while (!pq.empty()) {vector<CircuitBoard> currentNode = pq.top();pq.pop();if (currentNode.empty()) {bestSolution = min(bestSolution,calculateSolution(currentSolution));} else {vector<CircuitBoard> leftNode =expandNode(currentNode, true);vector<CircuitBoard> rightNode =expandNode(currentNode, false);int boundLeft = boundingFunction(leftNode, rem本人ningBoards);int boundRight = boundingFunction(rightNode, rem本人ningBoards);if (boundLeft < bestSolution) {pq.push(leftNode);}if (boundRight < bestSolution) {pq.push(rightNode);}}}}int m本人n() {// 读入电路板信息// ...// 调用分支限界法求解// ...return 0;}```4. 总结在本文中，我们使用C++语言实现了分支限界法来解决电路板排列问题。

电路板排列密度分支限界电路板排列密度分支限界是一个用于在电路板设计和布局过程中确定排列密度的技术指标。

它是根据电路板上元器件的和连接线的分布情况来进行界定的，以保证电路板的性能和稳定性。

排列密度是指在给定面积上所能容纳的元器件和连接线的数量。

在电路板设计的过程中，我们需要合理安排元器件的位置和连接线的布局，以使得电路板可以正常工作，并且避免元器件之间的干扰和相互影响。

由于电路板的面积有限，排列密度是一个重要的考虑因素。

如果元器件排列太密集，可能会导致元器件之间的短路或干扰，影响电路的性能。

如果排列过于稀疏，可能会浪费电路板上的空间，使得整个电路板过大，增加成本和功耗。

在电路板设计中需要根据实际情况确定排列密度的分支限界。

根据电路板设计的要求和元器件的特性，可以考虑以下因素来确定排列密度的分支限界：1. 元器件尺寸和间距：根据每个元器件的尺寸和间距要求，确定元器件的最小安装间距和最小连线间距，以确保元器件之间具有足够的空隙和隔离距离。

2. 热量分散：考虑元器件的热量分散和散热要求，避免元器件过度集中而导致热量难以散发，影响整个电路板的稳定性。

3. 信号和电源干扰：根据元器件的信号和电源要求，避免不同信号线或电源线之间的干扰和串扰，以确保电路的可靠性和稳定性。

4. 工艺限制：考虑到制造工艺的限制，避免元器件的尺寸过小或排列过于复杂，增加制造难度和成本。

最终确定的排列密度分支限界应该是一个平衡点，既要满足电路的性能和稳定性要求，又要考虑成本和制造难度等因素。

根据不同的电路需求和设计要求，排列密度的分支限界也会有所不同。

在电路板设计中，工程师需要综合考虑以上因素，并进行合理的评估和决策，以确保电路板的性能和可靠性。

布线问题（分⽀限界法）⼀、⾸先说⼀下分⽀限界法的思想：（1）⽐较：分⽀限界法和回朔法有相似之处，但是回朔法是搜索问题的所有解，采⽤深度优先搜索；⽽分⽀限界法是搜索问题的最优解，采⽤的是⼴度优先搜索；（2）核⼼思想：分⽀限界法中，每⼀个活节点都只有⼀次机会成为扩展节点。

活节点⼀旦成为扩展节点，就⼀次性产⽣所有的⼉⼦节点。

在这些⼉⼦节点中，导致不可⾏解或者导致⾮最优解的⼉⼦节点被舍弃，其余⼉⼦节点被加⼊活节点表中。

此后，从活节点表中取下⼀节点成为当前扩展节点，并重复上述节点的扩展过程。

这个过程⼀直在持续到找到所需要的最优解或者活节点表为空时为⽌；其中：选择扩展节点的⽅式可以分为：队列式分⽀限界法和优先队列式分⽀限界法。

后者相对于前者的改进是对活节点加⼊了优先级，优先级最⾼的成为扩展节点（通常通过最⼤堆最⼩堆实现）；⼆、布线问题描述：代码如下：//队列类 : LinkedQueue.h#ifndef LINKEDQUEUE_H#define LINKEDQUEUE_Htemplate <class Type>class LinkedQueue{public:LinkedQueue(){};explicit LinkedQueue(int Capacity); //创建队列bool IsEmpty(); //判断是否空bool IsFull(); //判断是否满bool Add(Type &cell); //向队列中加⼊元素bool Delete(Type &cell); //删除队列中的元素~LinkedQueue();private:Type cell;Type *ptr; //队列中的元素指针int QueueLen; //队列元素个数int QueueCapacity; //队列容量int Head;int Tail;};template <class Type>LinkedQueue<Type>::~LinkedQueue(){delete[]ptr;ptr = nullptr;}template <class Type>LinkedQueue<Type>::LinkedQueue(int Capacity){QueueCapacity = Capacity;Head = 0;Tail = 0;QueueLen = 0;ptr = new Type[QueueCapacity];}template <class Type>bool LinkedQueue<Type>::IsEmpty(){if (QueueLen == 0)return true;elsereturn false;}template <class Type>bool LinkedQueue<Type>::IsFull(){if (QueueLen == QueueCapacity)return true;elsereturn false;}template <class Type>bool LinkedQueue<Type>::Add(Type &cell){if (IsFull())return false;else{ptr[Tail] = cell;Tail++;QueueLen++;return true;}}template <class Type>bool LinkedQueue<Type>::Delete(Type &cell){if (IsEmpty())return false;else{cell = ptr[Head];Head++;QueueLen--;return true;}}#endif//使⽤分⽀限界法解决布线问题main.cpp//====================================================#include <iostream>#include "LinkedQueue.h"//#include <queue>using namespace std;int n, m; //布线盘是n * m⼤⼩class Position{public:int row;int col;};bool FindPath(int ** grid , Position start, Position finish, int &PathLen, Position * &path) {//计算从起始位置start到⽬标位置finish的最短布线路径//找到最短布线路径则返回true，否则返回flaseif ((start.row == finish.row) && (start.col == finish.col)){PathLen = 0;return true;}//设置⽅格阵列“围墙”for (int i = 0; i < m + 1; i++){grid[0][i] = grid[n + 1][i] = 1; //顶部和底部}for (int i = 0; i < n + 1; i++){grid[i][0] = grid[i][m + 1] = 1; //左翼和右翼}//初始化相对位移Position offset[4];offset[0].row = 0; offset[0].col = 1; //右offset[1].row = 1; offset[1].col = 0; //下offset[2].row = 0; offset[2].col = -1; //左offset[3].row = -1; offset[3].col = 0; //上int neigh_num = 4; //相邻⽅格数Position here, nbr;here.row = start.row;here.col = start.col;grid[start.row][start.col] = 2;//标记所有可以到达的⽅格位置LinkedQueue<Position> Q(n * m + 1); //队列//queue<Position> Q(); //队列//标记可到达的相邻⽅格do {for (int i = 0; i < neigh_num; i++){nbr.row = here.row + offset[i].row;nbr.col = here.col + offset[i].col;if (grid[nbr.row][nbr.col] == 0) //该⽅格未被锁定{grid[nbr.row][nbr.col] = grid[here.row][here.col] + 1;if ((nbr.row == finish.row) && (nbr.col == finish.col)) //完成布线break;Q.Add(nbr); //压⼊队列称为活节点}}//是否到达⽬标位置finish?if ((nbr.row == finish.row) && (nbr.col == finish.col)) //完成布线,是否要加这⼀步？ break;//活节点队列是否⾮空if (Q.IsEmpty()) //⽆解return false;Q.Delete(here); //取下⼀个扩展节点} while (true);//构造最短布线路径PathLen = grid[finish.row][finish.col] - 2;path = new Position[PathLen];//从⽬标位置finish开始向起始位置回溯here = finish;for (int j = PathLen - 1; j >= 0; j--){path[j] = here;//找前驱位置for (int i = 0; i < neigh_num; i++){nbr.row = here.row + offset[i].row;nbr.col = here.col + offset[i].col;if (grid[nbr.row][nbr.col] == j + 2)break;}here = nbr; //向前移动}return true;}int main(void){Position start, finish; //开始位置和⽬标位置int PathLen; //最短路径的长度Position *path; //记录的最短路径cout << "请输⼊布线盘的⼤⼩，n * m 规格： " << endl;cin >> n >> m;cout << "请输⼊开始位置(x , y) :" << endl;cin >> start.col >> start.row;cout << "请输⼊结束位置(x , y) :" << endl;cin >> finish.col >> finish.row;int ** grid = new int*[n + 2];for (int i = 0; i < n + 2; i++){grid[i] = new int[m + 2];}for (int i = 0; i < n + 2; i++){for (int j = 0; j < m + 2; j++){grid[i][j] = 0;}}FindPath(grid, start, finish, PathLen, path);for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){cout << grid[i][j] << " ";}cout << endl;}cout << "最短路径是： " << endl;cout << PathLen << endl;system("pause");return 0;}效果图类似：。

布线问题：如图1所示，印刷电路板将布线区域划分成n*m个方格。

精确的电路布线问题要求确定连接方格a的中点到b的中点的最短布线方案。

在布线时，电路只能沿直线或直角布线，如图1所示。

为了避免线路相交，已经布线的方格做了封锁标记（如图1中阴影部分），其他线路不允许穿过被封锁的方格。

3 问题的算法选择题目的要求是找到最短的布线方案，从图1的情况看，可以用贪婪算法解决问题，也就是从a开始朝着b的方向垂直布线即可。

实际上，再看一下图2，就知道贪婪算法策略是行不通的。

因为已布线的放个没有规律的所以直观上说只能用搜索方法去找问题的解。

根据布线方法的要求，除边界或已布线处，每个E-结点分支扩充的方向有4个：上、下、左、右，也就是说，一个E-结点扩充后最多产生4个活结点。

以图2的情况为例，图的搜索过程如图3所示。

搜索以a为第一个E-结点，以后不断扩充新的活结点，直到b结束（当然反之也可以）。

反过来从b到a，按序号8-7-6-5-4-3-2-1就可以找到最短的布线方案。

从图3中也可以发现最短的布线方案是不唯一的。

且由此可以看出，此问题适合用分支限界搜索。

#include <stdio.h>#include <stdlib.h>typedef struct Position{int row;int col;}Position;typedef struct team{int x;int y;struct team *next;}team,*TEAM;Position start,end,path[100];TEAM team_l=NULL;int a[100][100];int m,n,path_len;void output(){int i,j;printf("\n|-------------------布线区域图-------------------|\n");for(i=0;i<m+2;i++){for(j=0;j<n+2;j++){printf("%5d",a[i][j]);}printf("\n");}printf("|------------------------------------------------|\n");return;}void input_data(){char yes;int x,y;printf("创建布线区域...\n\n");printf("请输入区域大小(行列的个数): ");scanf("%d,%d",&m,&n);printf("请输入开始点坐标(x,y): ");scanf("%d,%d",&start.row,&start.col);printf("请输入结束点坐标(x,y): ");scanf("%d,%d",&end.row,&end.col);printf("区域内是否有被占用点? (y/n) ");fflush(stdin);scanf("%c",&yes);fflush(stdin);while(yes=='y'){printf("请输入占用点的坐标(x,y): ");scanf("%d,%d",&x,&y);fflush(stdin);if(x<0 || x>m+1 || y<0 || y>n+1 || (x==start.row && y==start.col) || (x==end.row && y==end.col)){printf("输入错误,请重新输入\n");continue;}else{a[x][y]=-1;}printf("是否还有被占用点? (y/n) ");scanf("%c",&yes);fflush(stdin);}for(x=0;x<m+2;x++){a[0][x]=-1;a[m+1][x]=-1;}for(x=0;x<n+2;x++){a[x][0]=-1;a[x][n+1]=-1;}return;}void inq(Position p){TEAM t,q;q=team_l;t=(TEAM)malloc(sizeof(TEAM));t->x=p.row;t->y=p.col;t->next=NULL;if(team_l==NULL){team_l=t;return ;}while(q->next!=NULL){q=q->next;}q->next=t;return;}Position outq(){Position out;out.row=team_l->x;out.col=team_l->y;team_l=team_l->next;return out;}void find_path(){Position offset[4];Position here={start.row,start.col};Position nbr={0,0};int num_of_nbrs=4;int i,j;offset[0].row=0;offset[0].col=1; //右offset[1].row=1;offset[1].col=0; //下offset[2].row=0;offset[2].col=-1;//左offset[3].row=-1;offset[3].col=0;//上printf("\n开始搜索路径...\n");if((start.row == end.row)&&(start.col == end.col)){ path_len = 0;return;}while(1){for(i=0;i<num_of_nbrs;i++){nbr.row=here.row+offset[i].row;nbr.col=here.col+offset[i].col;if(a[nbr.row][nbr.col]==0){a[nbr.row][nbr.col]=a[here.row][here.col] + 1;if((nbr.row == end.row) && (nbr.col == end.col)) break;inq(nbr); //nbr入队}}//是否到达目标位置finishif((nbr.row == end.row) && (nbr.col == end.col)) break;//或节点队列是否为空if(team_l==NULL){printf("\n没有结果\n");return ;}here=outq();}path_len=a[end.row][end.col];here=end;for(j=path_len-1;j>=0;j--){path[j] = here;for(i = 0;i < num_of_nbrs;i++){nbr.row = here.row + offset[i].row;nbr.col = here.col + offset[i].col;if(a[nbr.row][nbr.col] == j) //+ 2)break;}here=nbr;}return;}void out_path(){int i;printf("\n路径为:\n");printf("(%d,%d) ",start.row,start.col);for(i=0;i<path_len;i++){printf("(%d,%d) ",path[i].row,path[i].col);}printf("\n");return;}void main(){input_data();output();find_path();out_path();output(); }。

#include<iostream>#include<queue>#include<fstream>using namespace std;//import the grid data;ifstream fin("map.txt");//这个map是7行7列，请以这个为例子来理解这个程序typedef struct Position{int 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 offset[4];offset[0].row = -1;//upoffset[0].col = 0;offset[1].row = 1;//downoffset[1].col = 0;offset[2].row = 0;//leftoffset[2].col = -1;offset[3].row = 0;//rightoffset[3].col = 1;Posi here,nbr;here.row = start.row;here.col = start.col;int NumOfNbrs = 4;//ajacent position;grid[start.row][start.col] = 2;//init the start position's length with value 2,queue<Posi> Q;do{for(int firdex = 0;firdex < NumOfNbrs;firdex++){nbr.row = here.row + offset[firdex].row;nbr.col = here.col + offset[firdex].col;if(grid[nbr.row][nbr.col] == 0)//this position haven't been visted{grid[nbr.row][nbr.col] = grid[here.row][here.col] + 1;if((nbr.row == finish.row) && (nbr.col == finish.col))//find the shortest path{break;}Q.push(nbr);}}if((nbr.row == finish.row) && (nbr.col ==finish.col)){break;//wiring was completed}if(Q.empty())//if queue is empty{return false;//no result}here = Q.front();Q.pop();}while(true);//traceback the shortest pathPathLen = grid[finish.row][finish.col]-2;path = new Posi[PathLen];here = finish;for(int firdex = PathLen-1;firdex >=0;firdex--){path[firdex] = here;for(int secdex = 0;secdex < NumOfNbrs;secdex++){nbr.row = here.row + offset[secdex].row;nbr.col = here.col + offset[secdex].col;if(grid[nbr.row][nbr.col] == firdex+2)//It is the nbr's grid that why the grid[nbr.row][nbr.col] can give index of "firdex+2"{break;}}here =nbr;//move to the previous node}return 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++)grid[firdex] = new int[m+2];//set the boundfor(int index = 0;index < m+2;index++)//top an bottom {grid[0][index] = grid[n+1][index] =1;}for(int index = 0;index < n+2;index++){grid[index][0] = grid[index][m+1] = 1;}for(int firdex = 1;firdex < n+1;firdex++){for(int secdex = 1;secdex < m+1;secdex++)fin>>grid[firdex][secdex];}}//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 [] grid[firdex];grid[firdex] = 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;cout<<"Please input the m and n of the grid:"<<endl;cin>>n>>m;cout<<"Please input the start position:"<<endl;cout<<"start:row =";cin>>start.row;cout<<"start:col =";cin>>start.col;cout<<"Please input the finish position:"<<endl;cout<<"finish:row =";cin>>finish.row;cout<<"finish:col =";cin>>finish.col;InitGrid(grid,n,m);cout<<"the map resource:"<<endl;for(int firdex = 1;firdex < n+1;firdex++){for(int secdex = 1;secdex < m+1;secdex++)cout<<grid[firdex][secdex]<<" ";cout<<endl;}cout<<endl;FindPath(start,finish,PathLength,grid,path,n,m);cout<<"The shortest path of wiring is :"<<PathLength<<endl;cout<<"The path if follow:"<<endl;for(int index = 0;index < PathLength;index++){cout<<"("<<path[index].row<<","<<path[index].col<<")";if(index < PathLength-1)cout<<"-->";}cout<<endl;//Destory the resource of gridDestroy(grid,n,m);//release the path's resourceif(path != NULL){delete [] path;path = NULL;}return 0;}。

分支限界算法
通俗来讲，分支限界法是一种将一个具有相互冲突和复杂约束的大型优化问题划分成一系列规模较小的子问题的方法，并以此最终获得给定问题的最优解。

它把原问题分割成几个小子问题，每个子问题都有一个限制条件，分支限界法从一个子集中选择，分支出若干解法，并把选出的最优解作为下一次算法迭代的初始解，继续作为一个新的子集挑选优解，以此迭代直至找到了全局最优解。

分支限界法的运行流程主要包括以下几个步骤：
1.初始化：确定问题的规模大小及初始解；
2.分支：根据某种规则，将现有的一个节点分成若干个候选子节点，并构建子节点与父节点之间的映射关系；
3.限界：每个候选子节点都有一个下限价值，以降低算法计算量；
4.剪枝：根据某种明确的剪枝规则，去除那些应该剪枝的节点，减少计算量；
5.搜索：递归搜索下一个更优解，直至得出最优解。

0033算法笔记分支限界法分支限界法与单源最短路径问题 0033算法笔记-分支限界法分支限界法与单源最短路径问题1、分支限界法(1)叙述：使用广度优先产生状态空间一棵的结点，并采用剪枝函数的方法称作分枝限界法。

所谓“分支”是采用广度优先的策略，依次生成扩展结点的所有分支（即为：儿子结点）。

所谓“限界”是在结点扩展过程中，计算结点的上界（或下界），边搜索边减去搜寻一棵的某些分支，从而提升搜寻效率。

(2)原理：按照广度优先的原则，一个活结点一旦成为扩展结点（e-结点）r后，算法将依次生成它的全部孩子结点，将那些导致不可行解或导致非最优解的儿子舍弃，其余儿子加入活结点表中。

然后，从活结点表中取出一个结点作为当前扩展结点。

重复上述结点扩展过程，直至找到问题的解或判定无解为止。

(3)分支限界法与回溯法1)解目标：追溯法的解目标就是找到求解空间树中满足用户约束条件的所有求解，而分支限界法的解目标则就是找到满足用户约束条件的一个求解，或是在八十足约束条件的解中找出在某种意义下的最优解。

2)搜寻方式的相同：追溯法以深度优先的方式搜寻求解空间一棵，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。

(4)常见的分支限界法1)fifo分支限界法(队列式分支限界法)基本思想：按照队列先进先出(fifo)原则选取下一个活结点为扩展结点。

搜寻策略：一已经开始，根结点就是唯一的活结点，根结点入队。

从活结点队中抽出根结点后，做为当前拓展结点。

对当前拓展结点，先从左到右地产生它的所有儿子，用约束条件检查，把所有满足用户约束函数的儿子重新加入活结点队列中。

再从活结点表抽出队首结点（队中最先进去的结点）为当前拓展结点，……，直至找出一个求解或活结点队列入空年才。

2)lc(leastcost)分支限界法(优先队列式分支限界法)基本思想：为了加速搜索的进程，应采用有效地方式选择活结点进行扩展。

按照优先队列中规定的优先级选取优先级最高的结点成为当前扩展结点。

问题描述印刷电路板将布线区域划分成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.}程序运行结果如图：。