算法设计策略----回溯法和分枝限界法

显示约束和解空间：规定每个分量xi取值的约束条件称为显式约束。对给定的一个问题，显示约束规定了所有可能的元组，他们组成问题的候选解集，被称为该问题实例的解空间。

隐式约束和判定函数：隐式约束给出了判定一个候选解是否为可行解的条件。一般需要从问题描述的隐式约束出发，设计一个判定函数，程序根据判定函数判断一个解是否为可行解。

最优解和目标函数：目标函数，也称代价函数，用来衡量每个可行解的优劣。使目标函数取得最大（小）值的可行解为问题的最优解。

剪枝函数：为了提高搜索效率，在搜索过程中使用约束函数，可以避免无谓地搜索那些已知不含答案状态的子树。如果是最优化问题，还可以使用限界函数剪去那些不可能含有最优解的子树。约束函数和限界函数目的相同，都是为了剪去不必要搜索的子树，减少问题求解所需实际生成的状态结点数，他们统称为剪枝函数。

使用剪枝函数的深度优先生成状态空间树中的节点的求解方法称为回溯法；广度优先生成结点，并使用剪枝函数的方法称为分枝限界法。

一个问题能够用回溯法求解的条件：

1. 它的解具有n-y元组的形式；
2. 问题提供显式约束来确定状态空间树，并提供隐式约束来判定可行解；
3. 能设计有效的约束函数缩小检索空间。

回溯法算法框架：

Void RBacktrack(int k){
    for(每个x[k],使得x[k]∈T[x[0],...,x[k-1]&&B(x[0],...x[k]){
        if(x[o],x[1],...,x[k]是一个可行解）
            输出(x[o],x[1],...,x[k]);
        RBacktrack(k+1);
    }
}

回溯法相关算法：

• n-皇后问题
• 子集和数问题
• 图的着色问题
• 哈密顿环问题

分枝限界法相关算法：

• 15迷问题
• 带时限作业排序