搜索算法的形式化描述：

状态、动作、状态转移、路径、测试目标

一、启发式搜索（有信息搜索）

辅助信息　 所求解问题之外、与所求解问题相关的特定信息或知识 评价函数 f(n) 从当前节点n出发，根据评价函数来选择后续节点 启发函数 h(n)

计算从节点n到目标节点之间所形成路径的最小代价值。

这里将两点之间的直线距离作为启发函数。

搜索算法： 贪婪最佳优先、A*算法

1、贪婪最佳优先搜索的不足之处：

• 贪婪最佳优先搜索不是最优的。
• 启发函数代价最小化这一目标会对错误的起点比较敏感。
• 贪婪最佳优先搜索也是不完备的。即沿着一条无限路径走下去而不回来做其他选择尝试，因此无法找到最佳路径这一答案。
• 在最坏的情况下，贪婪最佳优先搜索的时间复杂度和空间复杂度都是O(bm)，其中b是节点的分支因子数目、m是搜索空间的最大深度。

2、A* 算法

     f(n) = g(n) + h(n)

     评估函数   当前最小开销代价 后续最小开销代价

二、对抗搜索（也称博弈搜索）

1、最小最大搜索

优点：

•  算法是一种简单有效的对抗搜索手段
• 在对手也“尽力而为”前提下，算法课返回最优结果

缺点：

• 如果搜索数极大，则无法在有效时间内返回结果

改善：

• 使用alpha-beta pruning算法来减少接节点
• 对节点进行采样、而非逐一搜索

2、Alpha-Beta剪枝搜索

      对最小最大搜索进行改进的算法，即在搜索过程中可剪除无需搜索的分支节点，且不影响搜索结果。

3、蒙特卡洛树搜索

     通过采样而非穷举方法来实现搜索

三、蒙特卡洛搜索