《数据结构与算法分析》课件第10章-搜索策略

第十章搜索策略搜索策略是从问题的解空间中搜索问题解的方法，本章将介绍两种常见的搜索算法：回溯法和分支界限法。回溯法回溯法的应用分支界限法分支界限法的应用一种既带有系统性又带有跳跃性的搜索算法，它在包含问题所有解的空间树中按照深度优先的策略从根结点出发搜索解空间树。回溯法回溯法回溯法在求问题所有的解时，需要回溯到树根，且在解空间树中的所有结点全部搜索完成后结束。当仅求问题的任意一个解时，只需要搜索到问题的一个解就可以结束。算法思想对解空间中任意一个结点，判断该结点是否不包含问题的解：不包含，则跳过以该结点为根的子树系统搜索，逐层向其祖先结点回溯；包含，则进入该子树并继续按深度优先的策略进行搜索。问题的解空间问题的解空间与解空间树解空间由长度为n的0-1向量组成，该解空间包含了对变量的所有可能的0-1赋值。树根代表了在查找解之前的初始状态。树的第一层节点代表了对解的第二个分量所做的选择，以此类推。如果一个部分构造树（子树）仍然有可能导致一个完全解，我们说这个部分分解在树中的相应节点是有希望的，否则说是没希望的。叶子要么代表没希望的，要么代表算法找到完全解。

问题的解空间0-1背包问题（n种物品）【例1】当n = 3时，其解空间是：

{(0,0,0),(0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),

(1,1,0),(1,1,1)}0-1背包问题的解空间树从根到叶路径上编码即解空间元素若取W=（16,15,15），P=（40,25,25），C=30时间复杂度：O(2n)回溯策略的基本思想基本思想(1)

当前结点成为活结点及扩展结点；(2)

从当前扩展结点向纵深方向搜索并移至一个新结点，这个新结点就成为一个新的活结点及当前的扩展结点；(3)

若当前扩展结点不能向纵深移动则成死结点，回溯至最近的活结点—成为当前扩展结点；(4)递归搜索，直至找到所要求的解或解空间中已无活结点时为止。

从开始结点(根结点)出发，以深度优先的方式搜索整个解空间：回溯策略的基本思想(1)

从根结点A开始搜索（唯一的活结点及当前扩展结点）。(2)从结点A沿纵深方向先移至结点B或结点C(以先选结点B为例)，此时A和B是活结点，结点B成为当前的扩展结点。由于选取了w0，因此在结点B处剩余背包容量r = 14，获取的价值为45。(3)从结点B可移至结点D或结点E，由于移至结点D至少需要的背包容量为w1 = 15，而当前仅有的剩余容量r = 14，因此移到结点D将导致一个不可行解；而移到结点E不需要背包容量，因而是可行的，此时结点E成为新的扩展结点，在结点E处，r = 14，获取的价值为45。(4)

这时结点A、B和E是活结点。从结点E可移到结点J或结点K，类似地，移到结点J导致一个不可行的解，而移到结点K是可行的，于是结点K成为新的扩展结点。(5)由于K是叶子结点，因此得到一个可行的解，即x = (1,0,0)，获得的价值为45。同理可获得其他可行解，从其中选择一个最优解作为问题最终解。【例2】n = 3的0-1背包问题。

设w={16,15,15}，v={45,25,25}，c=30分析：回溯策略的基本思想运用回溯法解题的关键要素有以下三点(1)针对给定的问题，定义问题的解空间；(2)确定易于搜索的解空间结构；(3)以深度优先方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索。递归和迭代回溯voidBackTrace(intt){

if(t>n)Output(x);

else for(inti=f(n,t);i<=g(n,t);i++){ x[t]=h(i);

if(Constraint(t)&&Bound(t))

BackTrace(t+1); }}

//BackTrace可用递归函数实现回溯法，递归函数模板如下：说明：t表示递归深度，即当前扩展结点在解空间树的深度；n控制递归深度，即解空间树的高度。当t＞n时，算法已搜索到一个叶子结点，此时函数Output(x)对得到的可行解x进行记录或输出处理。用f(n,t)和g(n,t)分别表示在当前扩展结点处未搜索过的子树的起始编号和终止编号；h(i)表示在当前扩展结点处x[t] 的第i个可选值；函数Constraint(t)和Bound(t)分别表示当前扩展结点处的约束函数和限界函数。递归和迭代回溯voidIterativeBackTrace(void){intt=1;

