算法设计与分析八八回溯法8.1一般方法例：分类问题对A(1:n)的元素分类问题用n元组表示解：（x1,x2,…,xn)xi：表示第i小元素在原始数组里的下标，取自有穷集Si=[1..n]。规范函数P：A(xi)≤A(xi+1)，1≤i＜n如何求取满足规范函数的元组？回溯（分枝限界）法带来什么样的改进？避免盲目求解，对可能的元组进行系统化搜索。在求解的过程中，逐步构造元组分量，并在此过程中，通过不断修正的规范函数（有时称为限界函数）去测试正在构造中的n元组的部分向量（x1,…,xi），看其能否导致最优解。如果判定（x1,…,xi）不可能导致最优解，则将可能要测试的mi+1…mn个向量一概略去，相对于硬性处理可大大减少计算量。概念1.约束条件：问题的解需要满足的条件。可以分为显式约束条件和隐式约束条件。显式约束条件：一般用来规定每个xi的取值范围。如：xi≥0即Si={所有非负实数}xi=0或xi=1即Si={0,1}li≤xi≤ui即Si={li≤a≤ui}显式约束条件可以与所求解的问题实例I有关，也可以无关。解空间：实例I的满足显式约束条件的所有元组，即所有xi合法取值的元组，构成I的解空间。隐式约束条件：用来规定I的解空间中那些满足规范函数的元组，隐式约束将描述xi必须彼此相关的情况。例：8-皇后问题行、列号：1…8皇后编号：1…8,约定皇后i放到第i行的某一列上。解的表示：可以用8-元组(x1,…,x8)表示，其中xi是皇后i所在的列号。显式约束条件：Si={1,2,3,4,5,6,7,8},1≤i≤8解空间：所有可能的8元组，有88个。隐式约束条件：用来描述xi之间的关系，即没有两个xi可以相同且没有两个皇后可以在同一条斜角线上。由隐式约束条件可知：可能解只能是（1,2,3,4,5,6,7,8）的置换（排列），最多有8！个。图中的解表示为一个8-元组为（4，6，8，2，7，1，3，5）例8.2子集和数问题解的表示：用下标的形式表示。形式一：问题的解为k-元组(x1,x2,…,xk),1≤k≤n。不同的解可以是大小不同的元组，如(1,2,4)和(3,4)。显式约束条件：xi∈{j|j为整数且1≤j≤n}。隐式约束条件：1）没有两个xi是相同的；2）wxi的和为M；3）xi＜xi＋1,1≤i＜n（避免重复元组）形式二：解由n-元组(x1,x2,…,xn)表示，其中xi∈{0,1}。如果选择了wi，则xi＝1，否则xi＝0。例：（1，1，0，1）和（0，0，1，1）特点：所有元组具有统一固定的大小。显式约束条件：xi∈{0,1}，1≤i≤n;隐式约束条件：Σ(xi×wi)=M解空间：所有可能的不同元组，总共有2n个元组返回结点13，结点13不能导致答案结点，变成死结点，被杀死。whilek>0do//对所有的行执行以下语句//取自有穷集Si=[1.回溯法是算法设计的基本方法之一。4-皇后问题回溯期间生成的树——称为排列树。该策略已证明对n-皇后问题及其它一些问题无效算法求出所有可能的位置//repeat状态空间树的分解：在状态空间树的每个结点处，解空间被分解为一些子解空间，表示在一些分量取特定值情况下的解空间元素。仅当满足上述两个条件时，限界函数B(X(1),…X(k))=true例：n＝4，（w1,w2,w3,w4）＝（11，13，24，7），置换（排列），最多有8！结点，则Bi(x1,x2,…xi)取假值，否则取真值。mi为X没受限界的儿子结点数目n-皇后问题注：如果不满足上述条件，则X(1),…X(k)根本不可能导致一个答案结点。用元素下标表示（n-元组）：（1，1，0，1）和例：n＝4，（w1,w2,w3,w4）＝（11，13，24，7），仅当满足上述两个条件时，限界函数B(X(1),…X(k))=true生成结点2，表示皇后1被放到第1行的第1列上，该结点是从根结点开始第一个被生成结点。该算法求出所有答案结点。同且没有两个皇后可以在同一条斜角线上。动态树：与实例有关的树称为动态树。if(X(1),…,X(k))是一条已抵达一答案结点的路径足隐式约束条件的解）(answerstates)。（1）生成下一个X(k)的时间要求找出wi的和数等于M的所有子集。xi=0或xi=1即Si={0,1}2）wxi的和为M；endif2）元组大小固定，每个都是n-元组树边标记：由i级结点到i＋1级结点的那些边用xi的值来标记，xi＝1或0。同一个问题可以有不同形式的状态空间树。关于状态空间树的概念状态空间树的分解：在状态空间树的每个结点处，解空间被分解为一些子解空间，表示在一些分量取特定