第5章 图的搜索算法优秀PPT.ppt

《第5章 图的搜索算法优秀PPT.ppt》由会员分享，可在线阅读，更多相关《第5章 图的搜索算法优秀PPT.ppt（137页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第5章图的搜索算法现在学习的是第1页，共137页5.1图搜索概述图搜索概述现在学习的是第2页，共137页1显式图与隐式图显式图与隐式图 在路径问题、连通性问题、可平面性检验、着色问题和网在路径问题、连通性问题、可平面性检验、着色问题和网络优化等问题中，图的结构是显式给出的，包括图中的顶点、络优化等问题中，图的结构是显式给出的，包括图中的顶点、边及权重，这类图我们称为边及权重，这类图我们称为显式图显式图，也就是一般意义上的图。，也就是一般意义上的图。隐式图隐式图是由问题的初始结点，为了求解或求证问题，根是由问题的初始结点，为了求解或求证问题，根据题目的规则（一般是由题目的意思隐含给出的），也就是

2、据题目的规则（一般是由题目的意思隐含给出的），也就是生成子结点的约束条件，逐步扩展结点，直到得到目标结点生成子结点的约束条件，逐步扩展结点，直到得到目标结点为止的一个隐式的图。为止的一个隐式的图。一、图及其术语图及其术语现在学习的是第3页，共137页2.2.显式图的常用术语显式图的常用术语 图中的这些点图中的这些点(v(v1 1,v,v2 2,v,vn n)被称为被称为顶点顶点，连接顶点的曲线或，连接顶点的曲线或直线称为直线称为边边。通常将这种由若干个顶点以及连接某些顶点的边所组成的图形称通常将这种由若干个顶点以及连接某些顶点的边所组成的图形称为图，顶点通常被称作是图中的数据元素为图，顶点通常

3、被称作是图中的数据元素.现在学习的是第4页，共137页带权图：带权图：图的边上附加一个代表性数据图的边上附加一个代表性数据(比如表示长度、流量或其他比如表示长度、流量或其他)，则称其为带权图，则称其为带权图。环环：顶点本身也有边相连，这种边称为环。：顶点本身也有边相连，这种边称为环。有限图：顶点与边数均为有限的图。有限图：顶点与边数均为有限的图。简单图：没有环且每两个顶点间最多只有一条边相连的图。简单图：没有环且每两个顶点间最多只有一条边相连的图。邻接与关联：当（邻接与关联：当（v1，v2）E，或，或E，即，即v1，v2间有边相连时，则称间有边相连时，则称v1和和v2是相邻的，它们互为是相邻的

4、，它们互为邻接点邻接点，同时称，同时称（v1，v2）或）或是与顶点是与顶点v1、v2相关联的边。相关联的边。现在学习的是第5页，共137页度数度数：从该顶点引出的边的条数，简称度。：从该顶点引出的边的条数，简称度。入度：有向图中把以顶点为终点的边的条数。入度：有向图中把以顶点为终点的边的条数。出度：有向图中把以顶点为起点的边的条数。出度：有向图中把以顶点为起点的边的条数。终端顶点：有向图中出度为终端顶点：有向图中出度为0的顶点。的顶点。路径与路长：在图路径与路长：在图G=(V，E)中，如果存在由不同的边中，如果存在由不同的边(vi0，vi1)，(vi1，vi2)，(vin-1，vin)或是或是

5、，)组成的序列，则称顶点组成的序列，则称顶点vi0，vin是是连通连通的，顶点序列（的，顶点序列（vi0，vi1，vi2，vin）是从顶点）是从顶点vi0到顶点到顶点vin的一条道路。路长是道路上边的数目，的一条道路。路长是道路上边的数目，vi0到到vin的这条的这条道路上的路长为道路上的路长为n。连通图：对于图中任意两个顶点连通图：对于图中任意两个顶点vi、vjV，vi、vj之间有道之间有道路相连。路相连。网络：带权的连通图。网络：带权的连通图。现在学习的是第6页，共137页3 3隐式图术语隐式图术语 1）子集树 当要求解的问题需要是在当要求解的问题需要是在n n 个元素的子集中进行搜索，其

6、搜索空间树个元素的子集中进行搜索，其搜索空间树被称作子集树。这被称作子集树。这n n个元素都有在子集中或被选取记为个元素都有在子集中或被选取记为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个叶结点的二叉树，对树个叶结点的二叉树，对树中所有分支进行