while(t>0){

if(f(n,t)<=g(n,t))

for(inti=f(n,t);i<=g(n,t);i++){

x[t]=h(i);

if(Constraint(t)&&Bound(t)){ if(Solution(t))Output(x);

elset++; }

}

elset--;

}}//IterativeBackTrace迭代回溯算法模板如下：说明：Solution(t)判断在当前扩展结点处是否已得到问题可行解，若其返回值为真，则表示在当前扩展结点处x[1:t]是问题一个可行解；否则表示在当前扩展结点处x[1:t]只是问题的一个部分解，还需向纵深方向继续搜索。子集树与排列树voidBackTrace(intt){if(t>n)Output(x);

else

for(inti=0;i<=n;i++){ x[t]=i; if(Contraint(t)&&Bound(t)) BackTrace(t+1);

}}//BackTrace子集树当给定的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间树称为子集树。例：n个物品的0-1背包问题所对应的解空间树是一棵子集树。回溯法搜索子集树的一般算法描述如下：子集树与排列树voidBackTrace(intt){

if(t>n)Output(x);

else

for(inti=0;i<=n;i++){

Swap(x[t],x[i]);

if(Contraint(t)&&Bound(t)) BackTrace(t+1);

Swap(x[t],x[i]);

}}//BackTrace排列树给定的问题是确定n个元素满足某种性质的排列时，对应的解空间树称为排列树。回溯法搜索排列树的一般算法描述如下：回溯法的应用给定一个无向图G=(V,E)，如果UV，且对任意u,v∈U有(u,v)∈E，则称U是G的一个完全子图。G的完全子图U是G的一个团当且仅当U不包含在G的更大的完全子图中；G的最大团是指G中所含顶点数最多的团。

子集 {1,2} 是G的一个大小为2的完全子图，它不是一个团，原因是它包含于G的更大完全子图 {1,2,5} 中；而 {1,2,5} 是G的一个最大团。同理，完全子图

{1,4,5}和 {2,3,5} 也是G的最大团。最大团问题问题描述回溯法的应用给定一个无向图G=(V,E)，如果UV，且对任意u,v∈U有(u,v)∈E，则称U是G的一个完全子图。G的完全子图U是G的一个团当且仅当U不包含在G的更大的完全子图中；G的最大团是指G中所含顶点数最多的团。

(a)和(b)是两个互为补图的无向图，{2,4}是G的一个空子图，也是G的最大独立集。而{1,2}是G' 的空子图，但它不是G' 的独立集，原因是它包含在G'的空子图{1,2,5}中。空子图{1,2,5}是G' 的最大独立集。注：若U是G的最大团当且仅当U是G'的最大独立集。回溯法的应用算法设计无向图G的最大团和最大独立集问题都可以用回溯法在时间复杂度为O(n2n)以内解决，且都可以看做图G的顶点集V的子集选取问题，因此可以用子集树表示问题的解空间。设当前扩展结点Z位于解空间树的第i层，在进入左子树前，必须确认从顶点i到已选择进入的顶点集之中每个顶点都有边相连；在进入右子树前，必须确认还有足够多的可选择顶点使得算法有可能在右子树中找到更大的团。回溯法的应用int**a;//图G的邻接矩阵intn;//图G的顶点数int*x; //当前解int*bestx;//当前最优解intcn;//当前顶点数intbestn;//当前最大顶点数voidBackTrace(inti){ if(i>n){ for(intj=1;j<=n;j++) bestx[j]=x[j];bestn=cn; return;

}

//检查顶点i与当前团是否连接 ….…//见下页回溯法的应用

//检查顶点i与当前团是否连接 intOK=1;

for(intj=1;j<i;j++) if(x[j]&&a[i][j]==0){//i与j不相连 OK=0;break;

}

if(OK){

x[i]=1;cn++;BackTrace(i+1);x[i]=0;cn--;

}

