50-回溯法算法秘籍

5.8　回溯法算法秘籍

用回溯法解决问题时，首先要考虑如下3个问题。

（1）定义合适的解空间

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

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

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

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

（3）搜索解空间

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

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

解空间的大小和剪枝函数的好坏是影响搜索效率的关键。

显约束可以控制解空间的大小，剪枝函数决定剪枝的效率。

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