一、对于状态图搜索，已经提出了许多策略，大体可分为：

  • 盲目搜索(blind search)

  • 启发式搜索(heuristic search)

二、盲目搜索

三、宽度/广度优先搜索(BFS, Breadth-First Search)

先访问与当前节点相邻的所有节点，然后再探索下一层的节点。通常使用队列来完成任务。

注：新的节点被插入到open表的最后。

四、深度优先搜索(DFS, Depth-First Search)

注：

  • 新的节点被插入到open表的最前面。

  • 有限的深度搜索(DLS, Depth-Limited Search)

  • 迭代深化深度优先算法(IDS, Iterative Deepening Search)

五、等代价搜索

注：如果所有连接弧线具有相等代价，则简化为宽度优先算法。

六、宽度优先和代价树

七、盲目式搜索小结

八、启发式搜索

启发式函数：在启发式搜索中，通常使用一个函数来评估从当前节点到目标节点的预期成本。这个函数被称为启发式函数。

九、启发式搜索的分类

十、局部最优

十一、A算法

十二、A*算法

十三、搜索方法好的标准

十四、小结