盲目搜索启发式搜索.ppt

《盲目搜索启发式搜索.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、1盲目搜索按预定的控制策略进行搜索，在搜索过程中获得的中间信息不用来改进控制策略。效率低、主要用于简单问题求解。启发式搜索在搜索中加入了与问题有关的启发性信息，用以指导搜索朝着最有希望的方向前进，加速问题的求解过程并找到最优解。搜索原理什么是搜索？根据问题的实际情况不断寻找可利用的知识，从而构造一条代价较少的推理路线，使问题得到圆满解决的过程。与图有关的术语状态空间图——由节点(不一定是有限的节点)及连接节点的分枝的集合构成。有限节点图——节点数目有限的图称为有限节点图。有向图——一对节点用分枝线连接起来，从一个节点指向另一个节点。这

2、种图叫做有向图。始节点叫父节点或双亲节点，终节点叫子节点。扩展——求解父节点的所有子节点，叫做扩展。路径——在一系列节点n1,n2,,nm中，从n1开始，ni总有分枝连接ni+1，称从n1到nm之间的分枝集合是路径。路径中不包含两个及以上相同的分枝，如果n1和nm是同一个节点，则称这种路径为闭路。不构成闭路的称为树。在用状态空间图来表示问题时，对问题的求解就是求出从初始节点到目标节点的路径。图搜索策略1.图搜索的定义——一种计算机在状态图中寻找路径的方法。2.CLOSED表的引入编号节点号父节点号CLOSED表(记录扩展过的节点)

3、OPEN表的引入节点号父节点号OPEN表(记录待扩展的节点)举例：八数码魔方例子中OPEN表变化过程节点号父节点号S0空AS0BS0CS0DS0EAFACLOSED表变化过程编号节点号父节点号0S0空1AS02BS0图搜索的一般过程(1)建立一个只含有起始节点S的搜索图G，把S放到一个叫做OPEN表的未扩展节点表中。(2)建立一个叫做CLOSED的已扩展节点表，其初始为空表。(3)LOOP：若OPEN表是空表，则失败退出。(4)选择OPEN表上的第一个节点，把它从OPEN表移出并放进CLOSED表中。称此节点为节点n。(5)若

4、n为一目标节点，则有解并成功退出，此解是追踪图G中沿着指针从n到S这条路径而得到的(指针将在第7步中设置)。图搜索的一般过程(6)扩展节点n，同时生成不是n的祖先的那些后继节点的集合M。把M的这些成员作为n的后继节点添入图G中。(7)对那些未曾在G中出现过的(既未曾在OPEN表上或CLOSED表上出现过的)M成员设置一个通向n的指针。把M的这些成员加进OPEN表。对已经在OPEN或CLOSED表上的每一个M成员，确定是否需要更改通到n的指针方向。对已在CLOSED表上的每个M成员，确定是否需要更改图G中通向它的每个后裔节点的指针方向。

5、(8)按某一任意方式或按某个探试值，重排OPEN表。(9)GOLOOP。开始把S放入OPEN表OPEN表为空表？把第一个节点(n)从OPEN表移至CLOSED表n为目标节点吗？把n的后继节点放入OPEN表的末端，提供返回节点n的指针修改指针方向重排OPEN表失败成功图搜索一般过程的框图是是否否13一、盲目搜索盲目搜索又叫做无信息搜索，一般只适用于求解比较简单的问题。主要包括宽度优先搜索、等深度优先搜索等。特点：1）搜索按规定的路线进行，不使用与问题有关的启发性信息。2）适用于其状态空间图是树状结构的一类问题。141、宽度优先搜索定义：

6、如果搜索是以接近起始节点的程度依次扩展节点的，那么这种搜索就叫做宽度优先搜索(breadth-firstsearch)。基本思想：从初始节点S开始，逐层地对节点进行扩展并考察它是否为目标节点，在第n层的节点没有全部扩展并考察之前，不对第n＋1层的节点进行扩展。OPEN表中的节点总是按进入的先后顺序排列，先进入的节点排在前面，后进入的排在后面。15宽度优先搜索示意图2021/8/1016宽度优先搜索算法：(1)把起始节点放到OPEN表中(如果该起始节点为一目标节点，则求得一个解答)。(2)如果OPEN是个空表，则没有解，失败退出；否则继

7、续。(3)把第一个节点(节点n)从OPEN表移出，并把它放入CLOSED扩展节点表中。(4)扩展节点n。如果没有后继节点，则转向上述第(2)步。(5)把n的所有后继节点放到OPEN表的末端，并提供从这些后继节点回到n的指针。(6)如果n的任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向第(2)步。17宽度优先搜索算法框图18宽度优先搜索方法分析：宽度优先搜索是图搜索一般过程的特殊情况，将图搜索一般过程中的第8步具体化为本算法中的第6步，这实际是将OPEN表作为“先进先出”的队列进行操作。宽度优先搜索方法能够保证在搜索树中

8、找到一条通向目标节点的最短途径；这棵搜索树提供了所有存在的路径(如果没有路径存在，那么对有限图来说，就说该法失败退出；对于无限图来说，则永远不会终止)。19例如：宽度优先搜索用于八数码难题。这个问题就是要把初始棋局变为如