第5章(5.1 穷举、5.2 广度、深度优先搜索)(精品).ppt

《第5章(5.1 穷举、5.2 广度、深度优先搜索)(精品).ppt》由会员分享，可在线阅读，更多相关《第5章(5.1 穷举、5.2 广度、深度优先搜索)(精品).ppt（20页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第五章第五章 搜索算法搜索算法 搜搜索索算算法法：是是利利用用计计算算机机的的高高性性能能来来有有目目的的地地枚枚举举一一个个问问题题的的部部分分或或所所有有可可能能情情况况，从从而而找找到到解解决决问问题的一种方法。题的一种方法。该该方方法法策策略略的的适适应应性性很很强强，只只要要问问题题有有解解，它它肯肯定定能将其解找到；但其搜索效率不是太好。能将其解找到；但其搜索效率不是太好。5.1 穷举搜索穷举搜索穷举搜索穷举搜索是最基本的搜索算法，是是最基本的搜索算法，是蛮力策略蛮力策略的一种表的一种表现形式。现形式。（蛮力策略有（蛮力策略有2种表现形式：枚举法，穷举搜索；）种表现形式：枚举法，穷

2、举搜索；）穷举搜索基本思想：穷举搜索基本思想：针对问题的可能解是有限种的情况，逐一检查所有针对问题的可能解是有限种的情况，逐一检查所有可能的情况，从中找到问题真正的解。可能的情况，从中找到问题真正的解。例例51：给定一个有向带权图给定一个有向带权图G=(V，E)，权非负，如图，权非负，如图5-1所示。找出顶点所示。找出顶点15的最短路径及其长度。的最短路径及其长度。问题分析问题分析该问题所有可能的路径只有三条，分别是：该问题所有可能的路径只有三条，分别是：12451345145采用穷举搜索的方法采用穷举搜索的方法逐一检查这三条路径的长度逐一检查这三条路径的长度。最短路径为最短路径为1245，其

3、长度为，其长度为3。例例52 给定一艘船和三个集装箱，船的载重为给定一艘船和三个集装箱，船的载重为10，三个集，三个集装箱的重量分别为装箱的重量分别为5，8，3。在体积不受限制的情况。在体积不受限制的情况下，如何将尽可能多的集装箱装上船？下，如何将尽可能多的集装箱装上船？问题分析：问题分析：每个集装箱要么装上船，要么不装；每个集装箱要么装上船，要么不装；0表示不装，表示不装，1表示装；表示装；则问题的所有可能解可以用则问题的所有可能解可以用8个个3元元01向量表示：向量表示：即即(0,0,0)、(0,0,1)、(0,1,0)、(0,1,1)、(1,0,0)、(1,0,1)(1,1,0)、(1,

4、1,1)采用采用穷举搜索的方法逐一检查穷举搜索的方法逐一检查容易得出问题的解容易得出问题的解(1,0,1)利用搜索法解题时，需要把问题的所有可能的解（利用搜索法解题时，需要把问题的所有可能的解（解解空间空间）描述出来，如何描述问题的所有可能解？）描述出来，如何描述问题的所有可能解？解空间通常有解空间通常有2 2表示形式：表示形式：1)1)子集树子集树 2 2）排列树）排列树1）子集树）子集树 当要求解的问题需要是在当要求解的问题需要是在n n 个元素的子集中进行搜索，其搜索个元素的子集中进行搜索，其搜索空间树被称作空间树被称作子集树子集树（subset treesubset tree）。某个元

5、素某个元素xi=xi=1 1表示该元素表示该元素在在要找的子集中，要找的子集中，xi=0 xi=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 个状态。个状态。如如例例52若表示为树形结构就是一棵有若表示为树形结构就是一棵有2n个叶结点的二叉树，个叶结点的二叉树，对树中所有分支进行遍历的算法都必须耗对树中所有分支进行遍历的算法都必须耗