if(cn+ni>bestn){

x[i]=0;BackTrace(i+1);

}}intMaxClique(int**a,intv[],intn){

cn=0;bestn=0;bestx=v;BackTrace(1);

returnbestn;}回溯法的应用问题描述给定一个无向连通图G和m种不同的颜色，用这些颜色为图G的各顶点着色，每个顶点染一种颜色，那么是否存在一种着色方案使得相邻顶点不重色。若一个图至少需要m种颜色才能使图中任何相邻顶点不重色，则m称为该图的色数。注：如果一个图的所有顶点和边都能用某种方式画在一个平面上且没有任何两条边相交，则称这个图为平面图。图的m着色问题求一个图的色数m的问题称为图的m可着色优化问题。回溯法的应用邻接矩阵a表示无向连通图G=(V,E)，若(i,j)∈E，则a[i][j]=1；否则a[i][j]=0。用整数1～m表示m种不同颜色，顶点i所染的颜色用x[i] 表示，因此该问题的解向量可表示为x[1:n]。问题的解空间可表示为一棵高度为n+1的完全m叉树，解空间树的第i(1≤i≤n)层中的每一个结点都有m个孩子，其中每个孩子对应于x[i] 的m种可能的着色之一；第n + 1层结点均为叶子结点。算法设计n = 3和m=3时问题的解空间树回溯法的应用求解图的m可着色问题的过程就是遍历解空间树的过程，并在遍历过程中记录所有可行的着色方案，遍历过程是向前搜索和回溯两个过程的综合，以期望获得所有可能的解(着色方案)。//N-图的顶点数//M-可用的颜色数//a-图的邻接矩阵//x-当前的解//sum-可m着色的方案数#defineN20#defineM5intsum,p[N+1],*x,**a[N+1][N+1];sum=0;x=p;回溯法的应用voidmColoring(){

for(inti=0;i<=N;i++)p[i]=0;

BackTrace(1);}voidBackTrace(intt){if(t>N){

sum++;

for(inti=1;i<=N;i++)printf("%d''",x[i]);

printf("\n");

}

else{ for(inti=1;i<=N;i++){

[t]=i;

if(OK(t))BackTrace(t+1);

}

}}时间复杂度O(nmn)回溯法的应用intOK(intt){

for(inti=1;i<=N;i++)

if((a[t][i]==1)&&(x[i]==x[t]))

return0;

return1;}(1)递归函数BackTrace(1)实现整个解空间回溯搜索，BackTrace(i)搜索解空间中的第i层子树。说明：(3)i≤n时当前扩展结点Z是解空间中的一个内部结点，该结点有x[i]=1,2,3,…,m共m个孩子结点，由函数OK检查其可行性，并以深度优先的方式递归地对可行子树进行搜索，或剪去不可行子树。(2)i＞n时表示该算法已搜索到一个叶子结点，得到新的m着色方案。回溯法的应用设某旅行售货员要到多个城市推销商品，已知各城市之间的路程(旅费)，现在为其设计一条售货路线，要求从某驻地出发经过每个城市一遍，最后又回到驻地，且使总的路程(旅费)最小。旅行售货员问题问题描述设G=(V,E)是一个带权图，其中，各条边的权(费用)为正整数；每一条周游路线是包含V中所有顶点的一条回路；一条周游路线的费用是该回路上所有边的权之和。所谓旅行售货员问题就是要在图G中找出一条有最小费用的周游路线。问题形式描述：回溯法的应用算法设计旅行售货员问题的解空间树是一棵排列树，根据排列树的递归算法模板，可得到如下算法：//n-图的顶点数；//a[n+1][n+1]-图的邻接矩阵；//x[n]-当前解；//bestx[n+1]-当前最优解；//cc-当前费用；//bestc-当前最优值；//NoEdge-无边标记；voidBackTrace(inti){if(i==n){

if((a[x[n

1]][x[n]]!=NoEdge)&&(a[x[n]][1]!=NoEdge)&&

(((cc+a[x[n

1]][x[n]]+a[x[n]][1])<bestc)||

(bestc==NoEdge))){

for(intj=1;j<=n;j++)

bestx[j]=x[j];}

}回溯法的应用

else{

for(intj=i;j<=n;j++)

//是否可以进入x[j]子树

if((a[x[i

1]][x[j]]!=NoEdge)&&

(((cc+a[x[i

1]][x[i]])<bestc)||(bestc==NoEdge))){

//搜索子树

Swap(x[i],x[j]);

cc+=a[x[i

1]][x[i]];

BackTrace(i+1);

cc

=a[x[i

1]][x[i]];

Swap(x[i],x[j]);

}

}}voidTravelRoute(){for(inti=1;i<=n;i++)x[i]=i;//初始化bestc=NoEdge; cc=0;

BackTrace(2);}回溯法的应用(1)

