0x29 总结与练习

在本章中，我们主要按照以下脉络探讨了各种搜索算法：

树与图的遍历是学习第 $0 \times 40$ 、 $0 \times 50$ 、 $0 \times 60$ 章的基础，读者务必熟练掌握在树上利用深度优先遍历和在有向无环图上按照拓扑序进行若干信息的统计。

深度优先搜索和广度优先搜索是解决各类问题的一般性方法，是搜索的最基础内容。设计并实现基本的DFS/BFS框架，也是程序设计的基本能力。为了提高搜索算法的效率，我们在0x23节提到了5类常见剪枝手法，其主要思想是降低搜索树的分支数量，及时发现并避免重复和无效的分支搜索。基于搜索树的层次限制，我们又在0x24

节提及了迭代加深和双向搜索两种思想。另外，请读者再次回顾0x26节中我们列出的根据每次扩展代价的情况对应的几种不同的广搜形式，这对于读者理解广搜和A*算法有很大的帮助。

A* 和 IDA* 是入门级的启发式搜索算法，虽然搜索框架基于 BFS/DFS，但关键在于设计出优秀的估价函数。在满足估价不大于未来实际代价这个基本准则的前提下，如何想出更确切的估价函数，就只能考验读者的见识和思维水平了。

值得提出的是，本章的部分例题和习题代码量较大，对于初学者来说不容易实现。希望读者在学习本章知识点的同时，多花时间尝试独立实现各道题目的具体编程工作，提高自己的代码实现能力——这也是我们设计本章内容的初衷之一。

$\spadesuit$ 本章知识点

树与图的遍历

树与图的深度优先遍历，树的DFS序、深度、重心，图的连通块划分

树与图的广度优先遍历，拓扑排序，bitset 优化的可达性统计

深度优先搜索

深搜的三种基本递归形式，经典的子集和、全排列、 $N$ 皇后问题等

深搜框架的设计与实现，搜索树理论

剪枝

剪枝的设计思想与实现

优化搜索顺序、排除等效冗余、可行性与最优性剪枝、记忆化等常见剪枝手法

迭代加深

迭代加深思想，迭代加深DFS（ID-DFS）

双向搜索思想，双向DFS

广度优先搜索

广搜框架的设计与实现，熟练使用记录数组判重、方向常数数组等

广搜的常见问题类型，如走地图、多起点BFS、双重BFS等

广搜变形

双端队列 BFS，双向 BFS

优先队列 BFS，理解并能根据每次扩展代价的实际情况选择正确的 BFS 形式

A*

估价函数的设计准则，估值 $f(state) \leq$ 未来实际代价 $g(state)$

$\mathbf{A}^*$ 算法的实现， $\mathrm{A}^{*} =$ 优先队列BFS $^+$ 估价函数

IDA*

$\mathbf{IDA^{*}}$ 算法的实现， $\mathrm{IDA^{*} =}$ 迭代加深DFS $^+$ 估价函数

$\spadesuit$ 练习

1. 完成本章中所有例题的代码实现（标有*的题目选做）
   2.靶形数独

题目地址：NOIP2009/CODEVS1174，提示：深度优先搜索/剪枝/位运算优化

1. 虫食算

题目地址：NOIP2004/CODEVS1064，提示：深度优先搜索/剪枝

1. Mayan 游戏

题目地址：NOIP2011/CODEVS1136，提示：深度优先搜索

1. *The Buses

题目地址：IOI1994/POJ1167，提示：深度优先搜索/迭代加深

1. *Missile Defending System

题目地址：POJ3700，提示：深度优先搜索/迭代加深

1. 武士风度的牛

题目地址：CODEVS1411，提示：广度优先搜索

1. 乳草的入侵

题目地址：TYVJ1030，提示：广度优先搜索

9.字串变换

题目地址：NOIP2002/CODEVS1099，提示：广度优先搜索/双向广搜

1. Weather Forecast

题目地址：POJ2044，提示：广度优先搜索

1. *Bloxorz II

题目地址：POJ3323，提示：广度优先搜索/分情况讨论/数学计算

1. Power Hungry Cow

题目地址：POJ1945，提示：A*

1. Flood-it!

题目地址：POJ4007/CODEVS2495，提示：IDA*

14.*骑士精神

题目地址：BZOJ1085，提示：IDA*