图的搜索算法.ppt

第五章 图的搜索算法,51 图搜索概述 511 图及其术语 512 图搜索及其术语52 广度优先搜索 521 算法框架 522 广度优先搜索的应用,上一页 下一页 返回首页,图是一种限止最少的数据结构，因此更接近现实，实际问题中很多数据关系都可以抽象成图，相关问题则可利用图的基本算法进行求解，很早就有专门研究图的是一门数学学科“图论”；其中的计算问题包括图的搜索、路径问题、连通性问题、可平面性检验、着色问题、网络优化等。图论中的著名算法有：求最小生成树的Kruskal算法、求最短路径的Dijkstra算法和Floyd算法、求二部图最大匹配（指派问题）的匈牙利算法、求一般图最大匹配的Edmonds“花”算法、求网络最大流和最小割的算法等。其中的一些算法在数据结构课程中已经学习过了。,1显式图与隐式图,在路径问题、连通性问题、可平面性检验、着色问题和网络优化等问题中，图的结构是显式给出的，包括图中的顶点、边及权重，这类图我们称为显式图，也就是一般意义上的图。,隐式图是由问题的初始结点，为了求解或求证问题，根据题目的规则（一般是由题目的意思隐含给出的），也就是生成子结点的约束条件，逐步扩展结点，直到得到目标结点为止的一个隐式的图。,511 图及其术语,2.显式图的常用术语,如图5-1所示的，均为显式图(Graph)。图中的这些点(v1,v2,vn)被称为顶点(vertex)或结点，连接顶点的曲线或直线称为边(edge)。通常将这种由若干个顶点以及连接某些顶点的边所组成的图形称为图，顶点通常被称作是图中的数据元素.,上一页 下一页 返回首页,图,带权图：j即图5-2给图 5-1中各图的边上附加一个代表性数据(比如表示长度、流量或其他)，则称其为带权图。环(cycle)：图5-1中 图中的 v 1点本身也有边相连，这种边称为环。有限图：顶点与边数均为有限的图，如图 5-1中的三个图均属于有限图。简单图：没有环且每两个顶点间最多只有一条边相连的图，如图 5-1中的 图。邻接与关联：当（v 1，v 2）E，或 E，即 v 1，v 2间有边相连时，则称 v 1和 v 2是相邻的，它们互为邻接点（adjacent），同时称（v 1，v 2）或 是与顶点 v 1、v 2相关联的边。,上一页 下一页 返回首页,顶点的度数(degree)：从该顶点引出的边的条数，即与该顶点相关联的边的数目，简称度。入度（indegree）：有向图中把以顶点 v为终点的边的条数称为是顶点 v的入度。出度（outdegree）：有向图中把以顶点 v为起点的边的条数称为是顶点 v的出度。终端顶点：有向图中把出度为 0的顶点称为终端顶点，如图 5-1中 图的 v 3。路径与路长：在图 G=(V，E)中，如果存在由不同的边(v i0，v i1)，(v i1，v i2)，(v in-1，v in)或是，)组成的序列，则称顶点 v i0，v in是连通的，顶点序列（v i0，v i1，v i2，v in）是从顶点 v i0到顶点 v in的一条道路。路长是道路上边的数目，v i0到 v in的这条道路上的路长为 n。连通图：对于图中任意两个顶点 v i、v j V，v i、v j之间有道路相连，则称该图为连通图。如 5-1中的 图。网络：带权的连通图，如图 5-2所示。,3隐式图术语 1）子集树,当要求解的问题需要是在n 个元素的子集中进行搜索，其搜索空间树被称作子集树（subset tree）。这n个元素都有在子集中或被选取记为1，不在子集中或被舍去记为0，这样搜索空间为：（0，0，0，0），（0，0，0，1），（0，0，1，0），（0，0，1，1），（1，1，1，1）。共2n 个状态。若表示为树形结构就是一棵有2n个叶结点的二叉树，对树中所有分支进行遍历的算法都必须耗时O（2n）。,上一页 下一页 返回首页,图5-3 n=3的子集树,上一页 下一页 返回首页,2）排列树,上一页 下一页 返回首页,当要求解的问题需要在n 元素的排列中搜索问题的解时，解空间树被称作排列树（permutation tree）。搜索空间为：（1，2，3，n-1，n）,（2，1，3，n-1，n）,（2，3，1，n-1，n）,（2，3，4，1，n-1，n）,（n，n-1，3，2，1）第一个元素有n 种选择，第二个元素有n-1种选择，第三个元素有n-2种选择，第n个元素有1种选择，共计n!个状态。若表示为树形就是一个n度树，这样的树有n!个叶结点，所以每一个遍历树中所有节点的算法都必须耗时O(n!),上一页 下一页 返回首页,图5-3 n=4的部分子集树,4图的存储 1）邻接矩阵法,上一页 下一页 返回首页,邻接矩阵是表示顶点之间相邻关系的矩阵，设G=(V,E)是具有n个顶点的图，则G的邻接矩阵可定义为：Ai,j=1,若（Vi,Vj)或是E(G)中的边。Ai,j=0,若(Vi,Vj)或不是E(G)中的边。若G是网络，则邻接矩阵可定义为：Ai,j=Wij 若（Vi,Vj)或属于E(G);Ai,j=0或 若（Vi,Vj）或 不属于E(G);其中，Wij表示边上的权值，表示一个计算机允许的，大于所有边上权值的数；,上一页 下一页 返回首页,2）邻接表,上一页 下一页 返回首页 例1,对于图G中的每个结点Vi,把所有邻接于Vi的顶点Vj链成一个单链表，这个单链表就称为顶点Vi的邻接表。邻接表由边表和顶点两部分组成。边表为一个单链表，每个表结点均有两个域：邻接点域adjvex，存放与vi相邻接的顶点vj的序号j。链域next，将邻接表的所有表结点链在一起。顶点表为一数组，每个元素均有两个域：顶点域vertex，存放顶点vi的信息 指针域firstedge，vi的边表的头指针。对于无向图来说，Vi的邻接表中每个表结点都对应于与Vi相关联的一条边，对于有向图来说，Vi的邻接表中每个表结点对应于Vi为始点射出的一条边。,图7.1,上一页 下一页 返回首页,图5-5 图5-1中（1）图的邻接表,512 图搜索及其术语,1穷举搜索与启发式搜索,穷举搜索是对图的最基本的搜索算法，是蛮力策略的一种表现形式。即不考虑给定问题的特有性质，按事先定好的顺序，依次运用规则，盲目搜索的方法。,启发式搜索是利用一些启发信息，提前判断出先搜索哪些状态可能尽快找到问题的解或某些情况不可能取到最优解，从而可以提前舍弃对这些状态的尝试。即考虑给定问题的特有性质，选用合适的细则，提高搜索的效率。,上一页 下一页 返回首页,2相关概念和术语,上一页 下一页 返回首页,问题状态:树中的每一个结点确定所求解问题的一个问题状态。状态空间:由根结点到其它结点的所有路径（分支），就确定 了这个问题的状态空间。解状态:是这样一些问题状态S，对于这些问题状态，由根到S 的那条路径确定了这解空间中的一个元组。答案状态:是这样的一些解状态S，对于这些解状态而言，由 根到S的这条路径确定了这问题的一个解状态空间树:解空间的树结构又称隐式图。,活结点：如果已生成一个结点而它的所有儿子结点还没有全部生成，则这个结点叫做活结点。E-结点：当前正在生成其儿子结点的活结点叫E-结点（正 扩展的结点）。死结点：不再进一步扩展或者其儿子结点已全部生成的生成结点就是死结点。,521 算法框架,1算法的基本思路,算法设计的基本步骤为：,1）确定图的存储方式；2）图的遍历过程中的操作，其中包括为输出问题解而进行的存储操作；3）输出问题的结论。,上一页 下一页 返回首页,2算法框架,上一页 下一页 返回首页 例1,从广度优先搜索定义可以看出活结点的扩展是按先来先处理的原则进行的，所以在算法中要用“队”来存储每个E-结点扩展出的活结点。为了算法的简洁，抽象地定义：queue为队列类型，InitQueue()为队列初始化函数，EnQueue(Q，k)为入队函数，QueueEmpty(Q)为判断队空函数，DeQueue(Q)为出队函数。实际应用中，用数组或链表实现队列。开辟数组visited记录visited结点的搜索情况。在算法框架中以输出结点值表示“访问”。,1）邻接表表示图的广度优先搜索算法,int visitedn;/n 为结点个数/bfs(int k,graph head)int i；queue Q；edgenode*p；/定义队列/InitQueue(Q)；/队列初始化/print(“visit vertex”，k)；/访问源点vk/visitedk=1；EnQueue(Q，k)；/vk已访问，将其入队。/while(!QueueEmpty(Q)/队非空则执行/i=DeQueue(Q)；/vi出队为E-结点/p=headi.firstedge；/取vi的边表头指针/while(pnull)/扩展E-结点/if(visitedp-adjvex=0)/若vj未访问过/print(“visitvertex”，p-adjvex)；/访问vj/visitedp-adjvex=1；EnQueue(Q，p-adjvex)；/访问过的vj人队/p=p-next；/找vi的下一邻接点/,2）邻接矩阵表示的图的广度优先搜索算法,上一页 下一页 返回首页,bfsm(int k,graph g100，int n)int i，j；CirQueue Q；InitQueue(Q)；print(visit vertex，k)；/访问源点vk/visitedk=1；EnQueue(Q，k)；while(not QueueEmpty(Q)i=DeQueue(Q)；/vi出队/for(j=0;jn;j+)/扩展结点/if(gij=1 and visitedj=0)print(visit vertex，j)；visitedj=1；EnQueue(Q，j)；/访问过的vj人队/,522 广度优先搜索的应用,【例1】已知若干个城市的地图，求从一个城市到另一个城市的路径，要求路径中经过的城市最少【例2】走迷宫问题,上一页 下一页 返回首页,【例1】已知若干个城市的地图，求从一个城市到另一个城市的路径，要求路径中经过的城市最少。算法设计：,上一页 下一页 返回首页 例2 例3,图的广度优先搜索类似与树的层次遍历，逐层搜索正好可以尽快找到一个结点与另一个结点相对而言最直接的路径。,如图5-6表示的是从城市A到城市H的交通图。从图中可以看出，从城市A到城市H要经过若干个城市。现要找出一条经过城市最少一条路线。,上一页 下一页 返回首页 例2 例3,图5-6,表5-1 图5-6的邻接距阵,具体过程如下：,1）将城市A（编号1）入队，队首qh置为0、队尾qe置为1。2）将队首所指的城市所有可直通的城市入队(如果这个城市在队中出现过就不入队),然后将队首加1，得到新的队首城市。重复以上步骤，直到城市H入队为止。当搜到城市H时，搜索结束。3）输出最少城市线路。,上一页 下一页 返回首页 例2 例3,数据结构设计：,1）线性数组a作为活结点队的存储空间。2）队列的每个结点有两个成员：ai.city记录入队的城市，ai.pre记录该城市的前趋城市在队列中的下标，这样通过ai.pre就可以倒推出最短线路。3）设置数组visited记录已搜索过的城市。,上一页 下一页 返回首页 例2 例3,算法如下：,search()qh=0;qe=1;sq1.city=1;sq1.pre=0;visited1=1;while(qhqe)/当队不空/qh=qh+1;/结点出队/for(i=1;i=n,i+)/扩展结点/if（jzsqqh.cityi=1 and visitedi=0）qe=qe+1;/结点入队/sqqe.city=i;sqqe.pre=qh;visitedqe=1;if(sqqe.city=8)out();print(“No avaliable way.”);,上一页 下一页 返回首页 例2 例3,算法分析：时间复杂度是O（n）；空间复杂性为（n2），包括图本身的存储空间和搜索时辅助空间“队”的存储空间。,out();/输出路径/print(sqqe.city);while(sqqe.pre0)qe=sqqe.pre;print(-,sqqe.city);,【例2】走迷宫问题,上一页 下一页 返回首页 例1 例3,迷宫是许多小方格构成的矩形，在每个小方格中有的是墙（图中的“1”）有的是路（图中的“0”）。走迷宫就是从一个小方格沿上、下、左、右四个方向到邻近的方格，当然不能穿墙。设迷宫的入口是在左上角(1,1)，出口是右下角(8,8)。根据给定的迷宫，找出一条从入口到出口的路径。,算法设计：,上一页 下一页 返回首页 例1 例3,从入口开始广度优先搜索可到达的方格入队，再扩展 队首的方格，直到搜索到出口时算法结束。对于迷宫中任意一点A（Y，X），有四个搜索方向：向上A（Y-1，X）向下A（Y+1，X）向左A（Y，X-1）向右A（Y，X+1）当对应方格可行（值为0），就扩展为活结点。,数据结构设计：,上一页 下一页 返回首页 例1 例3,用数组做队的存储空间，队中结点有三个成员：行号、列号、前一个方格在队列中的下标。搜索过的方格不另外开辟空间记录其访问的情况，而是用迷宫原有的存储空间置元素值为“-1”时，标识已经访问过该方格。为了构造循环体，用数组fx=1,-1,0,0、fy=0,0,-1,1 模拟上下左右搜索时的下标的变化过程。,int jz88=1,0,0,0,1,0,1,1,0,1,1,1,1,0,1,1,0,1,1,0,0,1,1,1,0,1,0,1,1,1,0,1,1,1,0,1,1,1,0,0,0,0,1,1,1,1,1,0,1,1,1,0,0,1,1,0,1,1,1,1,0,0,0,1;struct intcity,pre;sq100;int qh,qe,i,visited100;main()int i,n=8;for(i=1;i=n,i=i+1)visitedi=0;search();,search()qh=0;qe=1;sq1.city=1;sq1.pre=0;visited1=1;while(qhqe)/当队不空/qh=qh+1;/结点出队/for(i=1;i=n,i=i+1)/扩展结点/if（jzsqqh.cityi=1 and visitedi=0）qe=qe+1;/结点入队/sqqe.city=i;sqqe.pre=qh;visitedqe=1;if(sqqe.city=8)out();print(“No avaliable way.”);,out();/输出路径/print(sqqe.city);while(sqqe.pre0)qe=sqqe.pre;print(-,sqqe.city);算法分析：算法的时间复杂度并不复杂是O（n），算法的空间复杂性为O（n2），包括图本身的存储空间和搜索时辅助空间“队”的存储空间。,上一页 下一页 返回首页 例1 例3,深度优先遍历首先访问出发点v，并将其标记为已访问过；然后依次从v出发搜索v的每个邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点均已被访问为止。若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。,5.3 深度优先搜索,深度搜索与广度搜索的相近，最终都要扩展一个结点的所有子结点.区别在于对扩展结点过程，深度搜索扩展的是E-结点的邻接结点中的一个，并将其作为新的E-结点继续扩展，当前E-结点仍为活结点，待搜索完其子结点后，回溯到该结点扩展它的其它未搜索的邻接结点。而广度搜索，则是扩展E-结点的所有邻接结点，E-结点就成为一个死结点。,531 算法框架,1算法的基本思路 2算法框架,1算法的基本思路 算法设计的基本步骤为：1）确定图的存储方式；2）遍历过程中的操作，其中包括为输出问题解而进行的存储操作；3）输出问题的结论。4）一般在回溯前的应该将结点状态恢复为原始状态，特别是在有多解需求的问题中。,2算法框架 1）用邻接表存储图的搜索算法 2）用邻接矩阵存储图的搜索算法,graph head100；dfs(int k)/head图的顶点数组/edgenode*ptr/ptr图的边表指针/visitedk=1;/*记录已遍历过*/print(“访问”,k);/*印出遍历顶点值*/ptr=headk.firstedge;/*顶点的第一个邻接点*/while(ptr NULL)/*遍历至链表尾*/if(visitedptr-vertex=0)/*如过没遍历过*/dfs(ptr-vertex);/*递归遍历*/ptr=ptr-nextnode;/*下一个顶点*/算法分析：n图中有 n 个顶点，e 条边。扫描边的时间为O(e)。遍历图的时间复杂性为O(n+e)。返回,graph g100100,int n；dfsm(int k)int j；print(“访问”,k);visitedk=1；for(j=1；j=n；j+)/依次搜索vk的邻接点 if(gkj=1 and visitedj=0)dfsm(g,j)/(vk，vj)E，且vj未访问过，故vj为新出发点 算法分析：查找每一个顶点的所有的边，所需时间为O(n)，遍历图中所有的顶点所需的时间为O(n2)。返回,532 深度优先搜索的应用,【例1】走迷宫问题：问题同522【例2】1、算法设计：深度优先搜索，就是一直向着可通行的下一个方格行进，直到搜索到出口就找到一个解。若行不通时，则返回上一个方格，继续搜索其它方向。,2、数据结构设计：我们还是用迷宫本身的存储空间除了记录走过的信息，还要标识是否可行：mazeij=3 标识走过的方格；mazeij=2 标识走入死胡同的方格，这样，最后存储为“3”的方格为可行的方格。而当一个方格四个方向都搜索完还没有走到出口，说明该方格或无路可走或只能走入了“死胡同”。,3、算法int maze88=0,0,0,0,0,0,0,0,0,11,1,1,0,1,0,0,0,0,0,1,0,1,0,0,1,0,0,0,0,1,0,0,1,0,1,1,0,1,0,0,1,0,0,0,0,1,1,0,1,0,0,1,0,0,0,0,1,1,1,1,1,1,0;fx4=1,-1,0,0,fy4=0,0,-1,1;int i,j,k,total;main()int total=0;maze11=3;/入口坐标设置已走标志/search(1,1);print(“Total is”,total);/统计总步数/,search(int i,int j)int k,newi,newj;for(k=1;k=4;k+)/搜索可达的方格/if(check(i,j,k)=1)newi=i+fxk;newj=j+fyk;mazenewinewj=3;/来到新位置后,设置已走过标志/if(newi=8 and newj=8)/到出口则输出,否则下一步递归/Out();else search(newi,newj);mazeij=2;/某一方格只能走入死胡同/,Out()int i,j;for(i=1;i=8;i+)print(“换行符”);for(j=1;j=8;j+)if（mazeij=3）print(“V”);total+;/统计总步数/else print(“*”);,check(int i,int j,int k)int flag=1;i=i+fxk;j=j+fyk;if(i8 or j8)/是否在迷宫内/flag=0;else if(mazeij0)/是否可行/flag=0;return(flag);,4、算法说明：1）和广度优先算法一样每个方格有四个方向可以进行搜索，这样一点结点（方格）就可多次成为“活结点”，而在广度优先算法一点结点（方格）就可一次成为“活结点”，一出队就成了死结点。2）用广度优先算法，搜索出的是一条最短的路径，而用深度优先搜索则只能找出一条可行的路径，而不能保证是最短的路径。3）在空间效率上二者相近。都需要辅助空间。,【例2】有如图1所示的七巧板，试编写一源程序如下，使用至多四种不同颜色对七巧板进行涂色(每块涂一种颜色)，要求相邻区域的颜色互不相同，打印输出所有可能的涂色方案。,1、问题分析:为了让算法能识别不同区域间的相邻关 系，我们把七巧板上每一个区域看成一个顶点若两个区域相邻，则相应的顶点间用一条边相连，这样该问题就转化为图一个图的搜索问题了。,2、算法设计:按顺序分别对号、号、.、号区域进行试探性涂色，用、号代表种颜色。则涂色过程如下：1）对某一区域涂上与其相邻区域不同的颜色。2）若使用种颜色进行涂色均不能满足要求，则回溯一步，更改前一区域的颜色。3）转步骤继续涂色，直到全部区域全部涂色为止，输出结果。已经有研究证明，对任意的平面图至少存在一种四色涂色法。,3、数据采用的存储结构：邻接矩阵存储 0 1 0 0 1 0 1 1 0 0 1 0 1 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 0 0 0 0 0 1 0 1 1 1 0 0 0 1 0 1 1 1 0 0,4、算法如下:int data77,n,color7,total;main()int i,j;for(i=1;i=n;i+)for(j=1;j=n;j+)input(dataij);for(j=1;j=n;j+)colorj=0;total=0;try(1);print(换行符,Total=,total);,try(int s)int i,;if(s7)output();else for(i=1;i=4;i+)colors=i;if（colorsame(s)=0）try(s+1);,output()int i,;print(换行符，serial number：,total);for i:=1 to n do print(colori);total=total+1;,colorsame(int s)/判断相邻点是否同色/int i,flag;flag=0;for(i=1;i=s-1;i+)if(datais=1 and colori=colors)flag=1;return(flag),【例3】关结点的判断及消除 1网络安全相关的概念 在一个无向连通图G中，当且仅当删去G中的顶点v及所有依附于v的所有边后，可将图分割成两个以上的连通分量，则称v为图G的关结点，关结点亦称为割点。,图5-6 图5-7 连通图 连通图(含有关结点2、3、5)(不含关结点),图5-8 图5-6删去关结点2的结果,一个表示通信网络的图的连通度越高，其系统越可靠。网络安全比较低级的要求就是重连通图。在重连通图上，任何一对顶点之间至少存在有两条路径，在删除某个顶点及与该顶点相关联的边时，也不破坏图的连通性。即“如果无向连通图G根本不包含关结点，则称G为重连通图”。不是所有的无向连通图都是重连通图。,2连通图G的关结点的判别 算法设计：连通图中关结点的判别方法如下：1)从图的某一个顶点开始深度优先遍历图，得到深度优先生成树 2)用开始遍历的顶点作为生成树地根，一、根 顶点是图的关结点的充要条件是，根至少有两个子 女。二、其余顶点u是图的关结点的充要条件是，该顶点u至少有一个子女w，从该子女出发不可能通 过该子女顶点w和该子女w的子孙顶点，以及一条回 边所组成的路径到达u的祖先，不具有可行性。三、特别的，叶结点不是关结点。,例：图中，每个结点的外面都有一个数，它表示按深度优先检索算法访问这个结点的次序，这个数叫做该结点的深度优先数（DFN）。例如：DFN(1)=1，DFN(4)=2，DFN(8)=10等等。,图5-9 图5-6所示的深度优先生成树,图5-9(b)中的实线边构成这个深度优先生成树，这些边是递归遍历顶点的路径，叫做树边,虚线边为回边。,定义：L(u)=Min DFNu,loww,DFNk w是u在DFS生成树上的孩子结点;k是u在DFS生成树上由回边联结的祖先节点；(u,w)实边;(u,k)虚边,显然，L(u)是u通过一条子孙路径且至多后随一条逆边所可能到达的最低深度优先数。如果u不是根，那么当且仅当u有一个使得L(w)=DFN(u)的儿子w时，u是一个关结点。,对于图5-8（b）所示的生成树，各结点的最低深度优先数是：L(1:10)=(1,1,1,1,6,8,6,6,5,4)。由此，结点3是关结点，因为它的儿子结点10有L(10)=4DFN(3)=3。同理，结点2、5也是关结点。,按后根次序访问深度优先生成树的结点，可以很容易地算出L（U）。于是，为了确定图G的关结点,必须既完成对G的深度优先检索，产生G的深度优先生成树T，又要按后根次序访问树T的结点。,算法ART计算DFN和L的算法如下：int DFNn，Ln，num，n ART（u，v）/u是深度优先检索的开始结点。在深度优先生成树中，u若有父亲，那末v就是它的父亲。假设数组DFN是全程量，并将其初始化为0。num是全程变量，被初始化为 1。n是 G的结点数,算法如下：int DFNn，Ln，num=1，n；TRY（u，v）DFNu=num；Lu=num；num=num1；while（每个邻接于u的结点 w）if（DFN（w）=0）TRY（w，u）；if(L（u）L（w）L（u）=L（w）；else if（wv）if(L（u）DFN（w）)L（u）=DFN（w）；,算法说明：算法ART实现了对图G的深度优先检索；在检索期间，对每个新访问的结点赋予深度优先数；同时对这棵树中每个结点的L（i）值也进行计算。如果连通图G有n个结点e条边，且G由邻接表表示，那末ART的计算时间为O（ne）。识别关结点的总时间不超过O（ne）。,3非重连通图的加边策略 G=(V,E)是G的最大重连通子图，指的是G中再没有这样的重连通子图G=(V,E)存在，使得VV且EE。最大重连通子图称为重连通分图,图5-10 图5-6所示的重连通分图,两个重连通分图至多有一个公共结点，且这个结点就是割点。因而可以推出任何一条边不可能同时出现在两个不同的重连通分图中（因为这需要两个公共结点）。选取两个重连通分图中不同的结点连结为边，则生成的新图为重连通的。多个重连通分图的情况依此类推。,使用这个方法将图5-6变成重连通图，需要对应于关结点3增加边（4，10）和（10，9）；对应关结点2增加边（1，5）；对应关结点5增加（6，7），结果如图5-11。,图5-11(图5-6改进为重连通图）,54 回 溯 法,回溯算法实际是一个类似枚举的搜索尝试方法，它的主题思想是在搜索尝试中找问题的解，当不满足求解条件就”回溯”返回，尝试别的路径。回溯算法是尝试搜索算法中最为基本的一种算法，其采用了一种“走不通就掉头”的思想，作为其控制结构。,541 认识回溯法【例1】八皇后问题模型建立 要在8*8的国际象棋棋盘中放八个皇后，使任意两个皇后都不能互相吃掉。规则：皇后能吃掉同一行、同一列、同一对角线的任意棋子。如图5-12为一种方案，求所有的解。,模型建立 不妨设八个皇后为xi，她们分别在第i行（i=1，2，3，4，8），这样问题的解空间，就是一个八个皇后所在列的序号，为n元一维向量（x1,x2,x3,x4,x5,x6,x7,x8）,搜索空间是1xi8（i=1，2，3，4，8），共88个状态。约束条件是八个（1,x1）,(2,x2),(3,x3),(4,x4),(5,x5),(6,x6),(7,x7),(8,x8)不在同一行、同一列和同一对角线上。,虽然问题共有88个状态，但算法不会真正地搜索这么多的状态，因为前面已经说明，回溯法采用的是“走不通就掉头”的策略，而形如(1,1,x3,x4,x5,x6,x7,x8）的状态共有86个，由于1，2号皇后在同一列不满足约束条件，回溯后这86个状态是不会搜索的。,算法设计1：加约束条件的枚举算法 最简单的算法就是通过八重循环模拟搜索空间中的88个状态，按深度优先思想，从第一个皇后从第一列开始搜索，每前进一步检查是否满足约束条件,不满足时，用continue语句回溯，满足满足约束条件，开始下一层循环，直到找出问题的解。,约束条件不在同一列的表达式为xi xj；而在同一主对角线上时xi-i=xj-j,在同一负对角线上时xi+i=xj+j，因此，不在同一对角线上的约束条件表示为abs(xi-xj)abs(i-j)（abs（）取绝对值）。,算法1：,queen1（）int a9;for(a1=1;a1=8;a1+)for(a2=1;a2=8;a2+)if（check(a,2)=0）continue;for(a3=1;a3=8;a3+)if（check(a,3)=0）continue;for(a4=1;a4=8;a4+)if（check(a,4)=0）continue;for(a5=1;a5=8;a5+)if（check(a,5)=0）continue;for(a6=1;a6=8;a6+)if（check(a,6)=0）continue;,for(a7=1;a7=8;a7+)if（check(a,7)=0）continue;for(a8=1;a8=8;a8+)if（check(a,8)=0）continue;else for(i=1;i=8;i+)print(ai);,check(int a,int n)int i;for(i=1;i=n-1;i+)if(abs(ai-an)=abs(i-n)or(ai=an)return(0);return(1);,算法分析1：若将算法中循环嵌套间的检查是否满足约束条件的:“if（check(a,i)=0）continue;i=2,3,4,5,6,7“语句都去掉，只保留最后一个检查语句：“if（check(a,8)=0）continue;”,相应地check（）函数修改成：check*(a,n)int i,j;for(i=2;i=n;i+)for(j=1;j=i-1;j+)if(abs(ai-aj)=abs(i-j)or(ai=aj)return(0);return(1);则算法退化成完全的盲目搜索，复杂性就是88了,算法设计2：非递归回溯算法 以上的枚举算法可读性很好，但它只能解决八皇后问题，而不能解决任意的n皇后问题。下面的非递归算法可以说是典型的回溯算法模型。,算法2：int a20,n;queen2（）input(n);bckdate（n）;,backdate(int n)int k;a1=0;k=1;while(k0)ak=ak+1;while(ak=n)and(check(k)=0)/搜索第k个皇后位置/ak=ak+1;if（ak=n）if(k=n)output(n);/找到一组解/else k=k+1;继续为第k+1个皇后找到位置/ak=0;/注意下一个皇后一定要从头开始搜索/else k=k-1;/回溯/,check(int k)int i;for(i=1;i=k-1;i+)if(abs(ai-ak)=abs(i-k)or(ai=ak)return(0);return(1);output()int i;for(i=1;i=n;i+)print(ai);,算法设计3：递归算法 这种方式也可以解决任意的n皇后问题。这里我们用第三章323“利用数组记录状态信息”的技巧，用三个数组c,b,d分别记录棋盘上的n个列、n个主对角线和n个负对角线的占用情况。,以四阶棋盘为例，如图5-13，共有2n-1=7个主对角线，对应地也有7个负对角线。,图5-13 四皇后棋盘示意图,用i，j分别表示皇后所在的行列，同一主对角线上的行列下标的差一样，若用表达式i-j编号，则范围为-n+1n-1，所以我们用表达式i-j+n对主对角线编号，范围就是12n-1。同样地，负对角线上行列下标的和一样，用表达式i+j编号，则范围为22n。,算法3：int a20,b20,c40,d40;int n,t，i,j,k;/t记录解的个数/queen3（）int i,input(n);for(i=1;i=n;i+)bi=0;ci=0;cn+i=0;di=0;dn+i=0;try（1）;,try(i:integer)int j;for(j=1;j=n;j+)/第i个皇后有n种可能位置/if(bj=0)and(ci+j=0)and(di-j+n=0)ai=j;/摆放皇后/bj=1;/占领第j列/ci+j=1;di-j+n=1;/占领两个对角线/if(i8)try(i+1);/n个皇后没有摆完，递归摆放下一皇后/else output();/完成任务，打印结果/bj=0;ci+j=0;di-j+n=0;/回溯/,output()t=t+1;print(t,);for(k=1;k=n;k+)print(ak,);print(“换行符”);,递归算法的回溯是由函数调用结束自动完成的，也不需要指出回溯点，但也需要“清理现场”将当前点占用的位置释放，也就是算法try（）中的后三个赋值语句。,542 算法简介算法框架,1回溯法基本思想 2算法设计过程 3算法框架,1回溯法基本思想 回溯法是在包含问题的所有解的解空间树中。按照深度优先的策略，从根结点出发搜索解空间树，算法搜索至解空间树的任一结点时，总是先判断该结点是否满足问题的约束条件。如果满足进入该子树，继续按深度优先的策略进行搜索。否则，不去搜索以该结点为根的子树，而是逐层向其祖先结点回溯。回溯法就是对隐式图的深度优先搜索算法。,如图5-14是四皇后问题的搜索过程,图5-14四皇后问题的解空间树,2算法设计过程 1）确定问题的解空间 问题的解空间应只至少包含问题的一个解。2）确定结点的扩展规则 如每个皇后在一行中的不同位置移动，而象棋中的马只能走“日”字等。,3）搜索解空间 回溯算法从开始结点出发，以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。此时，应往回移动至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已没有活结点时为止。,3算法框架 1）问题框架 设问题的解是一个n维向量(a1,a2,an)，约束条件是ai（i=1，2，3n）之间满足某种条件，记为f(ai),2）非递归回溯框架int an，i;初始化数组a；i=1;While(i0(有路可走)and(未达到目标)/还未回溯到头/if(in)/正在处理第i个元素/搜索到一个解，输出;else ai第一个可能的值；while(ai在不满足约束条件 且 在在搜索空间内)ai下一个可能的值；if(ai在搜索空间内)标识占用的资源;i=i+1;/扩展下一个结点/else 清理所占的状态空间；i=i-1;/回溯/,3）递归算法框架 一般情况下用递归函数来实现回溯法比较简单，其中i为搜索深度。int an;try(int i)if（in）输出结果;else for（j=下界;j=上界;j+）/枚举i所有可能的路径/if（f(j)）/满足限界函数和约束条件/ai=j;/其它操作/try(i+1);回溯前的清理工作(如ai置空值等)；,543 应用1 基本的回溯搜索,【例2】马的遍历问题 在nm的棋盘中，马只能走日字。马从位置(x,y)处出发，把棋盘的每一格都走一次，且只走一次。找出所有路径。,1、问题分析 马是在棋盘的点上行走的，所以这里的棋盘是指行有条边、列有条边。而一个马在不出边界的情况下有八个方向可以行走，如当前坐标为（x,y）则行走后的坐标可以为：(x+1,y+2),(x+1,y-2),(x+2,y+1),(x+2,y-1),(x-1,y-2),(x-1,y+2),(x-2,y-1),(x-2,y+1),2、算法设计 搜索空间是整个nm个棋盘上的点。约束条件是不出边界且每个点只经过一次。结点的扩展规则如问题分析中所述。搜索过程