第二章 基于搜索的问题求解之应用智能的搜索

《第二章 基于搜索的问题求解之应用智能的搜索》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、§2.3应用智能的搜索启发式搜索初始节点S0目标节点Sg定义：为减小搜索范围而需要利用某些已知的、有关具体问题领域的特性信息。此种信息叫做启发信息。利用启发信息的搜索方法叫做启发式搜索方法。特点：重排OPEN表，选择最有希望的节点加以扩展种类：最佳优先搜索、A*算法等启发式搜索策略有关具体问题领域的信息常常可以用来简化搜索。一个比较灵活(但代价也较大)的利用启发信息的方法是应用某些准则来重新排列每一步OPEN表中所有节点的顺序。然后，搜索就可能沿着某个被认为是最有希望的边缘区段向外扩展。应用这种排序过程，需要某些估算节点“希望”的量度，这种量度叫做估价函数

2、(evalutionfunction)估价函数为获得某些节点“希望”的启发信息，提供一个评定侯选扩展节点的方法，以便确定哪个节点最有可能在通向目标的最佳路径上。f(n)——表示节点n的估价函数值建立估价函数的一般方法：试图确定一个处在最佳路径上的节点的概率；提出任意节点与目标集之间的距离量度或差别量度；或者在棋盘式的博弈和难题中根据棋局的某些特点来决定棋局的得分数。这些特点被认为与向目标节点前进一步的希望程度有关。应用节点“希望”程度（估价函数值）重排OPEN表。登山法和最佳优先搜索登山法的引入瞎子在山上某点，想要爬到山顶，怎么办？从立足处用明杖向前一试，

3、觉得高些，就向前一步，如果前面不高，向左一试，高就向左一步，不高再试后面，高就退一步，不高再试右面，高就向右走一步，四面都不高，就原地不动.总之，高了就走一步，就这样一步一步地走，就走上了山顶。这个向各方向的测试“步”，就是“登山法”的估价函数f(n)。登山法算法步骤：设定初始节点n；如果n是目标，则成功退出；扩展n，得到其子节点集合；从该集合中选取f(n)为最小的节点n’；将n’设为n，返回第②步。最佳优先搜索算法是“登山法”的推广，但它是对OPEN表中所有节点的f(n)进行比较，按从小到大的顺序重排OPEN表。其算法效率类似于纵向搜索算法，但使用了与问

4、题特性相关的估价函数来确定下一步待扩展的节点，因此是一种启发式搜索方法。开始把S放入OPEN表，计算估价函数f(s)OPEN表为空表？把OPEN表中的第一个节点n放入CLOSED表n为目标节点吗？扩展n，计算所有子节点的估价函数值，并提供它们返回节点n的指针。失败成功最佳优先搜索算法框图是否是否把子节点送入OPEN表，并对其中的所有节点按估价函数值由小到大重排。迷宫问题如下，F是入口，B是出口，试采用最佳优先搜索算法进行求解。举例：迷宫问题0123x123yFGHECADB22241111解：估价函数f(n)采用每个节点与目标节点在坐标系上的曼哈顿距离来表

5、示。例如，E点与目标节点B之间的距离是2+2=4，两个2分别是E与B在x轴及y轴上的距离。将初始点F及其估价函数值6放入OPEN表，然后取出，判断其是否为目标，若为否时，将其放入CLOSED表，对其进行子节点扩展，并计算其相应的估价函数值，得OPEN和CLOSED表。节点号父节点号G(5)F(6)OPEN表CLOSED表编号节点号父节点号(1)F(6)空接着，判断此时的OPEN表是否为空，若不是，则将OPEN表上的第一个节点G提出来，判断其是否为目标，若不是，则将其放入CLOSED表中，并对其进行扩展，得到的子节点及其估价函数值，按递减的顺序加入OPEN表

6、，如下节点号父节点号H(3)G(5)E(4)G(5)OPEN表CLOSED表编号节点号父节点号(1)F(6)空(2)G(5)F(6)……………取OPEN表上的第一个节点H，判断其是否为目标，若不是，则将其放入CLOSED表，并对其进行扩展.由于其没有子节点，因此没有新的子节点加入OPEN表，如下节点号父节点号E(4)G(5)OPEN表CLOSED表编号节点号父节点号(1)F(6)空(2)G(5)F(6)(3)H(3)G(5)……………再取OPEN表最上端的节点E，判断其是否为目标，若不是，则将其放入CLOSED表，并对其进行扩展，将其子节点加入OPEN表，

7、按估价函数值递减的顺序重排OPEN表，如下OPEN表CLOSED表节点号父节点号A(2)E(4)C(3)E(4)编号节点号父节点号(1)F(6)空(2)G(5)F(6)(3)H(3)G(5)(4)E(4)G(5)……………取OPEN表最上端的节点A，判断其是否为目标，若不是，则将其放入CLOSED表，并对其进行扩展，其子节点及估价函数值加入OPEN表，并按递减的顺序重新排序，如下OPEN表CLOSED表节点号父节点号B(0)A(2)C(3)E(4)编号节点号父节点号(1)F(6)空(2)G(5)F(6)(3)H(3)G(5)(4)E(4)G(5)(5)A(

8、2)E(4)……………对OPEN表最上端的节点B，判断其是否为目标