递归函数BackTrace中，当i=n时，当前扩展结点是排列树的叶子结点的双亲结点，此时算法检测图G是否存在两条边：一条从顶点x[n-1]到x[n]的边和一条从顶点x[n]到顶点x[1]的边。如果这两条边都存在，则找到了一条旅行售货员回路，此时算法还需要判断这条回路的费用是否优于已经找到的当前最优回路的费用bestc，如果是，则必须更新当前最优值bestc和当前最优解bestx。说明：(2)当i＜n时，当前扩展结点位于排列树的第i-1层，图G中存在从顶点x[i-1] 到顶点x[i]的边时，x[1:i]构成图G的一条路径，且当x[1:i]的费用小于当前最优值时算法进入排列树的第i层；否则将剪去相应的子树。算法中的变量cc记录当前路径x[1:i] 的费用。上述整个算法的时间复杂度为O(n!)分支界限法解题目标不同：分支界限法的解题目标是找出解空间树T中满足约束条件的一个解，或是在满足约束条件的解中找一个使目标函数值极大或极小的解，即某种意义下的最优解；而回溯法的解题目标是找出T中满足约束条件的所有解。在解空间树T上的搜索方式不同：回溯法以深度优先方式搜索T；而分支界限法以广度优先或最小耗费优先的方式搜索T。分支界限法是一种在问题的解空间树T上搜索问题解的算法分支界限法与回溯法的区别分支界限法在每一个活结点处计算函数值(限界)，并根据已计算出的函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间中有最优解的分支推进，以便尽快找出一个最优解。搜索策略在扩展结点处生成其所有的孩子结点(分支)，然后再从当前的活结点表中选择下一个扩展结点；分支界限法以广度优先或最小耗费(最大效益)优先的方式搜索问题的解空间树分支界限法常见解空间树(1)每一个活结点只有一次机会成为扩展结点，一次性产生其所有孩子结点；孩子结点中导致不可行解或导致非最优解的结点被舍弃，其余结点被加入活结点表。然后从活结点表中取当前扩展结点的下一个结点成为扩展结点。(2)重复上述结点的扩展过程，直至找到所需的解或活结点表空时为止。子集树和排列树基本思想分支界限法活结点表中选择下一个扩展结点作为当前扩展结点的方法(1)一般队列方法。一般队列方法是将活结点表组织成一般队列，并按队列中结点先进先出的原则选取下一个结点作为当前扩展结点。(2)优先级队列方法。优先级队列方法是将活结点表组织成一个优先级队列，并按优先级队列中规定的结点优先级来选取优先级最高的下一个结点作为当前扩展结点。分支界限法【例2】n = 3时的0-1背包问题。设w={16,15,15},p={45,25,25},c=30，其解空间树如图：分支界限法搜索解空间树的方法与解空间树的广度优先遍历算法极为相似，唯一不同之处是分支界限法不搜索以不可行结点为根的子树。分支界限法一般队列分支界限法：用队列存放活结点表；算法从根结点开始，初始时活结点队列为空，结点A是当前活结点；结点A的两个孩子B和C都是可行结点，故将结点B和结点C入队，并且舍弃当前扩展结点A；在活结点队列中取出活结点B作为当前扩展结点，扩展结点B有两个孩子D和E，由于结点D是不可行结点故舍弃，结点E是可行结点故入队；再从活结点队列中取出结点C作为当前扩展结点，继续上述计算，直至活结点队列空为止，算法终止。该算法搜索得到的最优值是50。分支界限法分支界限法与回溯法的区别求解目标不同回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。搜索方式的不同回法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先（最大效益）的方式搜索解空间树。分支界限法的应用分支限界法：每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。回溯法：当探索到某一结点时，要先判断该结点是否包含问题的解。如果包含，就从该结点出发继续探索下去；如果该结点不包含问题的解，则逐层向其祖先结点回溯。对扩展节点的扩展方式不同对存储空间的要求不同

分支限界法的存储空间比回溯法大得多，因此当内存容量有限时，回溯法成功的可能性更大。分支界限法的应用装载问题问题描述设有n个集装箱，计划将其装上两艘载重量分别为c1和c2的轮船，其中集装箱i的重量为wi，且。那么是否有一个合理的装载方案，可将n个集装箱装上这两艘轮船。问题分析当时，装载问题等价于子集和问题；当c1=c2，且

时，装载问题就等价于划分问题。分支界限法的应用采用下面的策略可以得到一个最优装载方案：算法设计(1)将第一艘轮船尽可能地装满；(2)