7、遍历的算法都必须耗时中所有分支进行遍历的算法都必须耗时O（2n）。）。现在学习的是第7页，共137页n=3的子集树的子集树现在学习的是第8页，共137页2）排列树 当当要要求求解解的的问问题题需需要要在在n n 元元素素的的排排列列中中搜搜索索问问题题的的解解时时，解解空空间间树树被称作排列树。被称作排列树。搜索空间为：搜索空间为：（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-1n-1，n n）,（n n，n-1n-1，3 3，2 2，1 1）第一个元素

8、有第一个元素有n种选择，第二个元素有种选择，第二个元素有n-1种选择，第三个元素种选择，第三个元素有有n-2种选择，种选择，第，第n个元素有个元素有1种选择，共计种选择，共计n!个状态。若表示为个状态。若表示为树形就是一个树形就是一个n度树，这样的树有度树，这样的树有n!个叶结点，所以每一个遍历树中个叶结点，所以每一个遍历树中所有节点的算法都必须耗时所有节点的算法都必须耗时O(n!)现在学习的是第9页，共137页图图5-3n=4的部分子集树的部分子集树现在学习的是第10页，共137页4 4图的存储图的存储 邻接矩阵是表示顶点之间相邻关系的矩阵，邻接矩阵是表示顶点之间相邻关系的矩阵，设设G=(V

9、,E)G=(V,E)是具有是具有n n个顶点的图，则个顶点的图，则G G的邻接矩阵可定义为：的邻接矩阵可定义为：Ai,j=1,Ai,j=1,若（若（V Vi i,V,Vj j)或或V 是是E(G)E(G)中的边。中的边。Ai,j=0,Ai,j=0,若若(V(Vi i,V,Vj j)或或V 不是不是E(G)E(G)中的边。中的边。若若G G是网络，则邻接矩阵可定义为：是网络，则邻接矩阵可定义为：Ai,j=W Ai,j=Wijij 若（若（V Vi i,V,Vj j)或或V 属于属于E(G);E(G);Ai,j=0或或若（若（Vi i,Vj j）或）或不属于不属于E(G);其其中中，Wij表表示示

10、边边上上的的权权值值，表表示示一一个个计计算算机机允允许许的的，大大于于所所有有边上权值的数；边上权值的数；1）邻接矩阵法现在学习的是第11页，共137页现在学习的是第12页，共137页2）邻接表 对于图对于图G G中的每个结点中的每个结点V Vi i,把所有邻接于把所有邻接于V Vi i的顶点的顶点V Vj j链成一个单链链成一个单链表，这个单链表就称为顶点表，这个单链表就称为顶点V Vi i的的邻接表邻接表。邻接表邻接表由边表由边表和和顶点表顶点表两部分组成。两部分组成。无向图无向图：V Vi i的邻接表中每个表结点都对应于与的邻接表中每个表结点都对应于与V Vi i相关联的一条边，相关联

11、的一条边，有向图有向图：V Vi i的邻接表中每个表结点对应于的邻接表中每个表结点对应于V Vi i为始点射出的一条为始点射出的一条边。边。现在学习的是第13页，共137页边表边表为一个单链表，每个表结点均有两个域：为一个单链表，每个表结点均有两个域：邻接点域邻接点域adjvexadjvex：存放与：存放与v vi i相邻接的顶点相邻接的顶点v vj j的序号的序号j j。链域链域nextnext：将邻接表的所有表结点链在一起。：将邻接表的所有表结点链在一起。顶点表顶点表为一数组，每个元素均有两个域：为一数组，每个元素均有两个域：顶点域顶点域vertexvertex：存放顶点：存放顶点v vi

12、 i的信息的信息指针域指针域firstedgefirstedge：v vi i的边表的头指针。的边表的头指针。现在学习的是第14页，共137页 二、图搜索及其术语二、图搜索及其术语1 1穷举搜索与启发式搜索穷举搜索与启发式搜索 穷举搜索是对图的最基本的搜索算法，是蛮力策略的一种表现形穷举搜索是对图的最基本的搜索算法，是蛮力策略的一种表现形式。即不考虑给定问题的特有性质，按事先定好的顺序，依次运用规式。即不考虑给定问题的特有性质，按事先定好的顺序，依次运用规则，盲目搜索的方法。则，盲目搜索的方法。启发式搜索是利用一些启发信息，提前判断出先搜索哪些状态可启发式搜索是利用一些启发信息，提前判断出先搜

