启发式搜索

一般需要某些有关具体问题的领域的特性信息,把此种信息叫做启发信息。

需定义一个评价函数，对当前的搜索状态进行评估，找出一个最有希望的节点来扩展。

重排OPEN表,选择最有希望的节点加以扩展

一、A算法

1

 2局部择优搜索(瞎子爬山法)

搜索过程如下:

(1) 把初始节点S0放入OPEN表，计算f(S0)；

(2) 如果OPEN表为空,则问题无解，退出；

(3) 把OPEN表的第一个节点(记为节点n)取出，放入CLOSED表；

(4) 考查节点n是否为目标节点，若是，则求得了问题的解，退出；

(5) 若节点n不可扩展，则转第(2)步；

(6) 扩展节点n，用估价函数 f(x) 计算每个子节点的估价值，并按估价值从小到大的顺序依次放入OPEN表的首部，并为每一个子节点都配置指向父节点的指针，转第(2)步。

3有序搜索

也叫全局择优搜索或最好优先搜索.

选择OPEN表上具有最小f值的节点作为下一个要扩展的节点。