图的搜索算法1

《图的搜索算法1》由会员分享，可在线阅读，更多相关《图的搜索算法1（167页珍藏版）》请在金锄头文库上搜索。

1、图的搜索算法1Stillwatersrundeep.流静水深流静水深,人静心深人静心深Wherethereislife,thereishope。有生命必有希望。有生命必有希望上一页 下一页 返回首页 图图是一种限止最少的数据结构，因此更接近现实，实是一种限止最少的数据结构，因此更接近现实，实际问题中很多数据关系都可以抽象成图，相关问题则可利际问题中很多数据关系都可以抽象成图，相关问题则可利用图的基本算法进行求解，很早就有专门研究图的是一门用图的基本算法进行求解，很早就有专门研究图的是一门数学学科数学学科“图论图论”；其中的计算问题包括图的搜索、路径；其中的计算问题包括图的搜索、路径问题、连通性

2、问题、可平面性检验、着色问题、网络优化问题、连通性问题、可平面性检验、着色问题、网络优化等。图论中的著名算法有：求最小生成树的等。图论中的著名算法有：求最小生成树的Kruskal算法、算法、求最短路径的求最短路径的Dijkstra算法和算法和Floyd算法、求二部图最算法、求二部图最大匹配（指派问题）的匈牙利算法、求一般图最大匹配的大匹配（指派问题）的匈牙利算法、求一般图最大匹配的Edmonds“花花”算法、求网络最大流和最小割的算法等。其算法、求网络最大流和最小割的算法等。其中的一些算法在数据结构课程中已经学习过了。中的一些算法在数据结构课程中已经学习过了。1显式图与显式图与隐式图隐式图 在

3、路径问题、连通性问题、可平面性检验、着色在路径问题、连通性问题、可平面性检验、着色问题和网络优化等问题中，图的结构是显式给出的，问题和网络优化等问题中，图的结构是显式给出的，包括图中的顶点、边及权重，这类图我们称为包括图中的顶点、边及权重，这类图我们称为显式图显式图，也就是一般意义上的也就是一般意义上的图图。 隐式图隐式图是由问题的初始结点，为了求解或求证是由问题的初始结点，为了求解或求证问题，根据题目的规则（一般是由题目的意思隐含问题，根据题目的规则（一般是由题目的意思隐含给出的），也就是生成子结点的约束条件，逐步扩给出的），也就是生成子结点的约束条件，逐步扩展结点，直到得到目标结点为止的一

4、个展结点，直到得到目标结点为止的一个隐式的图隐式的图。 5.1.1 5.1.1 图及其术语图及其术语2.显式图的常用术语 如图如图5-1所示的所示的，均为显式图均为显式图(Graph)。图中的这些点图中的这些点(v1,v2,(v1,v2,vn),vn)被称为被称为顶点顶点(vertex)或或结点结点，连接顶点的曲线或直线称为连接顶点的曲线或直线称为边边(edge)。 通常将这种由若干个顶点以及连接某些顶点的边所组通常将这种由若干个顶点以及连接某些顶点的边所组成的图形称为成的图形称为图图，顶点通常被称作是图中的，顶点通常被称作是图中的数据元素数据元素.上一页 下一页 返回首页图图5-1图图5-2

5、图带权图带权图：j即图即图5-2给图给图5-1中各图的边上附加一个代表性数中各图的边上附加一个代表性数据据(比如表示长度、流量或其他比如表示长度、流量或其他)，则称其为带权图，则称其为带权图。环环(cycle)：图：图5-1中中图中的图中的v1点本身也有边相连，这点本身也有边相连，这种边称为环。种边称为环。有限图有限图：顶点与边数均为有限的图，如图：顶点与边数均为有限的图，如图5-1中的三个图均中的三个图均属于有限图。属于有限图。简单图简单图：没有环且每两个顶点间最多只有一条边相连的图，：没有环且每两个顶点间最多只有一条边相连的图，如图如图5-1中的中的图。图。邻接与关联邻接与关联：当（：当（

6、v1，v2）E，或，或E，即，即v1，v2间有边相连时，则称间有边相连时，则称v1和和v2是相邻的，是相邻的，它们互为邻接点（它们互为邻接点（adjacent），同时称（），同时称（v1，v2）或）或是与顶点是与顶点v1、v2相关联的边。相关联的边。上一页 下一页 返回首页顶点的度数顶点的度数(degree)：从该顶点引出的边的条数，即与该顶点：从该顶点引出的边的条数，即与该顶点相关联的边的数目，简称度。相关联的边的数目，简称度。入度（入度（indegree）：有向图中把以顶点：有向图中把以顶点v为终点的边的条数称为终点的边的条数称为是顶点为是顶点v的入度。的入度。出度（出度（outdegre

7、e）：有向图中把以顶点：有向图中把以顶点v为起点的边的条数称为起点的边的条数称为是顶点为是顶点v的出度。的出度。终端顶点终端顶点：有向图中把出度为：有向图中把出度为0的顶点称为终端顶点，如图的顶点称为终端顶点，如图5-1中中图的图的v3。路径与路长：路径与路长：在图在图G=(V，E)中，如果存在由不同的边中，如果存在由不同的边(vi0，vi1)，(vi1，vi2)，(vin-1，vin)或是或是，)组成的序列，组成的序列，则称顶点则称顶点vi0，vin是连通的，顶点序列（是连通的，顶点序列（vi0，vi1，vi2，vin）是从顶点）是从顶点vi0到顶点到顶点vin的一条道路。路长是道的一条道路

8、。路长是道路上边的数目，路上边的数目，vi0到到vin的这条道路上的路长为的这条道路上的路长为n。连通图：连通图：对于图中任意两个顶点对于图中任意两个顶点vi、vjV，vi、vj之间有之间有道路相连，则称该图为连通图。如道路相连，则称该图为连通图。如5-1中的中的图。图。网络：网络：带权的连通图，如图带权的连通图，如图5-2所示。所示。3 3隐式图术语隐式图术语 1 1）子集树子集树 当要求解的问题需要是在当要求解的问题需要是在n n 个元素的子集中进行搜索，其个元素的子集中进行搜索，其搜索空间树被称作搜索空间树被称作子集树（子集树（subset treesubset tree）。这。这n n

9、个元素都有个元素都有在子集中或被选取记为在子集中或被选取记为1 1，不在子集中或被舍去记为，不在子集中或被舍去记为0 0，这样，这样搜索空间为：搜索空间为： （0 0，0 0，0 0，0 0），（），（0 0，0 0，0 0，1 1），）， （0 0，0 0，1 1，0 0），（），（0 0，0 0，1 1，1 1），）， （1 1，1 1，1 1，1 1）。）。共共2 2n n 个状态。若表示为个状态。若表示为树形结构树形结构就是一棵有就是一棵有2 2n n个叶结点的二个叶结点的二叉树，对树中所有分支进行遍历的算法都必须耗时叉树，对树中所有分支进行遍历的算法都必须耗时O（2n）。上一页上一页

10、 下一页下一页 返回返回首页首页图图5-3n=3的子集树的子集树上一页 下一页 返回首页2）排列树）排列树 上上一一页页 下下一一页页 返返回回首页首页 当当要要求求解解的的问问题题需需要要在在n n 元元素素的的排排列列中中搜搜索索问问题题的的解解时，解空间树被称作时，解空间树被称作排列树（排列树（permutation treepermutation tree）。搜索空间为：搜索空间为：（1 1，2 2，3 3，n-1n-1，n n）, , （2 2，1 1，3 3，n-1n-1，n n）, , （2 2，3 3，1 1，n-1n-1，n n）, ,（2 2，3 3，4 4，1 1，n-n

11、-1 1，n n）, ,（n n，n-1n-1，3 3，2 2，1 1） 第一个元素有第一个元素有n种选择，第二个元素有种选择，第二个元素有n-1种选择，第种选择，第三个元素有三个元素有n-2种选择，种选择，第，第n个元素有个元素有1种选择，共计种选择，共计n!个状态。若表示为树形就是一个个状态。若表示为树形就是一个n度树，这样的树有度树，这样的树有n!个叶结点，所以每一个遍历树中所有节点的算法都必须耗个叶结点，所以每一个遍历树中所有节点的算法都必须耗时时O(n!)上一页 下一页 返回首页图图5-3n=4的部分子集树的部分子集树4 4图的存储图的存储 1 1）邻接矩阵法邻接矩阵法 上上一一页页

12、 下下一一页页 返返回回首页首页 邻接矩阵邻接矩阵是表示顶点之间相邻关系的矩阵，是表示顶点之间相邻关系的矩阵，设设G=(V,E)G=(V,E)是具有是具有n n个顶点的个顶点的图图，则，则G G的邻接矩阵可定义为：的邻接矩阵可定义为： Ai,j=1, Ai,j=1, 若（若（Vi,Vj)Vi,Vj)或或是是E(G)E(G)中的边。中的边。 Ai,j=0, Ai,j=0, 若若 (Vi,Vj) (Vi,Vj)或或不是不是E(G)E(G)中的边。中的边。若若G G是是网络网络，则邻接矩阵可定义为：，则邻接矩阵可定义为： Ai,j=WAi,j=Wijij 若（若（Vi,Vj)Vi,Vj)或或属于属于

