Search Heuristics
启发式函数度量当前状态到目标状态的代价估计值，以利用问题的额外信息；
对于不同的问题，采取的启发式函数也不一样，常见的启发式函数有：Manhattan距离，Euclidean距离；
称一个启发式函数是Admissible的（可采纳性），如果这个Heuristics不会过高估计当前状态到目标状态的实际代价；
称一个启发式函数是consistent的（一致性），如果对于当前结点,下一步结点,和目标结点,有如下三角不等式成立：
结点的预估代价不会超过每个结点通过某一行动到达的单步代价与结点的预估代价和；
一致的启发函数一定是可采纳的；
Greedy Best-first Search
对于GBS来说试图拓展距离目标看起来最近的结点，也就是只利用启发信息,
我们从四个方面考察GBS的性能：
- 完备性：即使在有限状态空间中，GBS也是不完备的；
- 最优性：往往也不能达到全局最优解；
- 时间复杂度：;
- 空间复杂度：;
A* Search
对于A*S来说，采用的代价函数具有如下形式：
其中，表示开始结点到当前结点的实际代价，表示当前结点到目标结点的预估最小代价；
A*S试图拓展使得最小的结点,下从四个方面考察Astar算法的性能：
-
完备性：A*算法是完备的；
-
最优性：若可采纳，那么树搜索版本具有最优性，若一致，则图搜索版本具有最优性;只需注意到当A*选择结点时，就已经找到了的最优路径；
-
时间复杂度：在所有启发式算法中最优的也是效率最优的；
-
空间复杂度：内存保留已生成的结点，因此对于大规模问题在计算完成前往往就耗尽内存
IDA* Search
类似IDS，采用的截断值不是搜索深度而是代价，但是代价是一个实数，将面临和UCS一样的问题；
相对于A*，确实减少了内存需求；