6、O(2n).下图就是一个下图就是一个n3时的子集树时的子集树：树的树的根节点根节点表示初始状态；表示初始状态；中间节点中间节点表示某种情况下的表示某种情况下的中间状态；中间状态；叶子节点叶子节点表示结束状态；表示结束状态；从根节点到叶子节点的路径表示一个可能的解。从根节点到叶子节点的路径表示一个可能的解。2）排列树）排列树 当当要要求求解解的的问问题题需需要要在在n n 元元素素的的排排列列中中搜搜索索问问题题的的解解时时，相相应的解空间树被称作应的解空间树被称作排列树排列树（permutation treepermutation tree）。）。搜索空间为：搜索空间为：（1 1，2 2，3

7、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）第一个元素有第一个元素有n种选择，第二个元素有种选择，第二个元素有n-1种选择，第三个元种选择，第三个元素有素有n-2种选择，种选择，第，第n个元素有个元素有1种选择，共计种选择，共计n!个状态个状态。若表示为树形就是一个若表示为树形就是一个n度树度树，这样的树有，这样的树有n!个叶结点个叶结点，所以每，所以每一个遍历树中所有节点的算法都必须耗时一个遍历树中所有节

8、点的算法都必须耗时O(n!)下图为下图为n=4时的排列树时的排列树；图图5-3 n=4的的部分子集树部分子集树 补充：补充：广度优先搜索（自学）广度优先搜索（自学）1、算法的基本思想、算法的基本思想首先，构造问题的解空间；首先，构造问题的解空间；然然后后，从从初初始始节节点点S0开开始始，逐逐层层地地对对节节点点进进行行扩扩展展并并考察它是否为目标节点。考察它是否为目标节点。在在第第n层层的的节节点点没没有有全全部部扩扩展展并并考考察察之之前前，不不对对第第n+1层的节点进行扩展层的节点进行扩展。2 2、算法分析与描述、算法分析与描述 从从广度优先搜索定义可以看出活结点的扩展是按广度优先搜索定

9、义可以看出活结点的扩展是按先来先处先来先处理的原则进行的理的原则进行的，所以在算法中要用，所以在算法中要用“队队”来存储每个来存储每个E-E-结点结点扩展出的活结点。为了算法的简洁，抽象地定义：扩展出的活结点。为了算法的简洁，抽象地定义：queuequeue为队列类型，为队列类型，InitQueueInitQueue()()为队列初始化函数，为队列初始化函数，EnQueue(QEnQueue(Q，k)k)为入队函数，为入队函数，QueueEmpty(QQueueEmpty(Q)为判断队空函数，为判断队空函数，DeQueue(QDeQueue(Q)为出队函数。为出队函数。实际应用中，用数组或链表

10、实现队列。实际应用中，用数组或链表实现队列。开辟数组开辟数组visitedvisited记录记录visitedvisited结点的搜索情况。结点的搜索情况。在算法框架中以输出结点值表示在算法框架中以输出结点值表示“访问访问”。1 1）邻接表表示图的广度优先搜索算法）邻接表表示图的广度优先搜索算法 intvisitedn;/n visitedn;/n 为结点个数为结点个数/bfs(intk,graphhead)inti；queueQ；edgenode*p；/定义队列定义队列/InitQueue(Q)；/队列初始化队列初始化/print(“visitvertex”，k)；/访问源点访问源点vk/v

11、isitedk=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-n

12、ext；/找找vi的下一邻接点的下一邻接点/2）邻接矩阵表示的图的广度优先搜索算法）邻接矩阵表示的图的广度优先搜索算法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(

13、Q，j)；/访问过的访问过的vj人队人队/【例例】已知若干个城市的地图，求从一个城市到另一个城市已知若干个城市的地图，求从一个城市到另一个城市的路径，要求路径中经过的城市最少。的路径，要求路径中经过的城市最少。如下图表示的是从城市如下图表示的是从城市A到城市到城市H的交通图。从图中可的交通图。从图中可以看出，从城市以看出，从城市A到城市到城市H要经过若干个城市。现要找要经过若干个城市。现要找出一条经过城市最少一条路线。出一条经过城市最少一条路线。图5-6 具体过程如下：具体过程如下：1 1）将城市将城市A A（编号编号1 1）入队，队首）入队，队首qhqh置为置为0 0、队尾、队尾qeqe置为

14、置为1 1。2 2）将队首所指的城市所有可直通的城市入队）将队首所指的城市所有可直通的城市入队(如果如果这个城市在队中出现过就不入队这个城市在队中出现过就不入队),),然后将队首加然后将队首加1 1，得到新的队首城市。重复以上步骤，直到城市得到新的队首城市。重复以上步骤，直到城市H H入队入队为止。当搜到城市为止。当搜到城市H H时，搜索结束。时，搜索结束。3）输出最少城市线路）输出最少城市线路。算法描述如下：算法描述如下：search()()qhqh=0;=0;qeqe=1;sq1.city=1;sq1.pre=0;visited1=1;=1;sq1.city=1;sq1.pre=0;vis

15、ited1=1;while(while(qhqhqeqe)/)/当队不空当队不空/qhqh=qh+1;/=qh+1;/结点出队结点出队/for(i=1;i=n,i+)/for(i=1;i=n,i+)/扩展结点扩展结点/if if（jzsqqh.cityijzsqqh.cityi=1 and visitedi=0=1 and visitedi=0）qeqe=qe+1;/=qe+1;/结点入队结点入队/sqqe.citysqqe.city=i;sqqe.prei;sqqe.pre=qh;visitedqeqh;visitedqe=1;=1;if(if(sqqe.citysqqe.city=8)ou

16、t();=8)out();printprint(“No No avaliableavaliable way.way.”););out();/out();/输出路径输出路径/print(sqqe.cityprint(sqqe.city););while(sqqe.prewhile(sqqe.pre0)0)qe=sqqe.pre;print(-,sqqe.city);1、算法的基本思想、算法的基本思想首先首先，构造问题的解空间；，构造问题的解空间；然后然后，从初始节点，从初始节点S0开始，在其子节点中选择一个开始，在其子节点中选择一个节点进行考察。若不是目标节点，则再在该子节点的节点进行考察。若不

