0x20搜索

在本章中，我们将学习搜索算法。早在第0x00章“基本算法”中我们就多次提到，对问题进行求解，实际上是在问题对应的状态空间中进行映射与遍历。在阅读本章之前，请读者再次确保自己对于递归思想已经有了一定的认识，并懂得利用在第0x10章中介绍的栈、队列、链表、Hash、二叉堆等存储和操作“状态”的基本工具。这些内容会贯穿于我们搜索算法学习的始末。

在0x21节中，我们以树与图的遍历引入本章内容，尝试在树与图结构上进行访问、记录与推导。我们将介绍树的遍历产生的几种序列，树上信息的基本统计方法，图的拓扑排序等算法。这节内容会帮助我们建立“问题状态空间”与图之间的类比联系，从而更加直观地描绘后边几节的各个搜索过程。

在 $0 \times 22 \sim 0 \times 24$ 节中，我们探讨搜索的第一种基本实现形式——深度优先搜索（简称深搜，缩写DFS）。深搜是一种与递归和栈紧密结合的算法。我们会完善“搜索树”这一概念，进一步规范和理解问题状态空间的遍历过程。除此之外，我们会用较大篇幅介绍深搜的各种剪枝方法，并辅以大量例题，帮助读者掌握提高搜索时间、空间效率的途径。迭代加深搜索也是我们重点讨论的对象。

在 $0 \times 25 \sim 0 \times 26$ 节中，我们探讨搜索的第二种基本实现形式——广度优先搜索（简称广搜，缩写BFS）。广搜又称为宽度优先搜索，是一种与队列紧密结合的算法。它还有一些使用双端队列、优先队列或其他数据结构的变形版本，我们也会选择重要的几项进行介绍。无论是深搜还是广搜，如何使用Hash等方法快速记录并检索搜索历史和已遍历状态，也是一个重要的研究话题。

在 $0 \times 27 \sim 0 \times 28$ 节中，我们初探启发式搜索。启发式搜索的算法多种多样，也是解决很多复杂问题的强有力手段。对此，我们选择了 A* 算法进行讲解，包括其理论和应用，以及 IDA*（迭代加深 A*）这种变化形式。通过搜索类题目的大量训练，不但能让读者初步掌握“非多项式时间可解问题”的处理方法，还能大幅提高读者的代码实现能力，快速提升程序设计水平。