Informed Search 有信息搜索

1. 有信息搜索亦被称为启发式搜索。这类策略采用超出问题本身定义的、问题特有的知识，因此能够找到比无信息搜索更有效的解。
   ① Evaluation function 评价函数，记作f(n)，用于选择一个节点进行扩展。
   ② Heuristic function 启发式函数，记作h(n)，作为 f 的一个组成成分。

2. Best-first Search （最佳优先搜索）

Search Strategy （搜索策略）：一个节点被选择进行扩展是基于一个评价函数，f(n)。
大多数的最佳优先算法还包含一个启发式函数，h(n)。
Implementation（实现方法）：队列，按路径代价排序，最低优先。
然而，最佳优先搜索使用f(n)代替g(n)来整理优先队列。
Heuristic function （启发式函数）：h(n) = 从节点 n 到目标状态的最低路径估计代价。
Special cases （特例）：贪婪搜索、A*搜索。

3.Greedy Search （贪婪搜索）

Search Strategy：试图扩展最接近目标的节点。
Evaluation function ： f(n) = h(n)
它仅使用启发式函数对节点进行评价。
h(n) – 从 n 到最接近目标的估计代价。

特性：

4. A*Search （A星搜索）

Search Strategy：避免扩展代价高的路径，使总的估计求解代价最小化。
Evaluation function ： f(n) = g(n) + h(n)
g(n) – 到达该节点的代价
h(n) – 从该节点到目标的估计代价

Theorem：A* search is optimal ！（最优）

5. Iterative Deepening A* Search （迭代加深A*搜索）

它是迭代加深深度优先搜索的变种。从A*搜索算法借鉴了这一思想，即使用启发式函数来评价到达目标的剩余代价。
因为它是一种深度优先搜索算法，内存使用率低于A*算法。但是，不同于标准的迭代加深搜索，它集中于探索最有希望的节点，因此不会去搜索树任何处的同样深度。

Comparing Iterative Deepening Search （对比）：
迭代加深深度优先搜索：使用搜索深度作为每次迭代的截止值。
迭代加深A*搜索：使用信息更丰富的评价函数，即 f(n) = g(n) + h(n) 。

Heuristics for 8*puzzle （8数码难题的启发式）：