从暴力枚举到隐式解空间树很多组合问题看起来都绕不开穷举。比如图着色问题中给定一个无向图 G(V,E)G(V,E)如果每个顶点都可以染成 1,2,31,2,3 三种颜色之一那么对 nn 个顶点来说最朴素的候选空间大小是3n3n其中大多数染色方案并不合法因为相邻顶点可能颜色相同。如果完全无组织地枚举搜索很快会失控。搜索算法所做的第一件事就是把这些候选方案组织起来。很多搜索问题都可以写成一个解向量X(x1,x2,…,xn)X(x1​,x2​,…,xn​)其中每个分量 xixi​ 来自一个有限集合 SiSi​。完整搜索空间就是S1×S2×⋯×SnS1​×S2​×⋯×Sn​这句话看起来有些数学化但它其实就是我们平时写搜索代码时面对的对象。例如全排列问题中xixi​ 表示第 ii 个位置放哪个元素N 皇后问题中xixi​ 可以表示第 ii 行皇后所在的列3-coloring 中xixi​ 表示第 ii 个顶点的颜色0/1 背包中xi∈0,1xi​∈0,1 表示是否选择第 ii 个物品。一旦把问题写成连续决策它就自然形成了一棵树根节点表示空向量 ()()第 kk 层节点表示一个长度为 kk 的前缀 (x1,…,xk)(x1​,…,xk​)从一个节点扩展子节点就是给 xk1xk1​ 选择一个候选值叶子节点对应完整解向量。这棵树通常不会被显式构造出来。它存在于递归调用栈、队列、优先队列、状态变量或搜索框架里。因此它也常被称为隐式解空间树。从这个角度看搜索代码并不是“递归魔法”。它只是用某种顺序遍历这棵隐式树。一个节点代表的不是一个答案而是一整棵子树真正决定搜索效率的往往不是完整解而是部分解。一个长度为 kk 的前缀(x1,x2,…,xk)(x1​,x2​,…,xk​)代表的不只是当前这 kk 个选择而是它下面所有可能的补全。也就是说一个搜索节点代表的是一整棵子树。例如在 N 皇后中前 kk 行皇后的列号确定以后这个节点下面包含了所有可能的后 n−kn−k 行摆法。剪掉一个节点等于同时放弃它下面的所有补全。这件事很危险也很强大。如果剪错了就可能漏掉正确答案。如果剪得安全一次判断就能砍掉指数级数量的候选方案。所以每个安全剪枝背后都应该有一个证明。在回溯法中我们通常证明当前部分解违反约束⇒任意扩展都不可能合法当前部分解违反约束⇒任意扩展都不可能合法在分支限界法中我们通常证明当前子树的最好可能性不优于已知答案⇒任意扩展都不可能成为最优解当前子树的最好可能性不优于已知答案⇒任意扩展都不可能成为最优解如果一个判断只能说“这样大概率不会错”那它是启发式如果它能说“这样一定不会漏解”它才是精确搜索中的安全剪枝。这也是搜索算法最重要的思想剪枝不是技巧而是一种证明。部分解、死节点和 promising node在解空间树中一个节点通常可以被分成几类。第一类是完整解。它已经给所有变量赋值并且满足问题约束。第二类是仍有希望的部分解。它还不是完整解但目前没有足够理由否定它。第三类是死节点。它已经不可能扩展成合法解或者不可能扩展成更优解。当然“当前没有违反约束”不一定等于“未来一定可以扩展成完整解”。例如图着色中一个部分染色可能暂时没有任何已染色边冲突但某个未染色顶点的所有颜色都已经被邻居占用。此时它虽然没有出现显式冲突却已经不可能扩展成完整合法染色。没有被剪掉的节点只表示“暂时不能证明它失败”被剪掉的节点则必须能证明“它一定失败”。回溯法中的is_valid、is_promising、check这些函数本质上都是在回答同一个问题这个节点下面还有没有继续搜索的必要回溯法用约束剪掉不可能的解回溯法通常以深度优先方式遍历解空间树。它从空向量开始依次给 x1,x2,…x1​,x2​,… 赋值。如果当前前缀仍然有希望就继续深入如果当前前缀已经被证明不可能成功就返回上一层尝试下一个候选值。程序员熟悉的结构大概是search(k):if current state is a final solution:record itreturnfor x in candidates of next decision:choose xif current state is still promising:search(k 1)undo x这里最重要的不是递归而是promising判断。如果没有这个判断搜索就退化成完整枚举。promising越能尽早发现失败搜索树就越小。搜索顺序不是实现细节从解空间树的角度看候选值顺序决定了遍历顺序变量顺序决定了树的形态。这会带来几个直接后果变量顺序会改变剪枝发生的早晚候选值顺序会影响第一个解出现的位置剪枝判断越早发生被砍掉的子树越大同一个问题换一种状态表示可能得到完全不同规模的搜索树。所以成熟的搜索算法设计并不是“套模板”而是先设计一个好的状态空间再决定如何遍历它。N 皇后状态设计本身就是剪枝N 皇后是最经典的回溯问题之一。最直接但很糟糕的建模方式是逐格决定棋盘上每个位置是否放皇后。对于一个 n×nn×n 的棋盘这相当于面对接近 2n22n2 的候选空间。但我们知道每一行最终必须恰好放一个皇后。于是可以改用一维向量xi第 i 行皇后所在的列xi​第 i 行皇后所在的列这样搜索空间立刻从棋盘格子的子集变成每行列号的组合规模变成 nnnn如果进一步意识到每一列也最多只能放一个皇后那么还可以把状态空间限制为列的排列规模进一步变成 n!n!这三个状态空间描述的是同一个问题但搜索规模完全不同。这说明一个很重要的事实剪枝不只发生在if语句里也发生在状态定义里。在一维表示中对于任意两行 ii 和 jj两个皇后冲突当且仅当 xixjxi​xj​ 或