回溯法8.1概述用回溯法求解一个具有n个输入的问题，一般情况下，将其可能解表示为满足某个约束条件的等长向量X=(x1,x2,…,xn)，其中分量xi(1≤i≤n)的取值范围是某个有限集合Si={ai1,ai2,…,airi}，所有可能的解向量构成了问题的解空间。问题的解空间一般用解空间树（也称状态空间树）的方式组织，树的根结点位于第1层，表示搜索的初始状态，第2层的结点表示对解向量的第一个分量做出选择后到达的状态，第1层到第2层的边上标出对第一个分量选择的结果，依此类推，从树的根结点到叶子结点的路径就构成了解空间的一个可能解。1对于n=4的TSP问题解空间树。8.1.2回溯法的设计思想解空间树的动态搜索过程图8.20/1背包问题的解空间树回溯法的搜索过程涉及的结点（称为搜索空间）只是整个解空间树的一部分，在搜索过程中，通常采用两种策略避免无效搜索：（1）用约束条件剪去得不到可行解的子树；（2）用目标函数剪去得不到最优解的子树。这两类函数统称为剪枝函数。问题的解空间树是虚拟的，并不需要在算法运行时构造一棵真正的树结构，只需要存储从根结点到当前结点的路径。回溯法的一般框架——递归形式在问题的解向量X=(x1,x2,…,xn)中，分量xi(1≤i≤n)的取值范围为某个有限集合Si={ai1,ai2,…,airi}，因此，问题的解空间由笛卡儿积A=S1×S2×…×Sn构成。在用回溯法求解问题时，常常遇到两种典型的解空间树：（1）子集树：当所给问题是从n个元素的集合中找出满足某种性质的子集时，相应的解空间树称为子集树。在子集树中，|S1|=|S2|=…=|Sn|=c，即每个结点有相同数目的子树，通常情况下c=2，因此，子集树中共有2n个。（2）排列树：当所给问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。在排列树中，通常情况下，|S1|=n，|S2|=n-1，…，|Sn|=1，所以，排列树中共有n!个叶子结点，因此，遍历排列树需要Ω(n!)时间。8.1.4一个简单的例子—素数环问题图着色问题描述为：给定无向连通图G=(V,E)和正整数m，求最小的整数m，使得用m种颜色对G中的顶点着色，使得任意两个相邻顶点着色不同。A问题描述：著名的爱尔兰数学家哈密顿提出了著名的周游世界问题。正十二面体的20个顶点代表20个城市，要求从一个城市出发，经过每个城市恰好一次，然后回到出发城市。图8.9所示是一个正十二面体的展开图，按照图中的顶点编号所构成的回路，就是哈密顿回路的一个解。假定图G=(V,E)的顶点集为V={1,2,…,n}，则哈密顿回路的可能解表示为n元组X=(x1,x2,…,xn)，其中，xi∈{1,2,…,n}。根据题意，有如下约束条件：(a)一个无向图(b)哈密顿回路的搜索空间图8.10回溯法求哈密顿回路示例用回溯法求解哈密顿回路，首先把n元组的每一个分量初始化为0，然后深度优先搜索解空间树，如果满足约束条件，则继续进行搜索，否则，将引起搜索过程的回溯。设数组x[n]存储哈密顿回路上的顶点，数组visited[n]存储顶点的访问标志，visited[i]=1表示哈密顿回路经过顶点i，算法如下：8.3组合问题中的回溯法组合问题中的回溯法——八皇后问题若两个皇后摆放的位置分别是(i,xi)和(j,xj)，在棋盘上斜率为-1的斜线上，满足条件i－j=xi－xj，在棋盘上斜率为1的斜线上，满足条件i＋j=xi＋xj，综合两种情况，由于两个皇后不能位于同一斜线上，所以，解向量X必须满足约束条件：|i－xi|≠|j－xj|（式8.2）为了简化问题，下面讨论四皇后问题，如图8.11所示。四皇后问题的解空间树应该是一个完全4叉树，树的根结点表示搜索的初始状态，从根结点到第2层结点对应皇后1在棋盘中第1行的可能摆放位置，从第2层结点到第3层结点对应皇后2在棋盘中第2行的可能摆放位置，依此类推。的位置，也就是第一行第二列，接下来，把皇后2摆放第二行第四列的位置，把皇后3摆放到第三行第一列的位置，把皇后4摆放到第四行第三列的位置，这就是4皇后问题的一个解，在解空间树中的搜索过程如图8.12所示。在n=4的情况下，解空间树共有65个结点、24个叶子结点，但在实际搜索过程中，遍历操作只涉及8个结点，在24个叶子结点中，仅遍历1个叶子结点就找到了满足条件的解。如果问题需要求出所有解，回溯算法继续同样的操作，或者利用棋盘的对称性来求出其他解。8.3.2批处理作业调度问题作业1:2作业2:3