将剩余的集装箱装到第二艘轮船上。第一艘轮船尽可能地装满等价于选取全体集装箱的一个子集，使该子集中的集装箱重量之和最接近c1。由此可知，装载问题等价于以下特殊的0-1背包问题：装载问题是一个子集选取问题，其解空间树是一棵子集树分支界限法的应用一般队列分支界限法voidMaxLoading(intw[],intc,intn){

intlayer,Ew,bestw,wt;

layer=1;Ew=0;bestW=0;//初始化

InitQueue(Q);

//初始化队列，解空间树中的根结点入队

add(Q,Ew);

add(Q,

1)；

//搜索子集解空间树

while(!QueueIsEmpty(Q)){ delete(Q,Ew); //此时的Ew为0

if(Ew==1){

if(IsEmpty(Q))break;

add(Q,

1);

delete(Q,Ew);

layer++;

}分支界限法的应用

//检查左孩子结点

wt=Ew+w[layer];

if(wt<=c){//可行结点

x[layer]=1;

if(wt>bestw)bestw=wt;

if(layer<n)add(Q,wt);

}

add(Q,Ew); //右孩子结点总是可行的

}//while}说明：MaxLoading函数完成对解空间的分支界限搜索；队列Q用于存储活结点；Q中的Ew表示每个活结点所对应的当前载重量。分支界限法voidEnQueue(Q,intwt,int&bestw,intn){

//将活结点加入Q队列

if(i==n){ if(wt>bestw)

//可行叶子结点

bestw=wt;}

else{

//非叶子结点

add(Q,wt)；}}说明：函数EnQueue将活结点加入到活结点队列Q中。该函数检查i是否等于n，如果i=n，则表示当前活结点为叶子结点，因叶子结点不会进一步扩展，因此不必将其加入到活结点队列，此时检查该叶子结点所表示的可行解是否优于当前最优解，并适时更新当前最优解；否则当前活结点是内部结点，应加入到活结点队列中。分支界限法的应用算法改进设bestw是当前最优解，Ew是当前扩展结点对应的重量，r是剩余集装箱的重量。若Ew + r≤bestw，则可以将扩展结点所对应的子树剪去。函数MaxLoading将bestw初始化为0，直至搜索到叶子结点时才更新bestw，因此在算法搜索到第一个叶子结点之前bestw = 0，且r＞0，故Ew+r＞bestw总成立，即此时右子树测试不起作用。为了使上述右子树测试尽早发挥作用，应提前更新bestw。而我们知道算法最终找到的最优值是所求问题的子树中所有可行结点对应的重量最大值，并且结点所对应的重量仅在搜索进入左子树时增加，因此可以在算法每次进入左子树时更新bestw的值。分支界限法的应用voidMaxLoading(intw[],intc,intn){InitQ();//初始化队列intEw,bestw,r,layer,wt,i;Ew=0;//扩展结点所对应的载重量bestw=0;//当前的最优载重量r=0;//剩余集装箱重量layer=1;

//当前扩展结点所处的层

for(intj=2;j<=n;j++)r+=w[j];add(Q,Ew);//起始设置队列add(Q,

1);

while(!IsEmpty(Q)){delete(Q,Ew);

if(Ew==

1){

if(IsEmpty(Q)) break;

add(Q,

1);delete(Q,Ew);

layer++;

r

=w[layer]；

}分支界限法的应用

//检查左孩子结点

wt=Ew+w[layer]; //左孩子结点的重量

if(wt<=c){ //可行结点

if(wt>bestw)

bestw=wt; //更新最优值

if(layer<n)

add(Q,wt); //加入活结点队列

}

//检查右孩子结点

if(((Ew+r)>bestw)&&(layer<n))

add(Q,Ew); //可能包含最优解

}}分支界限法的应用voidEnQueue(structQNode*activeQ,intwt,inti,intn,intbestw,structQNode*E,structQNode*bestE,intbestx[],intflagChild){

if(i==n){ //可行叶子结点 if(wt==bestw){//当前最优装载重量

bestE=E;

bestx[n]=flagChild; } return;

}

//非叶子结点

structQNode*q;

q->weight=wt;

q->parent=E->parent;

q->flagOfChild=flagChild;

