05-解题秘籍

5.1.3　解题秘籍

（1）定义解空间

因为解空间的大小对搜索效率有很大的影响，因此使用回溯法首先要定义合适的解空间，确定解空间包括解的组织形式和显约束。

• 解的组织形式：解的组织形式都规范为一个n元组{x₁，x₂，…，x_n}，只是具体问题表达的含义不同而已。
• 显约束：显约束是对解分量的取值范围的限定，通过显约束可以控制解空间的大小。

（2）确定解空间的组织结构

解空间的组织结构通常用解空间树形象的表达，根据解空间树的不同，解空间分为子集树、排列树、m叉树等。

（3）搜索解空间

回溯法是按照深度优先搜索策略，根据隐约束（约束函数和限界函数），在解空间中搜索问题的可行解或最优解，当发现当前结点不满足求解条件时，就回溯尝试其他的路径。

如果问题只是要求可行解，则只需要设定约束函数即可，如果要求最优解，则需要设定约束函数和限界函数。

解的组织形式都是通用的n元组形式，解的组织结构是解空间的形象表达。解空间和隐约束是控制搜索效率的关键。显约束可以控制解空间的大小，约束函数决定剪枝的效率，限界函数决定是否得到最优解。

所以 回溯法解题的关键是设计有效的显约束和隐约束。

后面我们通过几个实例，深刻体会回溯法的解题策略。