最近一段时间仔细地学习了搜索方面的书籍，对搜索有了一些新的体会。搜索的算法有很多，从最简单的DFS、BFS，到稍稍有点优化的迭代加深、迭代加宽，再到A*、IDA*……感觉对于搜索的学习和运用，绝对不能只局限于这些常用的方法中，而应该对各个方法有一个整体的把握，分析各种方法的优点和缺点，学会比较各种方法的时空性能，针对题目的特点入手。

DFS

最常用的一种搜索方法，几乎学过搜索的都会。适用于搜索的深度已知，比较适合搜索全部解。常用的优化方法是在结点扩展时加入剪枝策略。

BFS

相对与DFS可能用得少了点，但也是必会的基本方法。如果搜索的深度不知，DFS可能陷入死循环，同时，如果空间上可以承受，这时候可以考虑BFS。侧重寻求最优解。

双向广度优先搜索

适用于知道目标状态，每次扩展两个结点，但不一定非要是交替扩展，扩展方式很多。如果目标状态始终不变，而有多个初始状态，就可以“周界搜索”。要注意的是，如何判断已经扩展结点是否在另一端的方法，是需要认真考虑，选取最优判断方法的。

迭代加深搜索 ID

每次限制搜索的深度，找到解就停止，否则加大深度再次搜索。相对于DFS不会陷入死循环，相对于BFS不会在空间上有压力，也可以用来寻求最优解，不过缺点是重复搜索。

迭代加宽搜索 IB

没有太多接触，无视……

A*

按f(s)的值扩展结点，是一种启发式搜索。需要两个表，每次判断是否在表1中、是否在表二中、同时在表一表二中，判断f(s)和f(s')的大小，选择是否替换。其中f(s)=g(s)+h(s)，h(s)为估价函数。要求h函数相容，对于这种说法，我自己的理解就是，状态每转移一次，h减少量最多为1。A*算法求得的第一个解必是最优解。缺点依然是空间需求太大。

IDA*

迭代加深的A*。每次搜索加上一个深度限制，扩展的时候判断最好情况是否会超过深度，也算是一种极端法的剪枝思想。适用与深度不定，最优解的深度又不一定很深，而状态转移的方式又有很多，使得状态空间无法承受。

关于剪枝：1、可行性剪枝 2、最优性剪枝

具体操作时：1、极端法 2、数学方法