add(Q,q);}将活结点加入到活结点队列中的函数EnQueue如下：分支界限法的应用intMaxLoad(intw[],intc,intn,intbestx[]){

//返回最优载重量，bestx返回最优解

structQNode*aQ;

//活结点队列

add(aQ,-1);//同层结点尾部标志

inti=1;//当前扩展结点所处的层

intEw=0;//对应扩展结点的载重量

intbestw=0;//当前最优载重量

intr=0;

//剩余集装箱重量for(intj=2;j<=n;j++)

r+=w[j];structQNode*Eq=0;//当前扩展结点

structQNode*bestE;//当前最优扩展结点

分支界限法的应用

//搜索子集空间树

while(true){//检查左孩子结点

intwt=Ew+w[i];

if(wt<c){//可行结点

if(wt>bestw)bestw=wt;

EnQueue(aQ,wt,i,n,bestw,Eq,bestE,bestx,1);

}

//检查右孩子结点

if(Ew+r>bestw)

EnQueue(aQ,wt,i,n,bestw,Eq,bestE,bestx,0);

delete(aQ,Eq);

//取下一个扩展结点

if(!Eq){//同层结点尾部

if(IsEmpty(aQ))break;

add(aQ,0);

//同层结点尾部标志

delete(aQ,Eq);//取下一个扩展结点

i++;//进入下一层

r-=w[i];

}

}//while分支界限法的应用

//构造当前最优解

for(intj=n-1;j>0;j--){

bestx[j]=bestE->flagOfChild;

bestE=bestE->parent;}returnbestw;}分支界限法的应用构造最优解

为了在算法结束后能方便地构造出与最优值相对应的最优解，算法必须记录相应子集树中从活结点到根的路径，为此，必须设置指向其双亲结点的指针，并设置左右孩子标志。活结点队列的数据结构如下：structQNode{structQNode*parent;

intflagOfChild;//0表示左孩子；1表示右孩子intweight;};分支界限法的应用印刷电路板将布线区域划分成n × m个方格阵列，如图(a)所示。电路布线问题要求确定连接方格a的中点和方格b的中点的最短布线方案。在布线时，电路只能沿直线或直角布线，并且要求所布线路不能相交，如图(b)所示。为了避免线路相交，已经布线的方格应设置封锁标记，其他线路不允许穿过已经封锁的方格。布线问题问题描述分支界限法的应用分析布线问题的解空间是一个图，用队列分支界限法解此问题。从起始位置a开始，将其作为第一个扩展结点，与该扩展结点相邻并且可达的方格成为可行结点被加入到活结点队列中，并且将这些方格标记为1，即从起始方格a到这些方格的距离为1。接着从活结点队列中取出队首结点作为下一个扩展结点，并将与当前扩展结点相邻且未标记过的方格标记为2，并存入活结点队列。这个过程一直持续到算法搜索到目标方格b，或活结点队列空时结束。分支界限法的应用首先考虑记录电路板上某方格位置：用结构体表示。结构体有row和col两个成员。其次需要表示布线前进的方向：布线可沿右、下、左、上四个方向移动，分别用0、1、2、3表示。再用offset[i].row和offset[i].col(i=0,1,2,3)表示沿着四个方向移动一步时对于当前方格的相对位移，如下表所示。移动方向行位移(offset[i].row)列位移(offset[i].col)0右011下102左0-13上-10用二位数组grid[i][j]表示电路板上某方格的布线，grid[i][j]=0表示该方格允许布线；grid[i][j]=1表示该方格不允许布线。分支界限法的应用voidFindPath(structPositionbeginP,structPositionendP){

intfinished=0;if((beginP.row==endP.row)&&(beginP.col==endP.col)) pathLen=0;

else{ for(inti=0;i<=m+1;i++){

grid[0][i]=1;

grid[n+1][i]=1; } for(inti=0;i<=n+1;i++){

grid[i][0]=1;

grid[i][m+1]=1; }

算法分支界限法的应用

structPositionoffset[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; intnumbersOfNeighbor=4; structPositioncurrentP,currentNeighbor; currentP.row=beginP.row; currentP.col=beginP.col; grid[beginP.row][beginP.col]=MAX; structActiveNodeQueueactiveQ;分支界限法的应用

while(finished==0){ for(inti=0;i<numbersOfNeighbor;i++){ currentNeighbor.row=currentP.row+offset[i].row; currentNeighbor.col=currentP.col+offset[i].col; if(grid[currentNeighbor.row][currentNeighbor.col]==0){

grid[currentNeighbor.row][currentNeighbor.col] =grid[currentP.row][currentP.col]+1;