13、索哪些状态可能尽快找到问题的解或某些情况不可能取到最优解，从而可以提前舍能尽快找到问题的解或某些情况不可能取到最优解，从而可以提前舍弃对这些状态的尝试。即考虑给定问题的特有性质，选用合适的细则，弃对这些状态的尝试。即考虑给定问题的特有性质，选用合适的细则，提高搜索的效率。提高搜索的效率。现在学习的是第15页，共137页2 2相关概念和术语相关概念和术语 问题状态问题状态:树中的每一个结点确定所求解问题的一个问题状态。树中的每一个结点确定所求解问题的一个问题状态。状态空间状态空间:由根结点到其它结点的所有路径（分支），就确定了这个由根结点到其它结点的所有路径（分支），就确定了这个问题的状态空间。

14、问题的状态空间。解状态解状态:是这样一些问题状态是这样一些问题状态S，对于这些问题状态，由根到，对于这些问题状态，由根到S的那条的那条路径确定了这解空间中的一个元组。路径确定了这解空间中的一个元组。答案状态答案状态:是这样的一些解状态是这样的一些解状态S，对于这些解状态而言，由根到，对于这些解状态而言，由根到S的这条路径确定了这问题的一个解的这条路径确定了这问题的一个解状态空间树状态空间树:解空间的树结构又称隐式图。解空间的树结构又称隐式图。现在学习的是第16页，共137页活结点：如果已生成一个结点而它的所有儿子结点还没活结点：如果已生成一个结点而它的所有儿子结点还没有全部生成，则这个结点叫做

15、活结点。有全部生成，则这个结点叫做活结点。E-结点：当前正在生成其儿子结点的活结点叫结点：当前正在生成其儿子结点的活结点叫E-结点（正结点（正扩展的结点）。扩展的结点）。死结点死结点：不再进一步扩展或者其儿子结点已全部生成的：不再进一步扩展或者其儿子结点已全部生成的生成结点就是死结点生成结点就是死结点。现在学习的是第17页，共137页5.2广度优先搜索广度优先搜索 从图中任选一顶点V为起点，首先访问V的所有邻接点W1,W2,Wt,然后再依次访问W1,W2,Wt邻接的所有未曾访问过的顶点。依此类推，直至图中所有和起点V有路径相通的顶点均已被访问为止。现在学习的是第18页，共137页一、算法框架一

16、、算法框架 1 1算法的基本思路算法的基本思路算法设计的基本步骤为算法设计的基本步骤为：1）确定图的存储方式；）确定图的存储方式；2）图的遍历过程中的操作，其中包括为输出）图的遍历过程中的操作，其中包括为输出问题解而进行的存储操作；问题解而进行的存储操作；3 3）输出问题的结论。）输出问题的结论。现在学习的是第19页，共137页2 2算法框架算法框架 1、通过通过E-E-结点扩展出的活结点结点扩展出的活结点2 2、活结点的扩展是按先来先处理的原则进行的、活结点的扩展是按先来先处理的原则进行的抽象地定义：抽象地定义：queuequeue为队列类型，为队列类型，InitQueue()InitQue

17、ue()：队列初始化函数，：队列初始化函数，EnQueue(QEnQueue(Q，k)k)：入队函数，：入队函数，QueueEmpty(Q)QueueEmpty(Q)：判断队空函数，：判断队空函数，DeQueue(Q)DeQueue(Q)：出队函数。：出队函数。visitedvisited：记录结点的搜索情况。：记录结点的搜索情况。现在学习的是第20页，共137页1 1）邻接表表示图的广度优先搜索算法）邻接表表示图的广度优先搜索算法 intvisitedn;/n为结点个数bfs(intk,graphhead)inti；queueQ；edgenode*p；/定义队列InitQueue(Q)；/队

18、列初始化print(“visitvertex”，k)；/访问源点vkvisitedk=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)；/访问vjvisitedp-adjvex=1；EnQueue(Q，p-adjvex)；/访问过的vj人队p=p-next；/找vi的下一邻接点现在学习