13、E(G);E(G);Ai,j=0或或若（若（Vi,Vj）或）或不属于不属于E(G); 其其中中，Wij表表示示边边上上的的权权值值，表表示示一一个个计计算算机机允允许许的的，大大于于所有边上权值的数；所有边上权值的数； 上上一一页页 下下一一页页 返返回回首页首页2 2）邻接表）邻接表 上上一一页页 下下一一页页 返返回回首首页页 例例1 1 对于图对于图G G中的每个结点中的每个结点Vi, Vi, 把所有邻接于把所有邻接于ViVi的顶点的顶点VjVj链成一个链成一个单链表，这个单链表就称为顶点单链表，这个单链表就称为顶点ViVi的邻接表。的邻接表。 邻接表由边表和顶点两部分组成。邻接表由边表

14、和顶点两部分组成。 边表边表为一个为一个单链表单链表，每个表结点均有两个域：，每个表结点均有两个域： 邻邻接接点点域域adjvexadjvex，存存放放与与vivi相相邻邻接接的的顶顶点点v vj j的的序序号号j j。 链链 域域 nextnext， 将将 邻邻 接接 表表 的的 所所 有有 表表 结结 点点 链链 在在 一一 起起 。 顶顶 点点 表表 为为 一一 数数 组组 ， 每每 个个 元元 素素 均均 有有 两两 个个 域域 ： 顶顶点点域域vertexvertex，存存放放顶顶点点v vi i的的信信息息 指针域指针域firstedgefirstedge， v vi i的边表的头

15、指针。的边表的头指针。 对于无向图来说，对于无向图来说，ViVi的邻接表中每个表结点都对应于与的邻接表中每个表结点都对应于与ViVi相关联的一条边，相关联的一条边， 对于有向图来说，对于有向图来说，ViVi的邻接表中每个表结点对应于的邻接表中每个表结点对应于ViVi为始点为始点射出的一条边。射出的一条边。 图7.1 上上一一页页 下下一一页页 返返回回首首页页图图5-5图图5-1中（中（1）图的邻接表）图的邻接表 5.1.2 图搜索及其术语1 1穷举搜索与穷举搜索与启发式搜索启发式搜索 穷举搜索穷举搜索是对图的最基本的搜索算法，是蛮力策略的一种是对图的最基本的搜索算法，是蛮力策略的一种表现形式

16、。即不考虑给定问题的特有性质，按事先定好的顺序，表现形式。即不考虑给定问题的特有性质，按事先定好的顺序，依次运用规则，盲目搜索的方法。依次运用规则，盲目搜索的方法。 启发式搜索启发式搜索是利用一些是利用一些启发信息启发信息，提前判断出先搜索哪些，提前判断出先搜索哪些状态可能尽快找到问题的解或某些情况不可能取到最优解，从状态可能尽快找到问题的解或某些情况不可能取到最优解，从而可以提前舍弃对这些状态的尝试。即考虑给定问题的特有性而可以提前舍弃对这些状态的尝试。即考虑给定问题的特有性质，选用合适的细则，提高搜索的效率。质，选用合适的细则，提高搜索的效率。 上一页 下一页 返回首页2相关概念和术语 上

17、上一一页页 下下一一页页 返返回回首页首页 问题状态问题状态: :树中的每一个结点确定所求解问题的一个问题状态。树中的每一个结点确定所求解问题的一个问题状态。状态空间状态空间: :由根结点到其它结点的所有路径（分支），就确定由根结点到其它结点的所有路径（分支），就确定 了这个问题的状态空间。了这个问题的状态空间。解状态解状态: :是这样一些问题状态是这样一些问题状态S，对于这些问题状态，由根到，对于这些问题状态，由根到S的那条路径确定了这解空间中的一个元组。的那条路径确定了这解空间中的一个元组。 答案状态答案状态: :是这样的一些解状态是这样的一些解状态S，对于这些解状态而言，由，对于这些解状

18、态而言，由 根到根到S的这条路径确定了这问题的一个解的这条路径确定了这问题的一个解状态空间树状态空间树: :解空间的树结构又称隐式图。解空间的树结构又称隐式图。活结点活结点：如果已生成一个结点而它的所有儿子结点还没有：如果已生成一个结点而它的所有儿子结点还没有全部生成，则这个结点叫做活结点。全部生成，则这个结点叫做活结点。 E-结点结点：当前正在生成其儿子结点的活结点叫：当前正在生成其儿子结点的活结点叫E-结点（正结点（正 扩展的结点）。扩展的结点）。死结点死结点：不再进一步扩展或者其儿子结点已全部生成的生：不再进一步扩展或者其儿子结点已全部生成的生成结点就是死结点成结点就是死结点。5.2.1

19、 算法框架 1算法的基本思路算法的基本思路算法设计的基本步骤为：算法设计的基本步骤为： 1）确定图的存储方式；确定图的存储方式；2）图的遍历过程中的操作，其中包括为输出问题解图的遍历过程中的操作，其中包括为输出问题解而进行的存储操作；而进行的存储操作； 3 3）输出问题的结论。输出问题的结论。 上一页 下一页 返回首页5.2 广度优先搜索 2 2算法框架算法框架 上上一一页页 下下一一页页 返返回回首首页页 例例1 1从从广度优先搜索定义可以看出活结点的扩展是按先来先处广度优先搜索定义可以看出活结点的扩展是按先来先处理的原则进行的，所以在算法中要用理的原则进行的，所以在算法中要用“队队”来存储

20、每个来存储每个E-E-结点结点扩展出的活结点。为了算法的简洁，抽象地定义：扩展出的活结点。为了算法的简洁，抽象地定义：queuequeue为队列类型，为队列类型，InitQueue( ) InitQueue( ) 为队列初始化函数，为队列初始化函数， EnQueue(QEnQueue(Q，k)k)为入队函数，为入队函数，QueueEmpty(Q) QueueEmpty(Q) 为判断队空函数，为判断队空函数，DeQueue(Q) DeQueue(Q) 为出队函数。为出队函数。 实际应用中，用数组或链表实现队列。实际应用中，用数组或链表实现队列。 开辟开辟数组数组visitedvisited记录记

21、录visitedvisited结点的搜索情况。结点的搜索情况。 在算法框架中以输出结点值表示在算法框架中以输出结点值表示“访问访问”。1 1）邻接表表示图的广度优先搜索算法）邻接表表示图的广度优先搜索算法 intvisitedn; /n visitedn; /n 为结点个数为结点个数/ /bfs(intk,graphhead)inti；queueQ；edgenode*p； /定义队列定义队列/InitQueue(Q)；/队列初始化队列初始化/print(“visitvertex”，k)；/访问源点访问源点vk/visitedk=1；EnQueue(Q，k)；/vk已访问，将其入队。已访问，将其

22、入队。/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）邻接矩阵表示的图的广度优先搜索算法

