所谓的搜索，就是在解空间里面去找解。

登录以参加训练计划

在状态空间里搜索

状态

在递归中我们讲过参数化的问题分解，即把同一个问题中变化的部分提取到参数中的策略。比如：

• 汉诺塔中将有多少个盘要搬提取成参数N，那么问题就变成「搬N个盘的步数」
• 爬楼梯中，把目标的台阶编号提取成参数N，那么问题就变成「爬N级台阶的方法数」
• 在x个元素的全排列中，把已经选过的元素提取成参数prefix，待选的集合提取成options，待选的数量提取为N，那么问题就变成「在已选prefix的前提下，从options里面选N个的全排列」

这些问题，我们称为状态

转移

这些状态之间可以转移。 比如，根据加法原理，完成一件事可以分成独立的三个步骤，那么总的方法数就是这三个步骤方法数之和。即：搬N个盘的步数 = 搬N-1个盘（从起始柱子到中间柱子） + 搬1个盘（从起始柱子到目标柱子） + 搬N-1个盘（从中间柱子到目标柱子）

解

这些状态中的一部分，就是原问题的解。比如：

• 汉诺塔中，当N == 1时
• 爬楼梯中，N小于某个数时
• 全排列中，待选的数量为0时

状态空间

当我们把状态看成节点，转移看成边。上述问题就变成了在一张图上找解节点的问题。

于是，图上常用的DFS 、 BFS都能用起来了。