19、的是第21页，共137页2 2）邻接矩阵表示的图的广度优先搜索算法）邻接矩阵表示的图的广度优先搜索算法bfsm(intk,graphg100，intn)inti，j；QueueQ；InitQueue(Q)；print(“visitvertex”，k)；/访问源点vkvisitedk=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人队 现在学习的

20、是第22页，共137页【例】如图表示的是从城市【例】如图表示的是从城市A A到城市到城市H H的交通图。从图中的交通图。从图中可以看出，从城市可以看出，从城市A A到城市到城市H H要经过若干个城市。现要找要经过若干个城市。现要找出一条经过城市最少一条路线。出一条经过城市最少一条路线。现在学习的是第23页，共137页算法过程：算法过程：1）将城市A（编号1）入队，队首qh置为0、队尾qe置为1。2）将队首所指的城市所有可直通的城市入队(如果这个城市在队中出现过就不入队),然后将队首加1，得到新的队首城市。重复以上步骤，直到城市H入队为止。当搜到城市H时，搜索结束。3）输出最少城市线路。现在学习

21、的是第24页，共137页数据结构设计：数据结构设计：1）线性数组sq作为活结点队的存储空间。2）队列的每个结点有两个成员：sqi.city记录入队的城市，sqi.pre记录该城市的前趋城市在队列中的下标，这样通过sqi.pre就可以倒推出最短线路。3）设置数组visited记录已搜索过的城市。现在学习的是第25页，共137页算法：算法：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

22、,0,1;structintcity,pre;sq100;intqh,qe,i,visited100;main()inti,n=8;for(i=1;i=n,i=i+1)visitedi=0;search();现在学习的是第26页，共137页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=