23、）邻接矩阵表示的图的广度优先搜索算法上上一一页页 下下一一页页 返返回回首页首页bfsm(intk,graphg100，intn)inti，j；CirQueueQ；InitQueue(Q)；print(visitvertex，k)；/访问源点访问源点vk/visitedk=1；EnQueue(Q，k)；while(notQueueEmpty(Q)i=DeQueue(Q)；/vi出队出队/for(j=0;jn;j+)/扩展结点扩展结点/if(gij=1andvisitedj=0)print(visitvertex，j)；visitedj=1；EnQueue(Q，j)；/访问过的访问过的vj人队人

24、队/ 5.2.2 广度优先搜索的应用 【例1】已知若干个城市的地图，求从一个城市到另一个城市的路径，要求路径中经过的城市最少 【例2】走迷宫问题 上一页 下一页 返回首页【例1】已知若干个城市的地图，求从一个城市到另一个城市的路径，要求路径中经过的城市最少。 算法设计：上一页 下一页 返回首页 例2 例3 图的广度优先搜索类似与树的层次遍图的广度优先搜索类似与树的层次遍历，逐层搜索正好可以尽快找到一个结点历，逐层搜索正好可以尽快找到一个结点与另一个结点相对而言最直接的路径。与另一个结点相对而言最直接的路径。 如图如图5-6表示的是从城市表示的是从城市A到城市到城市H的交通的交通图。从图中可以看

25、出，从城市图。从图中可以看出，从城市A到城市到城市H要经要经过若干个城市。现要找出一条经过城市最少过若干个城市。现要找出一条经过城市最少一条路线。一条路线。 上一页上一页 下一页下一页 返回首页返回首页 例例2 2 例例3 3图5-6 表5-1 图5-6的邻接距阵 具体过程如下： 1 1）将城市将城市A A（编号（编号1 1）入队，队首）入队，队首qhqh置为置为0 0、队尾、队尾qeqe置为置为1 1。2 2）将队首所指的城市所有可直通的城将队首所指的城市所有可直通的城市入队市入队( (如果这个城市在队中出现过就不如果这个城市在队中出现过就不入队入队),),然后将队首加然后将队首加1 1，得

26、到新的队首城，得到新的队首城市。重复以上步骤，直到城市市。重复以上步骤，直到城市H H入队为止。入队为止。当搜到城市当搜到城市H H时，搜索结束。时，搜索结束。3）输出最少城市线路输出最少城市线路。 上一页 下一页 返回首页 例2 例3数据结构设计： 1 1）线性线性数组数组a作为活结点队的存储空间。作为活结点队的存储空间。2 2）队队列列的的每每个个结结点点有有两两个个成成员员：ai.city记记录录入入队队的的城城市市，ai.pre记记录录该该城城市市的的前前趋趋城城市市在在队队列列中中的的下下标标，这这样样通通过过ai.pre就就可可以以倒推出最短线路。倒推出最短线路。3 3）设置数组设

27、置数组visited记录已搜索过的城市。记录已搜索过的城市。上一页 下一页 返回首页 例2 例3算法如下：search( )( )qh=0; qe=1;sq1.city=1;sq1.pre=0;visited1=1;qh=0; qe=1;sq1.city=1;sq1.pre=0;visited1=1; while( qhqe) / while( qhqe) /当队不空当队不空/ /qh=qh+1; /qh=qh+1; /结点出队结点出队/ / for(i=1;i=n,i+) /for(i=1;i=n,i+) /扩展结点扩展结点/ / if if （jzsqqh.cityi=1 and visi

28、tedi=0jzsqqh.cityi=1 and visitedi=0） qe=qe+1; / qe=qe+1; /结点入队结点入队/ /sqqe.city=i;sqqe.pre=qh;visitedqe=1;sqqe.city=i;sqqe.pre=qh;visitedqe=1;if (sqqe.city=8) out( );if (sqqe.city=8) out( ); print(“No avaliable way.”);print(“No avaliable way.”); 上一页 下一页 返回首页 例2 例3算法分析算法分析：时间复杂度是：时间复杂度是O（n）；空间复杂性为（）；空

29、间复杂性为（n2），），包括图本身的存储空间和搜索时辅助空间包括图本身的存储空间和搜索时辅助空间“队队”的存储空的存储空间。间。out( ); /out( ); /输出路径输出路径/ /print(sqqe.city);print(sqqe.city); while(sqqe.pre0) while(sqqe.pre0) qe=sqqe.pre; print(-,sqqe.city); 【例2】走迷宫问题 上一页 下一页 返回首页 例1 例3 迷宫是许多小方格构成的矩形，在每个小方格中有的是墙（图中的迷宫是许多小方格构成的矩形，在每个小方格中有的是墙（图中的“1”“1”）有的是路（图中的）有的

30、是路（图中的“0”“0”）。走迷宫就是从一个小方格沿上、下、左、）。走迷宫就是从一个小方格沿上、下、左、右四个方向到邻近的方格，当然不能穿墙。设迷宫的入口是在左上角右四个方向到邻近的方格，当然不能穿墙。设迷宫的入口是在左上角(1,1)(1,1)，出口是右下角，出口是右下角(8,8)(8,8)。根据给定的迷宫，找出一条从入口到出口的路径。根据给定的迷宫，找出一条从入口到出口的路径。 算法设计：上一页 下一页 返回首页 例1 例3 从入口开始广度优先搜索可到达的方格入队，再扩展从入口开始广度优先搜索可到达的方格入队，再扩展 队队首的方格，直到搜索到出口时算法结束。首的方格，直到搜索到出口时算法结束

31、。 对于迷宫中任意一点对于迷宫中任意一点A（Y，X），有四个搜索方向：），有四个搜索方向： 向上向上A（Y-1，X） 向下向下A（Y+1，X） 向左向左A（Y，X-1） 向右向右A（Y，X+1） 当对应方格可行（值为当对应方格可行（值为0），就扩展为活结点。），就扩展为活结点。 数据结构设计：数据结构设计： 上一页 下一页 返回首页 例1 例3 用用数数组组做做队队的的存存储储空空间间，队队中中结结点点有有三三个个成成员员：行行号号、列列号号、前前一一个个方方格格在在队队列列中中的的下下标标。搜搜索索过过的的方方格格不不另另外外开开辟辟空空间间记记录录其其访访问问的的情情况况，而而是是用用迷迷

32、宫宫原原有有的的存存储储空空间间置置元素值为元素值为“-1”“-1”时，标识已经访问过该方格。时，标识已经访问过该方格。 为了构造循环体，用数组为了构造循环体，用数组fx=1,-1,0,0fx=1,-1,0,0、fy=fy= 0,0,-1,1 0,0,-1,1 模拟上下左右搜索时的下标的模拟上下左右搜索时的下标的变化过程。变化过程。 intjz88=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,

33、0,1;structintcity,pre;sq100;intqh,qe,i,visited100;main()inti,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=1andvisitedi=0）qe=qe+1;/结点入点入队/sqqe.city=i;sqqe.pre=qh;visitedqe=1;if

34、(sqqe.city=8)out();print(“Noavaliableway.”);out();/输出路径出路径/print(sqqe.city);while(sqqe.pre0)qe=sqqe.pre;print(-,sqqe.city);算法分析算法分析： 算法算法的时间复杂度并不复杂是的时间复杂度并不复杂是O O（n n），算法的空间复杂性），算法的空间复杂性为为O O（n n2 2），包括图本身的存储空间和搜索时辅助空间），包括图本身的存储空间和搜索时辅助空间“队队”的的存储空间。存储空间。 上一页 下一页 返回首页 例1 例3深度优先遍历深度优先遍历首先访问出发点首先访问出发点v

35、 v，并将其标记为，并将其标记为已访问过；然后依次从已访问过；然后依次从v v出发搜索出发搜索v v的每个邻接点的每个邻接点w w。若若w w未曾访问过，则以未曾访问过，则以w w为新的出发点继续进行深度为新的出发点继续进行深度优先遍历，直至图中所有和源点优先遍历，直至图中所有和源点v v有路径相通的顶点有路径相通的顶点均已被访问为止。均已被访问为止。 若此时图中仍有未访问的顶点，则另选一个尚若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。中所有顶点均已被访问为止。5.3深度优先搜索深度优

36、先搜索 深度搜索与广度搜索的相近，最终都要深度搜索与广度搜索的相近，最终都要扩展一个结点的所有子结点扩展一个结点的所有子结点. . 区别在于对扩展结点过程，深度搜索扩区别在于对扩展结点过程，深度搜索扩展的是展的是E-E-结点的邻接结点中的一个，并将其结点的邻接结点中的一个，并将其作为新的作为新的E-E-结点继续扩展，当前结点继续扩展，当前E-E-结点仍为结点仍为活结点，待搜索完其子结点后，回溯到该结活结点，待搜索完其子结点后，回溯到该结点扩展它的其它未搜索的邻接结点。而广度点扩展它的其它未搜索的邻接结点。而广度搜索，则是扩展搜索，则是扩展E-E-结点的所有邻接结点，结点的所有邻接结点，E-E-

37、结点就成为一个死结点。结点就成为一个死结点。 5.3.1 5.3.1 算法框架算法框架 1算法的基本思路算法的基本思路2算法框架算法框架1 1算法的基本思路算法的基本思路 算法设计的基本步骤为：算法设计的基本步骤为： 1 1）确定图的存储方式；）确定图的存储方式； 2 2）遍历过程中的操作，其中包括为输出）遍历过程中的操作，其中包括为输出问题解而进行的存储操作；问题解而进行的存储操作； 3 3）输出问题的结论。）输出问题的结论。 4 4）一般在回溯前的应该将结点状态恢复）一般在回溯前的应该将结点状态恢复为原始状态，特别是在有多解需求的问题中。为原始状态，特别是在有多解需求的问题中。2算法框架算

38、法框架1）用邻接表存储图的搜索算法）用邻接表存储图的搜索算法2）用邻接矩阵存储图的搜索算法）用邻接矩阵存储图的搜索算法graph head100graph head100；dfs(int k) / headdfs(int k) / head图的顶点数组图的顶点数组/ / edgenode *ptr / ptr edgenode *ptr / ptr图的边表指针图的边表指针/ / visitedk=1; /* visitedk=1; /* 记录已遍历过记录已遍历过 */ */ print(“ print(“访问访问 ”,k); /* ”,k); /* 印出遍历顶点值印出遍历顶点值 */ */ p

39、tr=headk.firstedge; /* ptr=headk.firstedge; /* 顶点的第一个邻接点顶点的第一个邻接点 */ */ while ( ptr NULL ) /* while ( ptr NULL ) /* 遍历至链表尾遍历至链表尾 */ */ if ( visitedptr-vertex=0) /* if ( visitedptr-vertex=0) /* 如过没遍历过如过没遍历过 */ */ dfs(ptr-vertex); /* dfs(ptr-vertex); /* 递归遍历递归遍历 */ */ ptr = ptr-nextnode; /* ptr = ptr-

40、nextnode; /* 下一个顶点下一个顶点 */ */ 算法分析：n n图中有图中有 n n 个顶点，个顶点，e e 条边。扫描边的时间为条边。扫描边的时间为O(e)O(e)。遍历图的时间复杂性为遍历图的时间复杂性为O(n+e)O(n+e)。 返回返回 graph g100100,int ngraph g100100,int n；dfsm(int k)dfsm(int k) int j int j； print(“ print(“访问访问 ”,k); ”,k); visitedk=1 visitedk=1； for(j=1 for(j=1；j=nj=n；j+) /j+) /依次搜索依次搜索

41、vkvk的邻接点的邻接点 if(gkj=1 and visitedj=0) if(gkj=1 and visitedj=0) dfsm(g,j) dfsm(g,j) /(vk /(vk，vj)Evj)E，且，且vjvj未访问过，故未访问过，故vjvj为新出发点为新出发点 算法分析：查找每一个顶点的所有的边，所需时间为查找每一个顶点的所有的边，所需时间为O(n)O(n)，遍，遍历图中所有的顶点所需的时间为历图中所有的顶点所需的时间为O(n2)O(n2)。 返回返回5.3.2 5.3.2 深度优先搜索的应用深度优先搜索的应用【例【例1】走迷宫问题：问题同】走迷宫问题：问题同5.2.2【例【例2】1

42、、算法设计：深度优先搜索，就是一直向深度优先搜索，就是一直向着可通行的下一个方格行进，直到搜索到出着可通行的下一个方格行进，直到搜索到出口就找到一个解。若行不通时，则返回上一口就找到一个解。若行不通时，则返回上一个方格，继续搜索其它方向。个方格，继续搜索其它方向。2、数据结构设计：我们还是用迷宫本身的存储我们还是用迷宫本身的存储空间除了记录走过的信息，还要标识是否可行：空间除了记录走过的信息，还要标识是否可行： mazeij=3 mazeij=3 标识走过的方格标识走过的方格 ； mazeij=2 mazeij=2 标识走入死胡同的方格，标识走入死胡同的方格，这样，最后存储为这样，最后存储为“

43、3”“3”的方格为可行的方格。的方格为可行的方格。而当一个方格四个方向都搜索完还没有走到出口，而当一个方格四个方向都搜索完还没有走到出口，说明该方格或无路可走或只能走入了说明该方格或无路可走或只能走入了“死胡同死胡同”。3、算法int maze88=0,0,0,0,0,0,0,0,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,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,0,0,1,0,1,1,0,1,0, 0

44、,1,0,0,0,0,1,1,0,1,0,0,1,0,0,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, 0,1,1,1,1,1,1,0;fx4=1,-1,0,0, fy4=0,0,-1,1; int i,j,k,total; fy4=0,0,-1,1; int i,j,k,total;main( )main( ) int total=0; int total=0; maze11=3; / maze11=3; /入口坐标设置已走标志入口坐标设置已走标志/ / search(1,1);search(1,1); p

45、rint(“Total is”,total); / print(“Total is”,total); /统计总步数统计总步数/ / search(int i, int j)search(int i, int j)int k,newi,newj;int k,newi,newj; for(k=1;k=4;k+) / for(k=1;k=4;k+) /搜索可达的方格搜索可达的方格/ / if( if(check(i,j,k)check(i,j,k)=1)=1) newi=i+fxk; newj=j+fyk; newi=i+fxk; newj=j+fyk; mazenewinewj=3; / maze

46、newinewj=3; /来到新位置后来到新位置后, ,设置已走过标志设置已走过标志/ / if (newi=8 and newj=8) / if (newi=8 and newj=8) /到出口则输出到出口则输出, ,否则下一步递归否则下一步递归/ / Out( );Out( ); else search(newi,newj); else search(newi,newj); mazeij=2; / mazeij=2; /某一方格只能走入死胡同某一方格只能走入死胡同/ / Out( )Out( ) int i,j; int i,j; for( i=1;i=8;i+) for( i=1;i=8

47、;i+) print(“ print(“换行符换行符”);”); for(j=1;j=8;j+) for(j=1;j=8;j+) if if（mazeij=3mazeij=3） print(“V”); print(“V”); total+; / total+; /统计总步数统计总步数/ / else else print(“*”); print(“*”); check(int i,int j,int k)check(int i,int j,int k)int flag=1;int flag=1; i= i+fxk; j= j +fyk; i= i+fxk; j= j +fyk; if(i8 o

48、r j8) / if(i8 or j8) /是否在迷宫内是否在迷宫内/ / flag=0; flag=0; else else if(mazeij0) / if(mazeij0) /是否可行是否可行/ / flag=0; flag=0; return(flag); return(flag); 4、算法说明：1）和广度优先算法一样每个方格有四个方）和广度优先算法一样每个方格有四个方向可以进行搜索，这样一点结点（方格）向可以进行搜索，这样一点结点（方格）就可多次成为就可多次成为“活结点活结点”，而在广度优先，而在广度优先算法一点结点（方格）就可一次成为算法一点结点（方格）就可一次成为“活活结点结点

49、”，一出队就成了死结点。，一出队就成了死结点。2）用广度优先算法，搜索出的是一条最短）用广度优先算法，搜索出的是一条最短的路径，而用深度优先搜索则只能找出一的路径，而用深度优先搜索则只能找出一条可行的路径，而不能保证是最短的路径。条可行的路径，而不能保证是最短的路径。3）在空间效率上二者相近。都需要辅助空）在空间效率上二者相近。都需要辅助空间。间。【例【例2】有如图有如图1所示的七巧板，试编写一所示的七巧板，试编写一源程序如下，使用至多四种不同颜色对七巧源程序如下，使用至多四种不同颜色对七巧板进行涂色板进行涂色(每块涂一种颜色每块涂一种颜色)，要求相邻区，要求相邻区域的颜色互不相同，打印输出所

50、有可能的涂域的颜色互不相同，打印输出所有可能的涂色方案。色方案。1、问题分析:为了让算法为了让算法能识别不同区域间的相邻关能识别不同区域间的相邻关系，我们把七巧板上每一个系，我们把七巧板上每一个区域看成一个顶点若两个区区域看成一个顶点若两个区域相邻，则相应的顶点间用域相邻，则相应的顶点间用一条边相连，这样该问题就一条边相连，这样该问题就转化为图一个图的搜索问题转化为图一个图的搜索问题了。了。2、算法设计: 按顺序分别对号、号、按顺序分别对号、号、.、号区域、号区域进行试探性涂色，用、号代表种颜进行试探性涂色，用、号代表种颜色。色。 则涂色过程如下：则涂色过程如下： 1 1）对某一区域涂上与其相

51、邻区域不同的颜色。）对某一区域涂上与其相邻区域不同的颜色。 2 2）若使用种颜色进行涂色均不能满足要求，）若使用种颜色进行涂色均不能满足要求，则回溯一步，更改前一区域的颜色。则回溯一步，更改前一区域的颜色。 3 3）转步骤继续涂色，直到全部区域全部涂）转步骤继续涂色，直到全部区域全部涂色为止，输出结果。色为止，输出结果。 已经有研究证明，对任意的平面图至少存在一已经有研究证明，对任意的平面图至少存在一种四色涂色法。种四色涂色法。3、数据采用的存储结构：邻接矩阵存储邻接矩阵存储 0 1 0 0 1 0 1 0 1 0 0 1 0 1 1 0 0 1 0 1 0 1 0 0 1 0 1 0 0 0

52、 0 0 0 1 1 0 0 0 0 0 1 1 0 1 0 0 0 1 1 0 1 0 0 0 1 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0 1 1 1 0 0 0 0 1 1 1 0 0 0 1 0 1 1 1 0 01 0 1 1 1 0 04、算法如下:int data77,n,color7,total;int data77,n,color7,total;main( )main( ) int i,j; int i,j; for(i=1;i=n;i+) for(i=1;i=n;i+) for(j=1;j=n;j+) for(j=1;j=n;j+) input(dat

53、aij); input(dataij); for(j=1;j=n;j+) for(j=1;j7) if (s7) output( );output( ); else else for(i=1;i=4;i+) for(i=1;i=4;i+) colors=i; colors=i; if if （colorsame(s)colorsame(s)=0=0） try(s+1); try(s+1); output( )output( ) int i,; int i,; print( print(换行符，换行符，serial numberserial number：,total);,total); for

54、 i:=1 to n do for i:=1 to n do print(colori); print(colori); total=total+1; total=total+1; colorsame(int s)colorsame(int s) / /判断相邻点是否同色判断相邻点是否同色/ / int i,flag; int i,flag; flag=0; flag=0; for(i=1;i=s-1;i+) for(i=1;iDFN(3)=3L(10)=4DFN(3)=3。同理，结点。同理，结点2 2、5 5也是关结点。也是关结点。 按后根次序访问深度优先生成树的结点，按后根次序访问深度优先

55、生成树的结点，可以很容易地算出可以很容易地算出L L（U U）。于是，为了确定）。于是，为了确定图图G G的关结点的关结点, ,必须既完成对必须既完成对G G的深度优先检索，的深度优先检索，产生产生G G的深度优先生成树的深度优先生成树T T，又要按后根次序，又要按后根次序访问树访问树T T的结点。的结点。算法ART计算DFN和L的算法如下： int DFNn int DFNn，LnLn，numnum，n n ART ART（u u，v v） /u /u是深度优先检索的开是深度优先检索的开始结点。在深度优先生成树中，始结点。在深度优先生成树中， u u若有父亲，那末若有父亲，那末v v就是它的

56、父亲。假设就是它的父亲。假设数组数组DFNDFN是全程量，并将其初始化为是全程量，并将其初始化为0 0。numnum是是全程变量，被初始化为全程变量，被初始化为 1 1。n n是是 G G的结点数的结点数算法如下：算法如下：intDFNn，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）；）；elseif（wv）if(L（u）DFN（w）)L（u）=DFN（w）；）； 算法说明： 算法算法ARTART实现了对图实现了对

57、图G G的深度优先检索；的深度优先检索；在检索期间，对每个新访问的结点赋予深度在检索期间，对每个新访问的结点赋予深度优先数；同时对这棵树中每个结点的优先数；同时对这棵树中每个结点的L L（i i）值也进行计算。值也进行计算。 如果连通图如果连通图G G有有n n个结点个结点e e条边，且条边，且G G由邻由邻接表表示，那末接表表示，那末ARTART的计算时间为的计算时间为O O（n ne e）。）。识别关结点的总时间不超过识别关结点的总时间不超过O O（n ne e）。）。3 3非重连通图的加边策略非重连通图的加边策略 G=( V, E ) G=( V, E )是是G G的最大重连通子图，的最

58、大重连通子图，指的是指的是G G中再没有这样的重连通子图中再没有这样的重连通子图G=( G=( V, E )V, E )存在，使得存在，使得VVVV且且EEEE。 最大重连通子图称为重连通分图最大重连通子图称为重连通分图图5-10 图5-6所示的重连通分图两个重两个重连连通分通分图图至多有一个公共至多有一个公共结结点，且点，且这这个个结结点就是割点。点就是割点。因而可以推出任何一条因而可以推出任何一条边边不可能同不可能同时时出出现现在两个不同的重在两个不同的重连连通通分分图图中（因中（因为这为这需要两个公共需要两个公共结结点）。点）。选选取两个重取两个重连连通分通分图图中中不同的不同的结结点点

59、连结为边连结为边，则则生成的新生成的新图为图为重重连连通的。多个重通的。多个重连连通通分分图图的情况依此的情况依此类类推。推。 使用这个方法将图使用这个方法将图5-65-6变成重连通图，变成重连通图，需要对应于关结点需要对应于关结点3 3增加边（增加边（4 4，1010）和（）和（1010，9 9）；对应关结点）；对应关结点2 2增加边（增加边（1 1，5 5）；对应）；对应关结点关结点5 5增加（增加（6 6，7 7），结果如图），结果如图5-115-11。 图5-11 (图5-6改进为重连通图）5.4 回 溯 法回回溯溯算算法法实实际际是是一一个个类类似似枚枚举举的的搜搜索索尝尝试试方方法

60、法，它它的的主主题题思思想想是是在在搜搜索索尝尝试试中中找找问问题题的的解解，当当不不满满足足求求解解条条件件就就”回回溯溯”返返回回，尝尝试试别别的的路路径径。回回溯溯算算法法是是尝尝试试搜搜索索算算法法中中最最为为基基本本的的一一种种算算法法，其其采采用用了了一一种种“走走不不通通就就掉掉头头”的思想，作为其控制结构。的思想，作为其控制结构。5.4.1 5.4.1 认识回溯法认识回溯法【例【例1 1】八皇后问题模型建立】八皇后问题模型建立 要在要在8*88*8的国际象棋棋盘中放八个皇后，的国际象棋棋盘中放八个皇后，使任意两个皇后都不能互相吃掉。规则：皇使任意两个皇后都不能互相吃掉。规则：皇

61、后能吃掉同一行、同一列、同一对角线的任后能吃掉同一行、同一列、同一对角线的任意棋子。如图意棋子。如图5-125-12为一种方案，求所有的解。为一种方案，求所有的解。 模型建立 不妨设八个皇后为不妨设八个皇后为xixi，她们分别在第，她们分别在第i i行行（i=1i=1，2 2，3 3，44，8 8），这样问题的解空），这样问题的解空间，就是一个八个皇后所在列的序号，为间，就是一个八个皇后所在列的序号，为n n元元一维向量（一维向量（x1,x2,x3,x4,x5,x6,x7,x8x1,x2,x3,x4,x5,x6,x7,x8）, ,搜索空搜索空间是间是1xi81xi8（i=1i=1，2 2，3

62、3，44，8 8），共），共8888个状态。约束条件是八个（个状态。约束条件是八个（1,x11,x1）,(2,x2) ,(2,x2) ,(3,x3),(4,x4) ,(5,x5), (6,x6) , (7,x7), ,(3,x3),(4,x4) ,(5,x5), (6,x6) , (7,x7), (8,x8)(8,x8)不在同一行、同一列和同一对角线上。不在同一行、同一列和同一对角线上。 虽然问题共有虽然问题共有8 88 8个状态，但算法不会真正地搜个状态，但算法不会真正地搜索这么多的状态，因为前面已经说明，回溯法采用索这么多的状态，因为前面已经说明，回溯法采用的是的是“走不通就掉头走不通就掉

63、头”的策略，而形如的策略，而形如(1,1,x3,x4, x5,x6,x7,x8(1,1,x3,x4, x5,x6,x7,x8）的状态共有）的状态共有8 86 6个，由于个，由于1 1，2 2号皇后号皇后在同一列不满足约束条件，回溯后这在同一列不满足约束条件，回溯后这8686个状个状态是不会搜索的。态是不会搜索的。 算法设计1：加约束条件的枚举算法加约束条件的枚举算法 最简单的算法就是通过八重循环模拟搜索空最简单的算法就是通过八重循环模拟搜索空间中的间中的8 88 8个状态，按深度优先思想，从第一个皇后个状态，按深度优先思想，从第一个皇后从第一列开始搜索，每前进一步检查是否满足约束从第一列开始搜

64、索，每前进一步检查是否满足约束条件条件, ,不满足时，用不满足时，用continuecontinue语句回溯，满足满足语句回溯，满足满足约束条件，开始下一层循环，直到找出问题的解。约束条件，开始下一层循环，直到找出问题的解。 约束条件不在同一列的表达式为约束条件不在同一列的表达式为xi xjxi xj；而；而在同一主对角线上时在同一主对角线上时xi-i=xj-j, xi-i=xj-j, 在同一负对角线在同一负对角线上时上时xi+i=xj+jxi+i=xj+j，因此，不在同一对角线上的约束，因此，不在同一对角线上的约束条件表示为条件表示为abs(xi-xj) abs(i-j)abs(xi-xj)

65、 abs(i-j)（absabs（）取绝对（）取绝对值）。值）。算法1：queen1queen1（ ）int a9;int a9; for for(a1=1;a1=8;a1+)(a1=1;a1=8;a1+) for for(a2=1;a2=8;a2+)(a2=1;a2=8;a2+) if if （ check(a,2)check(a,2)=0 =0 ） continue; continue; for for(a3=1;a3=8;a3+)(a3=1;a3=8;a3+) if if（check(a,3)=0check(a,3)=0） continue; continue; for for(a4=1

66、;a4=8;a4+)(a4=1;a4=8;a4+) if if （check(a,4)=0check(a,4)=0） continue; continue; for for(a5=1;a5=8;a5+)(a5=1;a5=8;a5+) if if （check(a,5)=0check(a,5)=0） continue; continue; for for(a6=1;a6=8;a6+)(a6=1;a6=8;a6+) if if （check(a,6)=0check(a,6)=0） continue; continue; for(a7=1;a7=8;a7+) for(a7=1;a7=8;a7+) i

67、f if （check(a,7)=0check(a,7)=0） continue; continue; for(a8=1;a8=8;a8+) for(a8=1;a8=8;a8+) if if （check(a,8)=0check(a,8)=0） continue; continue; else else for(i=1;i=8;i+) for(i=1;i=8;i+) print(ai); print(ai); check(int a ,int n)check(int a ,int n)int i;int i; for(i=1;i=n-1;i+) for(i=1;i=n-1;i+) if (ab

68、s(ai-an)=abs(i-n) or (ai=an) if (abs(ai-an)=abs(i-n) or (ai=an) return(0); return(0);return(1);return(1); 算法分析1： 若将算法中循环嵌套间的检查是否满足若将算法中循环嵌套间的检查是否满足约束条件的约束条件的: : “if “if （check(a,i)=0check(a,i)=0）continue;continue; i=2,3,4,5,6,7“ i=2,3,4,5,6,7“ 语句都去掉，只保留最后一个检查语句：语句都去掉，只保留最后一个检查语句： “if “if （check(a,8)

69、=0check(a,8)=0）continue;”continue;”相应地相应地checkcheck（）函数修改成：（）函数修改成：check*(a,n)check*(a,n)int i,j;int i,j; for(i=2;i=n;i+) for(i=2;i=n;i+) for(j=1;j=i-1;j+) for(j=1;j0 ) while( k0 ) ak=ak+1; ak=ak+1; while (ak=n) and ( while (ak=n) and (check(k)check(k)=0) /=0) /搜索第搜索第k k个皇后位置个皇后位置/ / ak=ak+1; ak=ak+

70、1; if if（ ak=n ak=n） if(k=n ) if(k=n ) output(n); output(n); / / 找到一组解找到一组解/ / else k=k+1; else k=k+1; 继续为第继续为第k+1k+1个皇后找到位置个皇后找到位置/ / ak=0;/ ak=0;/注意下一个皇后一定要从头开始搜索注意下一个皇后一定要从头开始搜索/ / else k=k-1; / else k=k-1; /回溯回溯/ / check(int k)check(int k) int i; int i; for(i=1;i=k-1;i+) for(i=1;i=k-1;i+)if (abs

71、(ai-ak)=abs(i-k) or (ai=ak)if (abs(ai-ak)=abs(i-k) or (ai=ak) return(0); return(0); return(1); return(1); output( )output( ) int i; int i; for(i=1;i=n;i+) for(i=1;i=n;i+) print(ai); print(ai); 算法设计3：递归算法 这种方式也可以解决任意的这种方式也可以解决任意的n n皇后问题。皇后问题。 这里我们用第三章这里我们用第三章3 32 23 3 “利用数组记录利用数组记录状态信息状态信息”的技巧，用三个数组的

72、技巧，用三个数组c,b,dc,b,d分别记录棋分别记录棋盘上的盘上的n n个列、个列、n n个主对角线和个主对角线和n n个负对角线的占用个负对角线的占用情况。情况。 以四阶棋盘为例，如图以四阶棋盘为例，如图5-135-13，共有，共有2n-2n-1=71=7个主对角线，对应地也有个主对角线，对应地也有7 7个负对角线。个负对角线。图5-13 四皇后棋盘示意图 用用i i，j j分别表示皇后所在的行列，同一主对角分别表示皇后所在的行列，同一主对角线上的行列下标的差一样，若用表达式线上的行列下标的差一样，若用表达式i-ji-j编号，则编号，则范围为范围为-n+1n-1-n+1n-1，所以我们用表

73、达式，所以我们用表达式i-j+ni-j+n对主对主对角线编号，范围就是对角线编号，范围就是12n-112n-1。同样地，负对角。同样地，负对角线上行列下标的和一样，用表达式线上行列下标的和一样，用表达式i+ji+j编号，则范围编号，则范围为为22n22n。算法算法3 3： int a20,b20,c40,d40;int a20,b20,c40,d40; int n,t int n,t，i,j,k; /ti,j,k; /t记录解的个数记录解的个数/ / queen3 queen3（ ） int i, int i, input(n); input(n); for(i=1;i=n;i+) for(i

74、=1;i=n;i+) bi=0; bi=0; ci=0; cn+i=0; ci=0; cn+i=0; di=0; dn+i=0; di=0; dn+i=0; trytry（1 1）; ; try(i:integer)try(i:integer)int j;int j; for(j=1;j=n;j+) / for(j=1;j=n;j+) /第第i i个皇后有个皇后有n n种可能位置种可能位置/ / if (bj=0) and (ci+j=0) and (di-j+n=0) if (bj=0) and (ci+j=0) and (di-j+n=0) ai=j; / ai=j; /摆放皇后摆放皇后/

75、 / bj=1; / bj=1; /占领第占领第j j列列/ / ci+j=1; di-j+n=1; / ci+j=1; di-j+n=1; /占领两个对角线占领两个对角线/ / if (i8) if (i8) try(i+1); /n try(i+1); /n个皇后没有摆完，递归摆放下一皇后个皇后没有摆完，递归摆放下一皇后/ / else else output( );output( ); / /完成任务，打印结果完成任务，打印结果/ / bj=0; ci+j=0; di-j+n=0; / bj=0; ci+j=0; di-j+n=0; /回溯回溯/ / output( )output( )

76、 t=t+1; t=t+1; print(t, ); print(t, ); for( k=1;k=n;k+) for( k=1;k0(While (i0(有路可走有路可走) and () and (未达到目标未达到目标) /) /还未回溯到头还未回溯到头/ / if (in) / if (in) /正在处理第正在处理第i i个元素个元素/ / 搜索到一个解，输出搜索到一个解，输出; ; else else ai ai第一个可能的值；第一个可能的值； while (ai while (ai在不满足约束条件在不满足约束条件 且且 在在搜索空间内在在搜索空间内) ) ai ai下一个可能的值；下一

77、个可能的值； if (ai if (ai在搜索空间内在搜索空间内) ) 标识占用的资源标识占用的资源; i=i+1; /; i=i+1; /扩展下一个结点扩展下一个结点/ / else else 清理所占的状态空间；清理所占的状态空间； i=i-1;/ i=i-1;/回溯回溯/ / 3 3）递归算法框架）递归算法框架 一般情况下用递归函数来实现回溯法比较简单，其中一般情况下用递归函数来实现回溯法比较简单，其中i i为搜为搜索深度。索深度。int an;int an;try(int i)try(int i)if if （inin） 输出结果输出结果; ; else else for for（ j

78、= j=下界下界 ; j= ; jn or xm or x1 or yn or xm or x1 or y1) print(x,y error!); return; print(x,y error!); return; for(i=1;i=;i+) for(j=1;j=;j+) aij=0; for(i=1;i=;i+) for(j=1;j=;j+) aij=0; axy=1; axy=1; find(x,y,2);find(x,y,2); if (count=0 ) print(“No answer!”); if (count=0 ) print(“No answer!”); else pr

79、int(“count=!”,count); else print(“count=!”,count); find(int y,int x,int dep)find(int y,int x,int dep)int i , xx , yy ;int i , xx , yy ;for i=1 to 8 do /for i=1 to 8 do /加上方向增量加上方向增量, ,形成新的坐标形成新的坐标/ / xx=x+fxi; yy=y+fyi; xx=x+fxi; yy=y+fyi; if (check(xx,yy)=1) / if (check(xx,yy)=1) /判断新坐标是否出界判断新坐标是否出

80、界, ,是否已走过是否已走过?/?/ axx,yy=dep; / axx,yy=dep; /走向新的坐标走向新的坐标/ / if (dep=n*m) if (dep=n*m) output( ); output( ); else else find(xx,yy,dep+1); / find(xx,yy,dep+1); /从新坐标出发从新坐标出发, ,递归下一层递归下一层/ / axx,yy=0; / axx,yy=0; /回溯回溯, ,恢复未走标志恢复未走标志/ / outputoutput（ ） count=count+1; count=count+1; print(“ print(“换行符

81、换行符”);”); print(count=,count); print(count=,count); for y=1 to n do for y=1 to n do print(“ print(“换行符换行符”);”); for x=1 to m do for x=1 to m do print(ay,x:3); print(ay,x:3); 【例【例3 3】素数环问题】素数环问题 把从把从1 1到到2020这这2020个数摆成一个环，要求相个数摆成一个环，要求相邻的两个数的和是一个素数。邻的两个数的和是一个素数。 1、算法设计 尝试搜索从尝试搜索从1 1开始，每个空位有开始，每个空位有22

82、0220共共1919种可能，约束条件就是填进去的数满足：种可能，约束条件就是填进去的数满足：与前面的数不相同；与前面相邻数据的和是与前面的数不相同；与前面相邻数据的和是一个素数。一个素数。第第2020个数还要判断和第个数还要判断和第1 1个数的和个数的和是否素数。是否素数。2、算法 main main（）（） int a20,k; int a20,k; for (k=1;k=20;k+) for (k=1;k=20;k+) ak=0; ak=0; a1=1; a1=1; try(2);try(2); try(int i)try(int i) int k int k for (k=2;k=20;

83、k+) for (k=2;k=20;k+) if ( if (check1(k,i)=1check1(k,i)=1 and and check3(k,i)=1check3(k,i)=1 ) ) ai=k; ai=k; if if （i=20i=20） output( );output( ); else else try(i+1); try(i+1); ai=0; ai=0; check1(int j,int i)check1(int j,int i) int k; int k; for (k=1;k=i-1;k+) for (k=1;k=i-1;k+) if (ak=j ) return(0)

84、; if (ak=j ) return(0); return(1); return(1); check2(int x)check2(int x) int k,n; int k,n; n= sqrt(x); n= sqrt(x); for (k=2;k=n;k+) for (k=2;k=n;k+) if (x mod k=0 ) return(0); if (x mod k=0 ) return(0); return(1); return(1); check3(int j,int i)check3(int j,int i) if (i20) return( if (i20) return(che

85、ck2(j+ai-1check2(j+ai-1);); else else return(check2(j+ai-1) and check2(j+a1); return(check2(j+ai-1) and check2(j+a1); output( )output( ) int k; int k; for (k=1;k=20;k+)for (k=1;k=r+1，若，若ri+arinrn） print(“Input n,r error!”); print(“Input n,r error!”); else else a0=r; a0=r; comb(n,r); / comb(n,r); /调用

86、递归过程调用递归过程/ / comb2(int n,int r,int a)comb2(int n,int r,int a)int i,ri; ri=1; a1=n;int i,ri; ri=1; a1=n; while(a1r-1) while(a1r-1) if if （rirrir） / /没有搜索到底没有搜索到底/ / if if （ri+arirri+arir） ari+1=ari-1; ri=ri+1; ari+1=ari-1; ri=ri+1; else ri=ri-1; ari=ari-1; / else ri=ri-1; ari=ari-1; /回溯回溯/ / else el

87、se for (j=1;j=r;j+) print(aj); for (j=1;j=1) 3.1 依次考察每一种颜色，若顶点k的着色与其他顶点的着色不发生冲突，则转步骤3.2；否则，搜索下一个颜色； 3.2 若顶点已全部着色，则输出数组colorn，返回； 3.3 否则， 3.3.1 若顶点k是一个合法着色，则k=k+1，转步骤3处理下一个顶点； 3.3.2 否则，重置顶点k的着色情况，k=k-1，转步骤3回溯；算法算法图着色问题图着色问题voidGraphColor(intn,intc,intm)/所有数组下标从所有数组下标从1开始开始for(i=1;i=1)colork=colork+1;

88、while(colork=m)ifOk(k)break;elsecolork=colork+1;/搜索下一个颜色搜索下一个颜色if(colork=m&k=n)/求解完毕，输出解求解完毕，输出解for(i=1;i=n;i+)coutcolori;return; else if (colork=m & kn) k=k+1; /处理下一个顶点 else colork=0; k=k-1; /回溯 bool Ok(int k) /判断顶点k的着色是否发生冲突 for (i=1; i=1)3.1xk=xk+1，搜索下一个顶点，搜索下一个顶点;3.2若若(n个顶点没有被穷举个顶点没有被穷举)执行下列操作执行

89、下列操作3.2.1若若(顶点顶点xk不在哈密顿回路上不在哈密顿回路上&(xk- -1,xk)E)，转步骤转步骤3.3;3.2.2否则，否则，xk=xk+1，搜索下一个顶点；，搜索下一个顶点；3.3若数组若数组xn已形成哈密顿路径，则输出数组已形成哈密顿路径，则输出数组xn，算法结束；，算法结束；3.4否则，否则，3.4.1若数组若数组xn构成哈密顿路径的部分解，构成哈密顿路径的部分解，则则k=k+1，转步骤，转步骤3；3.4.2否则，重置否则，重置xk，k=k- -1，取消顶点，取消顶点xk的访问标志，的访问标志，转步骤转步骤3；算法算法哈密顿回路问题哈密顿回路问题voidHamiton(in

90、tn,intx,intc)/所有数组下标从所有数组下标从1开始开始for(i=1;i=1)xk=xk+1;/搜索下一顶点搜索下一顶点while(xk=n)if(visitedxk=0&cxk-1xk=1)break;elsexk=xk+1; if (xk=n & k= =n & cxk1= =1) for (k=1; k=n; k+ ) coutxk; return; else if (xk=n & kn ) visitedxk=1; k=k+1; else /回溯 xk=0; visitedxk=0; k=k-1; 5.4.4 5.4.4 应用应用2 2 排列及排列树的回溯搜索排列及排列树的

91、回溯搜索 【例【例7 7】输出自然数】输出自然数1 1到到n n所有不重复的排所有不重复的排列，即列，即n n的全排列的全排列 1、算法设计 n n的全排列是一组的全排列是一组n n元一维向量元一维向量: :（x1x1，x2x2，x3x3，xnxn），搜索空间是：），搜索空间是：1xin 1xin i=1i=1，2 2，3 3，n,n,约束条件很简单，约束条件很简单，xixi互不互不相同。相同。 这里我们采用第三章这里我们采用第三章“3“32 23 3 利用数利用数组记录状态信息组记录状态信息”的技巧，设置的技巧，设置n n个元素的数个元素的数组组d d，其中的，其中的n n个元素用来记录数据

92、个元素用来记录数据1n1n的的使用情况，已使用置使用情况，已使用置1 1，未使用置，未使用置0 0。2、算法 main main（ ） int j,n, int j,n, print(Input n= ); print(Input n= ); input(n); input(n); for(j=1;j=r;j+) for(j=1;j=r;j+) dj=0; dj=0; try(1);try(1); try(int k)try(int k) int j; int j; for(j=1;j=n;j+) for(j=1;j=n;j+) if (dj=0) ak=j; dj=1; if (dj=0)

93、ak=j; dj=1; else continue; else continue; if (kn) if (kn) try(k+1); try(k+1); else else p=p+1; p=p+1; output(k)output(k); dak=0; dak=0; output( ) output( ) int j; int j; print(p,”:”) print(p,”:”) for(j=1;j=n;j+) for(j=1;j=n;j+) print(aj); print(aj); print(“ print(“换行符换行符”);”); 3 3、算法说明：变量变量p p记录排列的组

94、数，记录排列的组数，k k为当前为当前 处理的第处理的第k k个元素个元素4、算法分析 全全排排列列问问题题的的复复杂杂度度为为O O（nnnn），不不是是一一个个好好的的算算法法。因因此此不不可可能能用用它它的的结结果果去去搜搜索索排列树。排列树。【例【例8 8】全排列算法另一解法】全排列算法另一解法搜索排列树搜索排列树的算法框架的算法框架 1、算法设计 根根据据全全排排列列的的概概念念，定定义义数数组组初初始始值值为为（1 1，2 2，3 3，4 4，n n），这这是是全全排排列列中中的的一一种种，然然后后通通过过数数据据间间的的交交换换，则则可可产产生生所所有的不同排列。有的不同排列。2

95、、算法 int a100,n,s=0; int a100,n,s=0; main( ) main( ) int i,; int i,; input(n); input(n); for(i=1;i=n;i+) for(i=1;in) if (tn) output( );output( ); else else for(j=t;j=n;j+) for(j=t;j=n;j+) swap(t,j); swap(t,j); try(t+1); try(t+1); swap(t,j);swap(t,j); / /回溯时，恢复原来的排列回溯时，恢复原来的排列/ / output( )output( ) in

96、t j; int j; printf(n); printf(n); for( j=1;j=n;j+) printf( mod d,aj); for( j=1;j=n;j+) printf( mod d,aj); s=s+1; s=s+1; swap(int t1,int t2)swap(int t1,int t2) int t; int t; t=at1; t=at1; at1= at2; at1= at2; at2=t; at2=t; 3、算法说明 1 1）有的读者可能会想）有的读者可能会想try( )try( )函数中，不函数中，不应该出现自身之间的交换，应该出现自身之间的交换，forfo

97、r循环是否应该循环是否应该改为改为for(j=t+1;j=n;j+)for(j=t+1;j=n;j+)？回答是否定的。？回答是否定的。当当n=3n=3时，算法的输出是：时，算法的输出是：123123，132132，213213，231231，321321，312312。123123的输出说明第一次到达的输出说明第一次到达叶结点是不经过数据交换的，而叶结点是不经过数据交换的，而132132的排列也的排列也是是1 1不进行交换的结果。不进行交换的结果。2 2）forfor循循环环体体中中的的第第二二个个swap( swap( ) )调调用用，是是用用来来恢恢复复原原顺顺序序的的。为为什什么么要要有

98、有如如此此操操作作呢呢？还还是是通通过过实实例例进进行行说说明明，排排列列“213”“213”是是由由“123”“123”进进行行1 1，2 2交交换换等等到到的的所所以以在在回回溯溯时时要将要将“132” “132” 恢复为恢复为“123”“123”。4、算法分析 全全排排列列算算法法的的复复杂杂度度为为O O（n!n!）, , 其其结结果果可以为搜索排列树所用。可以为搜索排列树所用。【例【例9 9】按排列树回溯搜索解决八皇后问题】按排列树回溯搜索解决八皇后问题 1、算法设计 利利用用例例6“6“枚枚举举”所所有有1-n1-n的的排排列列，从从中中选选出出满满足足约约束束条条件件的的解解来来

99、。这这时时的的约约束束条条件件只只有有不不在在同同一一对对角角线线，而而不不需需要要不不同同列列的的约约束束了了。和和例例1 1的的算算法法3 3一一样样，我我们们用用数数组组c c，d d记录每个对角线的占用情况。记录每个对角线的占用情况。 2、算法 int a100,n,s=0,c20,d20; int a100,n,s=0,c20,d20; main( ) main( ) int i; int i; input(n); input(n); for(i=1;i=n;i+) for(i=1;i=n;i+) ai=i; ai=i; for (i=1;i=n;i+) for (i=1;in) i

100、f (tn) output( ); output( ); else else for(j=t;j=n;j+) for(j=t;j=n;j+) swap(t,j); swap(t,j); if (ct+at=0 and dt-at+n=0) if (ct+at=0 and dt-at+n=0) ct+at=1; dt-at+n=1; ct+at=1; dt-at+n=1; try(t+1); try(t+1); ct+at=0; dt-at+n=0; ct+at=0; dt-at+n=0; swap(t,j); swap(t,j); output( )output( ) int j; int j

101、; print( print(换行符换行符);); for( j=1;j=n;j+) print(aj); for( j=1;j=ni=n就认就认为找到了更大的解，为找到了更大的解，inin不必解释位数多数据不必解释位数多数据一定大；一定大；i=ni=n时，由于尝试是由小到大进行的，时，由于尝试是由小到大进行的，位数相等时后来满足条件的位数相等时后来满足条件的菀欢菀欢 惹懊娴拇惹懊娴拇蟆蟆3、算法 main( ) main( ) int A101,B101; int i,j,k,n,r int A101,B101; int i,j,k,n,r； A1=1; A1=1; for(i=2;i=10

102、0;i+) / for(i=2;i=100;i+) /置初值：首位为置初值：首位为1 1 其余为其余为0/0/ Ai=0; Ai=0; n=1; i=1; n=1; i=1; while(A1=9) while(A1=n) / if (i=n) /发现有更大的满足条件的高精度数据发现有更大的满足条件的高精度数据/ / n=i; / n=i; /转存到数组转存到数组B B中中/ / for (k=1;k=n;k+) for (k=1;k=n;k+) Bk=Ak; Bk=Ak; i=i+1;r=0;i=i+1;r=0; for(j=1;j=i;j+) / for(j=1;j=i;j+) /检查第检

103、查第i i位是否满足条件位是否满足条件/ / r=r*10+Aj; r=r mod i; r=r*10+Aj; r=r mod i; if(r0) / if(r0) /若不满足条件若不满足条件/ / Ai=Ai+i-r ; / Ai=Ai+i-r ; /第第i i位可能的解位可能的解/ / while (Ai9 and i1) / while (Ai9 and i1) /搜索完第搜索完第i i位的解，回位的解，回 溯到前一位溯到前一位/ / Ai=0; i=i-1; Ai=Ai+i; Ai=0; i=i-1; Ai=Ai+i; 4、算法说明1 1）从）从A1=1A1=1开始，每增加一位开始，每

104、增加一位AiAi（初（初值为值为0 0）先计算）先计算r=(A1*10i-1+A2*10i-r=(A1*10i-1+A2*10i-2+Ai)2+Ai)，再测试，再测试r=r mod ir=r mod i是否为是否为0 0。 2 2）r=0r=0表示增加第表示增加第i i位后，满足条件，与位后，满足条件，与原有满足条件的数（存在数组原有满足条件的数（存在数组B B中）比较，若中）比较，若前者大，则更新后者（数组前者大，则更新后者（数组B B），继续增加下），继续增加下一位。一位。 3 3）r0r0表示增加表示增加i i位后不满足整除条件，位后不满足整除条件，接下来算法中并不是继续尝试接下来算法中

105、并不是继续尝试Ai= Ai+1Ai= Ai+1，而是继续尝试，而是继续尝试Ai= Ai+i-rAi= Ai+i-r，因为若，因为若Ai= Ai+i-r=9Ai= Ai+i-r9Ai -r +i9时时, ,要进位也要进位也不能算满足条件。这时，只能将此位恢复初不能算满足条件。这时，只能将此位恢复初值值0 0且回退到前一位（且回退到前一位（i=i-1i=i-1）尝试）尝试Ai= Ai Ai= Ai +i+i。这正是最后一个。这正是最后一个whilewhile循环所做的工循环所做的工作。作。 5 5）当回溯到）当回溯到i=1i=1时，时，A1A1加加1 1开始尝试首开始尝试首位为位为2 2的情况，最

106、后直到将的情况，最后直到将A1=9A1=9的情况尝试的情况尝试完毕，算法结束。完毕，算法结束。【例【例1111】流水作业车间调度】流水作业车间调度 n n个个作作业业要要在在由由2 2台台机机器器M1M1和和M2M2组组成成的的流流水水线线上上完完成成加加工工。每每个个作作业业加加工工的的顺顺序序都都是是先先在在M1M1上上加加工工，然然后后在在M2M2上上加加工工。M1M1和和M2M2加加工工作作业业i i所所需需的的时时间间分分别别为为aiai和和bibi。流流水水作作业业调调度度问问题题要要求求确确定定这这n n个个作作业业的的最最优优加加工工顺顺序序，使使得得从从第第一一个个作作业业在

107、在机机器器M1M1上上开开始始加加工工，到到最最后后一一个个作作业业在在机机器器M2M2上上加加工工完完成成所所需需的的时时间间最少。作业在机器最少。作业在机器M1M1、M2M2的加工顺序相同。的加工顺序相同。1、算法设计 1 1）问问题题的的解解空空间间是是一一棵棵排排列列树树，简简单单的的解解决决方方法法就就是是在在搜搜索索排排列列树树的的同同时时，不不断断更更新新最最优优解解，最最后后找找到到问问题题的的解解。算算法法框框架架和和例例6 6完完全全相相同同，用用数数组组x x（初初值值为为1 1，2 2，3 3，n n）模模拟拟不不同同的的排排列列，在在不不同同排排列列下下计计算算各各种

108、种排排列列下下的加工耗时情况。的加工耗时情况。 2 2）机器）机器M1M1进行顺序加工，其加工进行顺序加工，其加工f1f1时间是固定的，时间是固定的，f1i= f1i-1+axif1i= f1i-1+axi。机器。机器M2M2则有空闲（图则有空闲（图5-195-19（1 1）或积压（图或积压（图5-195-19（2 2）的情况，总加工时间）的情况，总加工时间f2f2，当机器，当机器M2M2空闲时，空闲时，f2i=f1+ bxif2i=f1+ bxi；当机器；当机器M2M2有积压情况出现时，有积压情况出现时，f2i= f2i-1+ bxif2i= f2i-1+ bxi。总加工时间就是。总加工时间

109、就是f2nf2n。 图图5-195-19（1 1）有空闲）有空闲 图图5-195-19（2 2）有积压）有积压 3 3）一一个个最最优优调调度度应应使使机机器器M1M1没没有有空空闲闲时时间间，且且机机器器M2M2的的空空闲闲时时间间最最少少。在在一一般般情情况况下下，当当作作业业按按在在机机器器M1M1上上由由小小到到大大排排列列后后，机机器器M2M2的的空空闲闲时时间间较较少少，当当然然最最少少情情况况一一定定还还与与M2M2上上的的加加工工时时间间有有关关，所所以以还还需需要要对对解解空空间间进进行行搜搜索索。排排序序后后可可以以尽尽快快地地找找到到接接近近最最优优的的解解，再再加加入入

110、下下一一步步限限界界操操作作就就能加速搜索速度。能加速搜索速度。 4 4）经经过过以以上上排排序序后后，在在自自然然数数列列的的排排列列下下，就就是是一一个个接接近近最最优优的的解解。因因此此，在在以以后后的的搜搜索索过过程程中中，一一当当某某一一排排列列的的前前面面几几步步的的加加工工时时间间已已经经大大于于当当前前的的最最小小值值，就就无无需需进进行行进一步的搜索计算，从而可以提高算法效率。进一步的搜索计算，从而可以提高算法效率。2 2、数据结构设计、数据结构设计 1 1）用二维数组）用二维数组job1002job1002存储作业在存储作业在M1M1、M2M2上的加工时间。上的加工时间。

111、2 2）由于）由于f1f1在计算中，只需要当前值，所以用变在计算中，只需要当前值，所以用变量存储即可；而量存储即可；而f2f2在计算中，还依赖前一个作业的在计算中，还依赖前一个作业的数据，所以有必要用数组存储。数据，所以有必要用数组存储。 3 3）考虑到回溯过程的需要，用变量）考虑到回溯过程的需要，用变量f f存储当前存储当前加工所需要的全部时间。加工所需要的全部时间。3、算法int job1002,x100,nint job1002,x100,n，f1=0,f=0,f2100=0;f1=0,f=0,f2100=0;main( )main( ) int j; int j; input(n);

112、input(n); for(i=1;i=2;i+) for(i=1;i=2;i+) for(j=1;j=n;j+) for(j=1;j=n;j+) input(jobji); input(jobji); try( ); try( ); try(int i) try(int i) int j; int j; if (i=n+1) if (i=n+1) for(j=1;j=n;j+) for(j=1;j=n;j+) bestxj=xj; bestxj=xj; bestf=f; bestf=f; else else for(j=1;j=n;j+) for(j=1;jf1) f2i= f2i-1+jo

113、bxj2; if (f2i-1f1) f2i= f2i-1+jobxj2; else f2i= f1+jobxj2; else f2i= f1+jobxj2; f=f+f2i; f=f+f2i; if (fbestf) if (fbestf) swap(xi,xj); try(i+1); swap(xi,xj); try(i+1); swap(xi,xj); swap(xi,xj); f1= f1-jobxj1; f1= f1-jobxj1; f=f-f2i; f=f-f2i; 解空间为排列树的最优化类问题，都可解空间为排列树的最优化类问题，都可以依此算法解决。而对于解空间为子集树的以依此算法解决。而对于解空间为子集树的最优化类问题，类似本节例题最优化类问题，类似本节例题1 1、2 2、3 3枚举元枚举元素的选取或不选取两种情况进行搜索就能找素的选取或不选取两种情况进行搜索就能找出最优解，同时也可以加入相应的限界策略。出最优解，同时也可以加入相应的限界策略。