17、是目标节点，则再在该子节点的子节点中选择一个节点进行考察，一直如此向下搜索。子节点中选择一个节点进行考察，一直如此向下搜索。当达到某个子节点，且该子节点既不是目标节点，又当达到某个子节点，且该子节点既不是目标节点，又不能继续扩展时，才选择其兄弟节点进行考察。不能继续扩展时，才选择其兄弟节点进行考察。5.2 5.2 深度优先搜索（自学）深度优先搜索（自学）例例54：给定一个有向图给定一个有向图G=(V，E)，如图，如图5-2所示。给出深所示。给出深度优先搜索该图的一个访问序列。度优先搜索该图的一个访问序列。输出一个深度优先搜索序列：输出一个深度优先搜索序列：1,2,5,3,4,6,7 算法描述：

18、算法描述：/标记图中顶点是否被访问过标记图中顶点是否被访问过bool Visitedn+1;for（int i=1;i=n;i+）Visitedi=0;/用用0表示顶点未被访问过表示顶点未被访问过/从顶点从顶点k出发进行深度优先搜索出发进行深度优先搜索Dfsk(int k)Visitedk=1；/标记顶点标记顶点k已被访问过已被访问过for(int j=1;j=n;j+)if(ckj=1&Visitedj=0)/c是图是图G对应的邻接矩阵对应的邻接矩阵 Dfsk(j);/深度优先搜索整个图深度优先搜索整个图GDfs()for(int i=1;i=n;i+)if(Visitedi=0)Dfsk(

19、i);深度优先搜索与广度优先搜索比较：深度优先搜索与广度优先搜索比较：相似：相似：最终都要扩展一个结点的所有子结点。最终都要扩展一个结点的所有子结点。区别：区别：在于对扩展结点过程在于对扩展结点过程，深度搜索深度搜索扩展的是扩展的是E-E-结点的邻结点的邻接结点中的一个，并将其作为新的接结点中的一个，并将其作为新的E-E-结点继续扩展，结点继续扩展，当前当前E-E-结点仍为活结点，待结点仍为活结点，待搜索完其子结点后搜索完其子结点后，回溯回溯到该结点扩展它的其它未搜索的邻接结点到该结点扩展它的其它未搜索的邻接结点。而而广度搜索广度搜索，逐层逐层地对节点进行扩展并考察它是否为地对节点进行扩展并考察它是否为目标节点。目标节点。