05-解题秘籍

6.1.3　解题秘籍

（1）定义解空间

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

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

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

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

（3）搜索解空间

分支限界法是按照广度优先搜索策略，一次性生成所有孩子结点，根据隐约束（约束函数和限界函数）判定孩子结点是舍弃还是保留，如果保留则依次放入活结点表中，活结点表是普通（先进先出）队列或者是优先级队列。然后丛活结点表中取出一个结点，继续扩展，直到找到所需的解或活结点表为空时为止。每一个活结点最多只有一次机会成为扩展结点。

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

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

在优先队列分支限界法中，还有一个关键的问题是优先级的设定：选什么值作为优先级？如何定义优先级？优先级的设计直接决定算法的效率。因此在本章中，我们重点介绍如何设定高效的优先级问题。

后面我们通过几个实例，深刻体会分支限界法的解题策略。