23、n,i+)/扩展结点扩展结点 if(jzsqqh.cityi=1 and visitedi=0 if(jzsqqh.cityi=1 and visitedi=0）qe=qe+1;/qe=qe+1;/结点入队结点入队 sqqe.city=i;sqqe.city=i;sqqe.pre=qh;sqqe.pre=qh;visitedqe=1;visitedqe=1;if(sqqe.city=8)out();return;if(sqqe.city=8)out();return;print(“No avaliable way.”);print(“No avaliable way.”);现在学习的是第27页

24、，共137页算法分析：时间复杂度是算法分析：时间复杂度是O（n）；空间复杂性为（）；空间复杂性为（n2），包括图），包括图本身的存储空间和搜索时辅助空间本身的存储空间和搜索时辅助空间“队队”的存储空间。的存储空间。out();/输出路径 print(sqqe.city);while(sqqe.pre0)qe=sqqe.pre;print(-,sqqe.city);现在学习的是第28页，共137页【例】走迷宫问题【例】走迷宫问题 迷宫是许多小方格构成的矩形，在每个小方格中有的是墙（图中的迷宫是许多小方格构成的矩形，在每个小方格中有的是墙（图中的“1 1”）有）有的是路（图中的的是路（图中的“0

25、0”）。走迷宫就是从一个小方格沿上、下、左、右四个方向）。走迷宫就是从一个小方格沿上、下、左、右四个方向到邻近的方格，当然不能穿墙。设迷宫的入口是在左上角到邻近的方格，当然不能穿墙。设迷宫的入口是在左上角(1,1)(1,1)，出口是右下角，出口是右下角(8,8)(8,8)。根据给定的迷宫，找出一条从入口到出口的路径。根据给定的迷宫，找出一条从入口到出口的路径。现在学习的是第29页，共137页算法设计：算法设计：从入口开始广度优先搜索可到达的方格入队，再扩展 队首的方格，直到搜索到出口时算法结束。对于迷宫中任意一点A（Y，X），有四个搜索方向：向上：A（Y-1，X）向下：A（Y+1，X）向左：A

26、（Y，X-1）向右：A（Y，X+1）当对应方格可行（值为0），就扩展为活结点。现在学习的是第30页，共137页数据结构设计：数据结构设计：队队列列：用用数数组组做做存存储储空空间间，有有三三个个成成员员：行行号号、列列号号、前一个方格在队列中的下标。前一个方格在队列中的下标。搜搜索索过过的的方方格格的的记记录录：用用迷迷宫宫原原有有的的存存储储空空间间置置元元素值为素值为“-1”“-1”时，标识已经访问过该方格。时，标识已经访问过该方格。用数组用数组fx=1,-1,0,0fx=1,-1,0,0、fy=0,0,-1,1 fy=0,0,-1,1 模拟上下左模拟上下左右搜索时的下标的变化过程。右搜索

27、时的下标的变化过程。现在学习的是第31页，共137页search()qh=0;qe=1;maze11=-1;sq1.pre=0;sq1.x=1;sq1.y=1;while(qhqe)qh=qh+1;for(k=1;k=4;k+)i=sqqh.x+fxk;j=sqqh.y+fyk;if(check(i,j)=1)qe=qe+1;sqqe.x=i;sqqe.y=j;sqqe.pre=qh;mazeij=-1;if(sqqe.x=8andsqqe.y=8)out();return;print(“Noavaliableway.”);现在学习的是第32页，共137页check(inti,intj)if(

28、i8orj1orj8)return0;if(mazeij=1ormazeij=-1)return0;return1;out()print(“(“,sqqe.x,”,”,sqqe.y,”)”);while(sqqe.pre0)qe=sqqe.pre;print(“(“,sqqe.x,”,”,sqqe.y,”)”);现在学习的是第33页，共137页 首先访问出发点V，并将其标记为已访问过；然后依次从V出发搜索V的每个邻接点W。若W未曾访问过，则以W为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点均已被访问为止。5.3深度优先搜索深度优先搜索现在学习的是第34页，共137页1

29、1算法的基本思路算法的基本思路 1）确定图的存储方式；2）遍历过程中的操作，其中包括为输出问题解而进行的存储操作；3）输出问题的结论。4）一般在回溯前的应该将结点状态恢复为原始状态，特别是在有多解需求的问题中。一、算法框架一、算法框架现在学习的是第35页，共137页int visiten;graph head100；dfs(int k)/head图的顶点数组 edgenode*ptr /ptr图的边表指针 visitedk=1;/记录已遍历过 print(k);ptr=headk.firstedge;/顶点的第一个邻接点 while(ptrNULL)/遍历至链表尾 if(visitedptr-

30、vertex=0)/如没遍历过 dfs(ptr-vertex);/递归遍历 ptr=ptr-nextnode;/下一个顶点 1 1）用邻接表存储图的搜索算法）用邻接表存储图的搜索算法2 2算法框架算法框架现在学习的是第36页，共137页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为新出发点 2 2）邻接矩阵存储图的搜索算法）邻接矩阵存储图的搜索算法现在学习的是第37

31、页，共137页【例】走迷宫问题深度优先搜索，就是一直向着可通行的下一个方格行进，直到搜索到出口就找到一个解。若行不通时，则返回上一个方格，继续搜索其它方向。算法设计：算法设计：现在学习的是第38页，共137页用迷宫本身的存储空间除了记录走过的信息，还要标识是否可行：mazeij=3 标识走过的方格；mazeij=2 标识走入死胡同的方格，这样，最后存储为“3”的方格为可行的方格。而当一个方格四个方向都搜索完还没有走到出口，说明该方格或无路可走或只能走入了“死胡同”。数据结构设计：数据结构设计：现在学习的是第39页，共137页int maze88=0,0,0,0,0,0,0,0,0,1,1,1,

32、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;int 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);/统计总步数算法：算法：现在学习的是第40页，共137页search(int i,int j)int k,newi,newj;for(k=1;k=4;

33、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;/某一方格只能走入死胡同现在学习的是第41页，共137页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(“*”);现在学习的是第42页，共137页check(int i,

34、int j,int k)i=i+fxk;j=j+fyk;if(i8 or j8)return 0;if(mazeij0)return 0;return 1;现在学习的是第43页，共137页1）和广度优先算法一样每个方格有四个方向可以进行搜索，这样一个结点（方格）就可多次成为“活结点”，而在广度优先算法一个结点（方格）就可一次成为“活结点”，一出队就成了死结点。2）用广度优先算法，搜索出的是一条最短的路径，而用深度优先搜索则只能找出一条可行的路径，而不能保证是最短的路径。3）在空间效率上二者相近。都需要辅助空间。算法说明：算法说明：现在学习的是第44页，共137页【例】有如图所示的七巧板，试编写

35、一源程序如下，使用至多四种不同颜色对七巧板进行涂色(每块涂一种颜色)，要求相邻区域的颜色互不相同，打印输出所有可能的涂色方案。现在学习的是第45页，共137页 为了让算法能识别不同区域间的相邻关系，将七巧板上每一个区域看成一个顶点若两个区域相邻，则相应的顶点间用一条边相连，这样该问题就转化为图一个图的搜索问题了。图的存储采用邻接矩阵。问题分析：问题分析：0 1 0 0 1 0 11 0 0 1 0 1 00 0 0 0 0 1 10 1 0 0 0 1 11 0 0 0 0 0 10 1 1 1 0 0 01 0 1 1 1 0 0现在学习的是第46页，共137页int data77,n,co

36、lor7,total;main()int i,j;for(i=1;i=n;i+)for(j=1;j=n;j+)input(dataij);for(j=1;j7)output();else for(i=1;i=4;i+)colors=i;if(colorsame(s)=0)try(s+1);现在学习的是第48页，共137页output()int i,;print(换行符，serial number：,total);for(i=1;i=n;i+)print(colori);total=total+1;colorsame(int s)/判断相邻点是否同色 int i,flag;flag=0;for(

37、i=1;i=s-1;i+)if(datais=1 and colori=colors)flag=1;return(flag);现在学习的是第49页，共137页5.4回溯法回溯法 回回溯溯算算法法实实际际是是一一个个类类似似枚枚举举的的搜搜索索尝尝试试方方法法，它它的的主主题题思思想想是是在在搜搜索索尝尝试试中中找找问问题题的的解解，当当不不满满足足求求解解条条件件就就”回回溯溯”返返回回，尝尝试试别别的的路路径径。回回溯溯算算法法是是尝尝试试搜搜索索算算法法中中最最为为基基本本的的一一种种算法，其采用了一种算法，其采用了一种“走不通就掉头走不通就掉头”的思想，作为其控制结构。的思想，作为其控制

38、结构。现在学习的是第50页，共137页【例】八皇后问题：要在8*8的国际象棋棋盘中放八个皇后，使任意两个皇后都不能互相吃掉。规则：皇后能吃掉同一行、同一列、同一对角线的任意棋子。下图为一种方案，求所有的解。一、认识回溯法一、认识回溯法现在学习的是第51页，共137页 设八个皇后为xi（i=1，2，3，4，8）分别在第i行。问题的解空间：八个皇后所在列的序号（x1,x2,x3,x4,x5,x6,x7,x8）搜索空间：1xi8（i=1，2，3，4，8），共88个状态。约束条件：1、不在同一列：xixj 2、不在同一主对角线上：xi-ixj-j 3、不在同一负对角线上：xi+ixj+j 2、3可合并

39、为：abs(xi-xj)abs(i-j)问题分析：问题分析：现在学习的是第52页，共137页加约束条件的枚举算法：main()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）contin

40、ue;现在学习的是第53页，共137页 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);现在学习的是第54页，共137页check(int a,int n)int i;for(i=1;i0)ak=ak+1;while(ak=n)and(check(k)=0)ak=ak+1;if(ak=n)if(k=n)output(n);else k=k+1;ak=0;else k=k-1;/回溯 现在学习的是第57页，共137

41、页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 n)int i;for(i=1;i=n;i+)print(ai);现在学习的是第58页，共137页 用三个数组c,b,d分别记录棋盘上的n个列、n个主对角线和n个负对角线的占用情况。以四阶棋盘为例，共有2n-1=7个主对角线，对应地也有7个负对角线。四皇后棋盘示意图递归算法递归算法:现在学习的是第59页，共137页用i，j分别表示皇后所在的行列，列：列：范围1-n主对角线：主对角线：行列下标的差一样

