启发式图搜索ppt课件精品PPT课件.pptx

启发式搜索定义:为减小搜索范围而需要利用某些已知的、有关具体问题领域的特性信息。此种信息叫做启发信息。利用启发信息的搜索方法叫做启发式搜索方法。特点:重排OPEN表,选择最有希望的节点加以扩展种类:最佳优先搜索、A*算法等启发式搜索策略有关具体问题领域的信息常常可以用来简化搜索。一个比较灵活(但代价也较大)的利用启发信息的方法是应用某些准则来重新排列每一步OPEN表中所有节点的顺序。然后,搜索就可能沿着某个被认为是最有希望的边缘区段向外扩展。应用这种排序过程,需要某些估算节点“希望”的量度,这种量度叫做估价函数(evalutionfunction)估价函数为获得某些节点“希望”的启发信息,提供一个评定侯选扩展节点的方法,以便确定哪个节点最有可能在通向目标的最佳路径上。f(n)——表示节点n的估价函数值建立估价函数的一般方法:试图确定一个处在最佳路径上的节点的概率;提出任意节点与目标集之间的距离量度或差别量度;或者在棋盘式的博弈和难题中根据棋局的某些特点来决定棋局的得分数。这些特点被认为与向目标节点前进一步的希望程度有关。应用节点“希望”程度(估价函数值)重排OPEN表。登山法和最佳优先搜索登山法的引入瞎子在山上某点,想要爬到山顶,怎么办?从立足处用明杖向前一试,觉得高些,就向前一步,如果前面不高,向左一试,高就向左一步,不高再试后面,高就退一步,不高再试右面,高就向右走一步,四面都不高,,高了就走一步,就这样一步一步地走,就走上了山顶。这个向各方向的测试“步”,就是“登山法”的估价函数f(n)。登山法算法步骤:设定初始节点n;如果n是目标,则成功退出;扩展n,得到其子节点集合;从该集合中选取f(n)为最小的节点n’;将n’设为n,返回第②步。最佳优先搜索算法是“登山法”的推广,但它是对OPEN表中所有节点的f(n)进行比较,按从小到大的顺序重排OPEN表。其算法效率类似于纵向搜索算法,但使用了与问题特性相关的估价函数来确定下一步待扩展的节点,因此是一种启发式搜索方法。开始把S放入OPEN表,计算估价函数f(s)OPEN表为空表?把OPEN表中的第一个节点n放入CLOSED表n为目标节点吗?扩展n,计算所有子节点的估价函数值,并提供它们返回节点n的指针。失败成功最佳优先搜索算法框图是否是否把子节点送入OPEN表,并对其中的所有节点按估价函数值由小到大重排。迷宫问题如下,F是入口,B是出口,试采用最佳优先搜索算法进行求解。举例:迷宫问题0123x123yFGHECADB22241111解:估价函数f(n)采用每个节点与目标节点在坐标系上的距离来表示。例如,E点与目标节点B之间的空间距离是2+2=4,两个2分别是E与B在x轴及y轴上的距离。