目录

回顾/本期梗概

一、迭代加深搜索（IDDFS）

        1、IDDFS基础知识

        1）什么是迭代加深搜索

         2)迭代加深的基本结构

         3)IDDFS和BFS比较优势是什么

        4）IDDFS中的复杂计算问题

二、A*算法

        1、A*算法基础知识

        1.什么是A*算法

        2.A*算法的核心思想、

         3、A*算法的核心要点：

        相关说明：

        （1）为什么终点出队说明最短？

        （2）为什么非终点出队，不一定是最优解？

三、IDA*

        1、IDA*基础知识

        1）什么是IDA*

        2）IDA*和A*的区别

---

回顾/本期梗概

        上期我们学习了搜索优化、搜索进阶（空降链接）本期我们将学习迭代加深搜索、启发式搜索、A、IDA。

---

一、迭代加深搜索（IDDFS）

        1、IDDFS基础知识

        1）什么是迭代加深搜索

        迭代加深搜索（IDDFS）是深度优先搜索，与普通的dfs不同的是，每次深搜都会有搜索的最大深度限制，如果没有找到解，那么就增大深度，再进行深搜，如此循环直到找到的解为止，这样可以找到最浅层的解。

        IDDFS适和求解：搜索深度较深，但正确的解再较浅的深度的问题。

        IDDFS的使用前提是：一定要有解。

        

         2)迭代加深的基本结构

while(!dfs(maxdep))
    maxdep++;

         3)IDDFS和BFS比较优势是什么

        BFS 的基础是一个队列，队列的空间复杂度很大，当状态比较多或者当状态比较大时，使用队列的BFS就显出了了劣势。事实上，迭代加深就类似于用DFS方式实现的BFS，他的空间复杂度相对较小。

        IDDFS和BFS相比的优势在于：空间复杂度会小很多，也可以配合剪枝来提升搜索效率。

        4）IDDFS中的复杂计算问题

        当搜索树的分支比较多时，每增加一层的搜索复杂度会出现指数级爆炸式增长，这时前面重复的部分所带来的复杂度几乎可以忽略，这也就是为什么迭代加深可以近似看成BFS的。

---

二、A*算法

        1、A*算法基础知识

        启发式搜索（Heurisrically Search）又称为有信息搜索（Informed Search），它是利用问题拥有的启发信息来引导搜索，达到减少搜索范围、减低问题复杂度的目的，这种利用启发信息的搜索过程称为启发式搜索。

        启发式策略：可以通过指导搜索向最有希望的方向前进，降低了复杂度。通过删除某些状态及其延伸，启发式算法可以消除组合爆炸，并得到令人能接受的解。

        1.什么是A*算法

        A*算法，A*（A-Star）算法是一种静态路网中求解最短路径最有效的直接搜索方法。

        2.A*算法的核心思想、

        A*算法的核心思想：使用一下队列BFS，并结合估价函数，每次取出优先队列中总代价最低点进行BFS扩展。这种带有估价函数的优先队列BFS算法，就是A*算法。

        例子：求S点到T点的最短路。

        

        普通BFS：

         A*算法：

        使用A*算法，优先队列维护：d[u]+f[u]

        设：f[u]=该点到终点的曼哈顿距离

        类似优先队列BFS，走到不能证明最短，出队才能说明是最短。

         3、A*算法的核心要点：

        A.设f(x)代表了x点到终点的估计值，g(x)代表了x点到终点的最终实际值，则一定要满足：，也就是：估计值必须最终实际值，估价函数才有意义。

                a、当：f(x)=0时，A*算法退化为普通的优先队列BFS的算法;

                b、当问题无解时，A*算法退化为朴素的BFS但由于A*算法要维护优先队列，因此此效率低于朴素的BFS。

        B.目标状态在第1次从优先队列取出时，就得到了最优解。

        C.搜索看见比较庞大且问题一定有解时，A*算法的优势才会比较明显；

        D.出兑就是最小距离的性质，只对终点成立，对其他的点不一定成立，且每个点可能会被讨论多次。

        相关说明：

        （1）为什么终点出队说明最短？

        假设u点出队，到u点的最短路为d(u)，u点到终点的估计值为f(u)，实际值为g(u)

        

        

        如果u点出队，说明d(u)+f（u）是当前队列的最小值，如果该值不是最优解，说明队列中有比其更小的值，与优先队列维护最小值的性质矛盾，因此u点出列时，一定能得到u点的最优解。

        注意：如果u点是终点，则g(u)=0.

        （2）为什么非终点出队，不一定是最优解？

        设：1,2,4,5点的f(x)=0，走其余点f(x)=g(x),A*算法对估价函数的要求是因此，设置2种不同的估计函数并不影响算法的正确性。

        则：d(x)+f(x)的结果将如图所示

        讨论发现：

        A.点5出队时，到点5的最短路计算出来是3，这并不是最优解，只是因为1,2,4,5点的估价函数较小，因此点5先出队。

        B.当走到点6时，d(x)+f(x)的最小值不是点6，而是点3，因此有机会更正之前错误的解，重新用点3更新点5.

---

三、IDA*

        1、IDA*基础知识

        1）什么是IDA*

        IDA*算法是：基于迭代加深的A*算法。迭代加深只有在状态呈指数级增长时才有较好的效果，而A*就是为了防止状态呈指数级增长的。

        IDA*算法本质上是：同时运用迭代加深与全局最优性剪枝。

        2）IDA*和A*的区别

        A*=BFS+启发函数

        IDA*=IDDFS+启发函数

        IDA*由于是深搜，空间消耗相对A*更少。