1.4 启发式图搜索1.启发式搜索 定义：为减小搜索范围而需要利用 某些已知的、有关具体问题领域的特 性信息。此种信息叫做启发信息。利 用启发信息的搜索方法叫做启发式搜 索方法。 特点：重排OPEN 表，选择最有希望 的节点加以扩展 种类：最佳优先搜索、A * 算法等启发式搜索策略 有关具体问题领域的信息常常可以用 来简化搜索。一个比较灵活( 但代价也 较大) 的利用启发信息的方法是应用某 些准则来重新排列每一步OPEN 表中 所有节点的顺序。然后，搜索就可能 沿着某个被认为是最有希望的边缘区 段向外扩展。应用这种排序过程，需 要某些估算节点“ 希望” 的量度，这种 量度叫做估价函数(evalution function) 估价函数 为获得某些节点“ 希望” 的启发信息 ，提供一个评定侯选扩展节点的方法， 以便确定哪个节点最有可能在通向目标 的最佳路径上 。 f(n) 表示节点n 的估价函数值 建立估价函数的一般方法： 试图确定一个处在最佳路径上的节点的 概率；提出任意节点与目标集之间的 距离量度或差别量度；或者在棋盘式 的博弈和难题中根据棋局的某些特点 来决定棋局的得分数。这些特点被
