搜索技术【启发式搜索】 - 简介 & A* 算法 & IDA*算法
尽管广度优先搜索、深度优先搜索加上有效的剪枝方法，可以解决很多问题，但这两种搜索都是盲目的，它们不管目标在哪里，只管按照自己的方式搜索，会存在很多没必要的搜索。
所以有没有一种启发式搜索算法，可以启发程序朝着目标的方向搜索，从而提高搜索效率呢？
启发式搜索算法对每一个搜索状态都进行评估，选择估值最好的状态，从该状态进行搜索直到目标。如何对一个状态进行评估呢？一个状态的当前代价最小，只能说明从初始状态到当前状态的代价最小，不代表总的代价最小，因为余下的路还很长，未来的代价有可能更高。
因此评估需要考虑两部分：当前代价和未来估价。
评估函数f (x )：f (x )=g (x )+h (x )，其中，g (x )表示从初始状态到当前状态x 的代价，h (x )表示从当前状态到目标状态的估价，h (x )被称为启发函数。
常用的启发式搜索算法有很多，例如A*、IDA*、模拟退火算法、蚁群算法、遗传算法等。
【A*算法】
A算法是带有评估函数的优先队列式广度优先搜索算法。在广度优先搜索时维护一个优先队列，每次都从优先队列中取出评估值最优的状态进行扩展。第1次从优先队列中取出目标状态时，即可得到最优解。A算法提高搜索效率的关键在于启发函数的设计，不同的启发函数，其搜索效率不同。启发函数h (x )越接近当前状态到目标状态的实际代价h′ (x )，A*算法的效率就越高。
启发函数的估值不能超过实际代价，即h (x )≤h ′(x )。
如果启发函数的估值超过实际代价，则失去意义。
例如，如果当前节点到目标的实际最短距离为30，当前节点的启发函数估值为50，另一个节点的启发函数估值为100，则在两个节点已走过路径长度g(x )相同的情况下，不能说明当前节点就一定比另一个节点优，也没有比较的意义，反正两个都不优。
如果令所有状态的h (x )都为0，则退化为普通的优先队列式广度优先搜索算法，不再有启发式搜索的作用。
【IDA*算法】
IDA*算法是带有评估函数的迭代加深DFS算法。
深度优先搜索有可能跌入一个无底深渊，搜索了很多步也无法找到问题的解，因此要对搜索的深度加以限制，超过该深度便不再搜索，立即回溯。迭代加深DFS算法是深度优先搜索算法的一种变形，事先限定一个深度depth，在不超过该深度的情况下进行深度优先搜索，如果找不到解，则增加深度限制，重新进行搜索，直到找到目标。IDA*算法设置了一个评估函数f (x)：当前深度+未来估计步数，当f (x )>depth时立即回溯，避免无效搜索，提高效率。
在很多情况下，IDA*算法的效率更高，代码更少。