42、，若用表达式i-j编号，则范围为-n+1n-1，使用i-j+n对主对角线编号，范围就是12n-1。负对角线：负对角线：行列下标的和一样，用表达式i+j编号，则范围为22n。现在学习的是第60页，共137页int a20,b20,c40,d40;int n,t，i,j,k;/t记录解的个数main()int i,input(n);for(i=1;i=n;i+)bi=0;ci=0;cn+i=0;di=0;dn+i=0;try（1）;现在学习的是第61页，共137页try(int i)int j;for(j=1;j=n;j+)/第i个皇后有n种可能位置 if(bj=0)and(ci+j=0)and(

43、di-j+n=0)ai=j;/摆放皇后 bj=1;/占领第j列 ci+j=1;di-j+n=1;/占领两个对角线 if(i8)try(i+1);/递归摆放下一皇后 else output();/完成任务，打印结果 bj=0;ci+j=0;di-j+n=0;/回溯 现在学习的是第62页，共137页output()t=t+1;print(t,);for(k=1;k0(有路可走)and(未达到目标)/还未回溯到头 if(in)/正在处理第i个元素 搜索到一个解，输出;else ai第一个可能的值；while(ai在不满足约束条件 且 在在搜索空间内)ai下一个可能的值；if(ai在搜索空间内)标识占

44、用的资源;i=i+1;/扩展下一个结点 else 清理所占的状态空间；i=i-1;/回溯 2）非递归回溯框架现在学习的是第70页，共137页int an;try(int i)if（in）输出结果;else for(j=下界;jn or xm or x1 or y1)print(x,y error!);return;for(i=1;i=;i+)for(j=1;j=;j+)aij=0;axy=1;find(x,y,2);if(count=0)print(“No answer!”);else print(“count=!”,count);现在学习的是第76页，共137页find(int y,int

45、x,int dep)int i,xx,yy;for i=1 to 8 do /加上方向增量,形成新的坐标 xx=x+fxi;yy=y+fyi;if(check(xx,yy)=1)/判断新坐标是否出界,是否已走 axxyy=dep;/走向新的坐标 if(dep=n*m)output();else find(xx,yy,dep+1);/从新坐标出发,递归下一层 axxyy=0;/回溯,恢复未走标志/现在学习的是第77页，共137页output（）count=count+1;print(“换行符”);print(count=,count);for(y=1;y=n;y+)print(“换行符”);fo

46、r(x=1;x=m;x+)print(ayx);现在学习的是第78页，共137页【例】素数环问题：把从1到20这20个数摆成一个环，要求相邻的两个数的和是一个素数。尝试搜索从1开始，每个空位有220共19种可能，约束条件就是填进去的数满足：与前面的数不相同；与前面相邻数据的和是一个素数。第20个数还要判断和第1个数的和是否素数。现在学习的是第79页，共137页main()int a20,k;for(k=1;k=20;k+)ak=0;a1=1;try(2);算法：算法：现在学习的是第80页，共137页try(int i)int k;for(k=2;k=20;k+)if(check1(k,i)=1

47、 and check3(k,i)=1)ai=k;if(i=20)output();else try(i+1);ai=0;现在学习的是第81页，共137页check1(int j,int i)int k;for(k=1;k=i-1;k+)if(ak=j)return(0);return(1);check2(int x)int k,n;n=sqrt(x);for(k=2;k=n;k+)if(x mod k=0)return(0);return(1);现在学习的是第82页，共137页check3(int j,int i)if(i20)return(check2(j+ai-1);else return

48、(check2(j+ai-1)and check2(j+a1);output()int k;for(k=1;k=20;k+)print(ak);print(“换行符”);现在学习的是第83页，共137页【例】输出自然数1到n所有不重复的排列，即n的全排列 n的全排列是一组n元一维向量:（x1，x2，x3，xn），搜索空间是：1xin i=1，2，3，n,约束条件很简单，xi互不相同。现在学习的是第84页，共137页int p=0,n,a100,d100;main()int j,n,print(Input n=);input(n);for(j=1;j=n;j+)dj=0;try(1);算法算法1

49、 1：现在学习的是第85页，共137页try(int k)int j;for(j=1;j=n;j+)if(dj0)continue;ak=j;dj=1;if(kn)try(k+1);else p=p+1;output(k);dak=0;现在学习的是第86页，共137页output()int j;print(p,”:”)for(j=1;j=n;j+)print(aj);print(“换行符”);现在学习的是第87页，共137页算法算法2:2:搜索排列树搜索排列树 根据全排列的概念，定义数组初始值为（1，2，3，4，n），这是全排列中的一种，然后通过数据间的交换，则可产生所有的不同排列。现在学习的

50、是第88页，共137页int a100,n,s=0;main()int i,;input(n);for(i=1;in)output();else for(j=t;j=n;j+)swap(t,j);try(t+1);swap(t,j);/回溯时，恢复原来的排列 现在学习的是第90页，共137页output()int j;printf(n);for(j=1;j=n就认为找到了更大的解，in不必解释位数多数据一定大；i=n时，由于尝试是由小到大进行的，位数相等时后来满足条件的现在学习的是第95页，共137页 main()int A101,B101;int i,j,k,n,r；A1=1;for(i=2