回溯法

null８　回溯法８　回溯法　　概 述 　　图问题中的回溯法　　 组合问题中的回溯法null8.1 概 述 8.1.1 问题的解空间8.1.2 解空间树的动态搜索（1）8.1.3 回溯法的求解过程8.1.4 回溯法的时间性能null 复杂问题常常有很多的可能解，这些可能解构成了问题的解空间。解空间也就是进行穷举的搜索空间，所以，解空间中应该包括所有的可能解。确定正确的解空间很重要，如果没有确定正确的解空间就开始搜索，可能会增加很多重复解，或者根本就搜索不到正确的解。8.1.1 问题的解空间 null例如下面的问题：桌子上有6根火柴棒，要求以这6根火柴棒为边搭建4个等边三角形。可以很容易用5根火柴棒搭建2个等边三角形，但却很难将它扩展到4个等边三角形，如图8.1(a)所示。是问题的描述产生了误导，因为它暗示的是一个二维的搜索空间（火柴是放在桌子上的），但是，为了解决这个问题，必须在三维空间中考虑，如图8.1(b)所示。null 对于任何一个问题，可能解的 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示方式和它相应的解释隐含了解空间及其大小。例如，对于有n个物品的0/1背包问题，其可能解的表示方式可以有以下两种： （1）可能解由一个不等长向量组成，当物品i(1≤i≤n)装入背包时，解向量中包含分量i，否则，解向量中不包含分量i，解向量的长度等于装入背包的物品个数，则解空间由长度为0～n的解向量组成。（2）可能解由一个等长向量{x1, x2, …, xn}组成，其中xi=1(1≤i≤n)表示物品i装入背包，xi=0表示物品i没有装入背包，则解空间由长度为n的0/1向量组成。null为了用回溯法求解一个具有n个输入的问题，一般情况下，将其可能解表示为满足某个约束条件的等长向量X=(x1, x2, …, xn)，其中分量xi (1≤i≤n)的取值范围是某个有限集合Si={ai1, ai2, …, airi}，所有可能的解向量构成了问题的解空间。 例如，n个城市的TSP问题，将其可能解表示为向量X=(x1, x2, …, xn)，其中分量xi（1≤i≤n）的取值范围S={1, 2, …, n}，并且解向量必须满足约束条件xi≠xj (1≤i, j≤n)。null 问题的解空间一般用解空间树（Solution Space Trees,也称状态空间树）的方式组织，树的根结点位于第1层，表示搜索的初始状态，第2层的结点表示对解向量的第一个分量做出选择后到达的状态，第1层到第2层的边上标出对第一个分量选择的结果，依此类推，从树的根结点到叶子结点的路径就构成了解空间的一个可能解。null对于n=3的0/1背包问题，其解空间树如图8.2所示，树中第i层与第i+1层(1≤i≤n)结点之间的边上给出了对物品i的选择结果，左子树表示该物品被装入了背包，右子树表示该物品没有被装入背包。树中的8个叶子结点分别代表该问题的8个可能解，例如结点8代表一个可能解(1, 0, 0)。 null 对于n=4的TSP问题，其解空间树如图8.3所示，树中第i层与第i+1层(1≤i≤n)结点之间的边上给出了分量xi的取值。记i→j表示从顶点i到顶点j的边(1≤i, j≤n)，从图8.3中可以看到，根结点有4棵子树，分别表示从顶点1、2、3、4出发求解TSP问题，当选择第1棵子树后，结点2有3棵子树，分别表示1→2、1→3、1→4，依此类推。树中的24个叶子结点分别代表该问题的24个可能解，例如结点5代表一个可能解，路径为1→2→3→4→1，长度为各边代价之和。 null8.1.2 解空间树的动态搜索（1） 蛮力法是对整个解空间树中的所有可能解进行穷举搜索的一种方法，但是，只有满足约束条件的解才是可行解，只有满足目标函数的解才是最优解，这就有可能减少搜索空间。回溯法从根结点出发，按照深度优先策略遍历解空间树，搜索满足约束条件的解。在搜索至树中任一结点时，先判断该结点对应的部分解是否满足约束条件，或者是否超出目标函数的界，也就是判断该结点是否包含问题的（最优）解，如果肯定不包含，则跳过对以该结点为根的子树的搜索，即所谓剪枝（Pruning）；否则，进入以该结点为根的子树，继续按照深度优先策略搜索。null8.1.2 解空间树的动态搜索（1） 例如，对于n=3的0/1背包问题，三个物品的重量为{20, 15, 10}，价值为{20, 30, 25}，背包容量为25，从图8.2所示的解空间树的根结点开始搜索，搜索过程如下： null图8.2 0/1背包问题的解空间树1111110000000112345781112141531069重量为{20, 15, 10}， 价值为{20, 30, 25}， 背包容量为25nullnull例如，对于n=4的TSP问题，其代价矩阵如图8.5所示， C=∞ 3 6 7 12 ∞ 2 8 8 6 ∞ 2 3 7 6 ∞图8.5 TSP问题的代价矩阵从图8.3所示解空间树的根结点开始搜索，搜索过程？ nullnull 从上述两个例子可以看出，回溯法的搜索过程涉及的结点（称为搜索空间）只是整个解空间树的一部分，在搜索过程中，通常采用两种策略避免无效搜索：（1）用约束条件剪去得不到可行解的子树；（2）用目标函数剪去得不到最优解的子树。这两类函数统称为剪枝函数（Pruning Function）。 需要注意的是，问题的解空间树是虚拟的，并不需要在算法运行时构造一棵真正的树结构，只需要存储从根结点到当前结点的路径。例如，在0/1背包问题中，只需要存储当前背包中装入物品的状态，在TSP问题中，只需要存储当前正在生成的路径上经过的顶点。null8.1.3 回溯法的求解过程 由于问题的解向量X=(x1, x2, …, xn)中的每个分量xi(1≤i≤n)都属于一个有限集合Si={ai1, ai2, …, airi}，因此，回溯法可以按某种顺序（例如字典序）依次考察笛卡儿积S1×S2×…×Sn中的元素。初始时，令解向量X为空，然后，从根结点出发，选择S1的第一个元素作为解向量X的第一个分量，即x1= a11，如果X=(x1)是问题的部分解，则继续扩展解向量X，选择S2的第一个元素作为解向量X的第2个分量，否则，选择S1的下一个元素作为解向量X的第一个分量，即x1= a12。依此类推，一般情况下，如果X=(x1, x2, …, xi)是问题的部分解，则选择Si+1的第一个元素作为解向量X的第i+1个分量时，有下面三种情况： （1）如果X=(x1, x2, …, xi＋1)是问题的最终解，则输出这个解。如果问题只希望得到一个解，就结束搜索，否则null继续搜索其他解； （2）如果X=(x1, x2, …, xi＋1)是问题的部分解，则继续构造解向量的下一个分量； （3）如果X=(x1, x2, …, xi＋1)既不是问题的部分解也不是问题的最终解，则存在下面两种情况： ① 如果xi+1= ai＋1k不是集合Si＋1的最后一个元素，则令xi+1= ai＋1k＋1，即选择Si+1的下一个元素作为解向量X的第i+1个分量； ② 如果xi+1= ai＋1k是集合Si＋1的最后一个元素，就回溯到X=(x1, x2, …, xi)，选择Si的下一个元素作为解向量X的第i个分量，假设xi= aik，如果aik不是集合Si的最后一个元素，则令xi= aik＋1；否则，就继续回溯到X=(x1, x2, …, xi－1)； 回溯法的递归形式的一般框架如下： null回溯法的一般框架——递归形式 advance(int k) 1. 对每一个x∈Sk循环执行下列操作 1.1 xk=x; 1.2 将xk加入X; 1.3 if (X是最终解) flag=true; return; 1.4 else if (X是部分解) advance(k+1);主算法 1．X={ }; 2. flag=false; 3. advance(1); 4. if (flag) 输出解X; else输出“无解”;null 回溯算法的非递归迭代形式的一般框架如下：回溯法的一般框架——迭代形式 1．X={ }; 2．flag=false; 3．k=1; 4．while (k>=1) 4.1 当(Sk没有被穷举)循环执行下列操作 4.1.1 xk=Sk中的下一个元素; 4.1.2 将xk加入X; 4.1.3 if (X为最终解) flag=true; 转步骤5; 4.1.4 else if (X为部分解) k=k+1; 转步骤4; 4.2 重置Sk，使得下一个元素排在第1位; 4.3 k=k-1; //回溯 5．if flag 输出解X; else 输出“无解”;null8.1.4 回溯法的时间性能 一般情况下，在问题的解向量X=(x1, x2, …, xn)中，分量xi (1≤i≤n)的取值范围为某个有限集合Si={ai1, ai2, …, airi}，因此，问题的解空间由笛卡儿积A=S1×S2×…×Sn构成，并且第1层的根结点有|S1|棵子树，则第2层共有|S1|个结点，第2层的每个结点有|S2|棵子树，则第3层共有|S1|×|S2|个结点，依此类推，第n+1层共有|S1|×|S2|×…×|Sn|个结点，他们都是叶子结点，代表问题的所有可能解。 在用回溯法求解问题时，常常遇到两种典型的解空间树： （1）子集树（Subset Trees）：当所给问题是从n个元素的集合中找出满足某种性质的子集时，相应的解空间树称为子集树。在子集树中，|S1|=|S2|=…=|Sn|=c，即每个结点有相同数目的子树，通常情况下c=2，所以，子集树中共有2n个null因此，遍历子集树需要Ω(2n)时间。例如，0/1背包问题的解空间树是一棵子集树。 （2）排列树（Permutation Trees）：当所给问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。在排列树中，通常情况下，|S1|=n，|S2|=n-1，…，|Sn|=1，所以，排列树中共有n!个叶子结点，因此，遍历排列树需要Ω(n!)时间。例如，TSP问题的解空间树是一棵排列树。在用回溯法求解问题时，常常遇到两种典型的解空间树： （1）子集树（Subset Trees）：当所给问题是从n个元素的集合中找出满足某种性质的子集时，相应的解空间树称为子集树。在子集树中，|S1|=|S2|=…=|Sn|=c，即每个结点有相同数目的子树，通常情况下c=2，所以，子集树中共有2n个叶子结点null回溯法实际上属于蛮力穷举法，当然不能指望它有很好的最坏时间复杂性，遍历具有指数阶个结点的解空间树，在最坏情况下，时间代价肯定为指数阶。然而，从本章介绍的几个算法来看，他们都有很好的平均时间性能。回溯法的有效性往往体现在当问题规模n很大时，在搜索过程中对问题的解空间树实行大量剪枝。但是，对于具体的问题实例，很难预测回溯法的搜索行为，特别是很难估计出在搜索过程中所产生的结点数，这是分析回溯法的时间性能的主要困难。null下面介绍用概率方法估算回溯法所产生的结点数。 估算回溯法产生结点数的概率方法的主要思想是：假定约束函数是静态的（即在回溯法的执行过程中，约束函数不随算法所获得信息的多少而动态改变），在解空间树上产生一条随机路径，然后沿此路径估算解空间树中满足约束条件的结点总数m。设x是所产生随机路径上的一个结点，且位于解空间树的第i层，对于x的所有孩子结点，计算出满足约束条件的结点数mi，路径上的下一个结点从x的满足约束条件的mi个孩子结点中随机选取，这条路径一直延伸，直到叶子结点或者所有孩子结点均不满足约束条件为止。 随机路径中含有的结点总数的计算方法是：假设第1层有m0个满足约束条件的结点，每个结点有m1个满足约束null条件的孩子结点，则第2层上有m0m1个满足约束条件的结点，同理，假设第2层上的每个结点均有m2个满足约束条件的孩子结点，则第3层上有m0m1m2个满足约束条件的结点，依此类推，第n层上有m0m1m2 … mn-1个满足约束条件的结点，因此，这条随机路径上的结点总数为：m0 + m0m1 + m0m1m2 + … + m0m1m2…mn-1。随机路径中含有的结点总数的计算方法是：假设第1层有m0个满足约束条件的结点，每个结点有m1个满足约束null例如，对于4皇后问题，图8.7给出了4条随机路径所对应的棋盘状态和产生的结点总数。 图8.7 4皇后问题的随机路径及路径上结点总数估算示例null 在使用概率估算方法估算搜索空间的结点总数时，为了估算得更精确一些，可以选取若干条不同的随机路径（通常不超过20条），分别对各随机路径估算结点总数，然后再取这些结点总数的平均值。例如，图8.7所示4皇后问题，搜索空间的结点数取4条随机路径结点总数的平均值，结果为14。而4皇后问题的解空间树中的结点总数为65，则回溯法求解4皇后问题产生的搜索空间的结点数大约是解空间树中的结点总数的14/65≈21.5%，这说明回溯法的效率大大高于蛮力穷举法。 null8.2 图问题中的回溯法 8.2.1 图着色问题 8.2.2 哈密顿回路问题null8.2.1 图着色问题 图着色问题描述为：给定无向连通图G=(V, E)和正整数m，求最小的整数m，使得用m种颜色对G中的顶点着色，使得任意两个相邻顶点着色不同。 由于用m种颜色为无向图G=(V, E)着色，其中，V的顶点个数为n，可以用一个n元组C=(c1, c2, …, cn)来描述图的一种可能着色，其中，ci∈{1, 2, …, m}(1≤i≤n)表示赋予顶点i的颜色。例如，5元组(1, 2, 2, 3, 1)表示对具有5个顶点的无向图的一种着色，顶点1着颜色1，顶点2着颜色2，顶点3着颜色2，如此等等。如果在n元组C中，所有相邻顶点都不会着相同颜色，就称此n元组为可行解，否则为无效解。用m种颜色为一个具有n个顶点的无向图着色，就有mn种可能的着色组合，因此，它的解空间树是一棵完全m叉树，树中每一个结点都有m棵子树，最后一层有mn个叶子结点，每个叶子结点代表一种可能着色。 nullACBDE(a) 一个无向图 (b) 回溯法搜索空间 图8.8 回溯法求解图着色问题示例null例如，在图8.8(a)所示的无向图中求解3着色问题，在解空间树中，从根结点出发，搜索第1棵子树，即为顶点A着颜色1，再搜索结点2的第1棵子树，即为顶点B着颜色1，这导致一个不可行解，回溯到结点2，选择结点2 的第2棵子树，即为顶点B着颜色2，在为顶点C着色时，经过着颜色1和颜色2的失败的尝试后，选择结点4的第3棵子树，即为顶点C着颜色3，在结点7选择第1棵子树，即为顶点D着颜色1，但是在为顶点E着色时，顶点E无论着3种颜色的哪一种均发生冲突，于是导致回溯，在结点7选择第2棵子树也会发生冲突，于是，选择结点7的第3棵子树，即顶点D着颜色3，在结点10选择第1棵子树，即为顶点E着颜色1，得到了一个解(1, 2, 3, 3, 1)。注意到，解空间树中共有243个结点，而回溯法只搜索了其中的14个结点后就找到了问题的解。在解空间树中的搜索过程如图8.8(b)所示。null 回溯法求解图着色问题，首先把所有顶点的颜色初始化为0，然后依次为每个顶点着色。在图着色问题的解空间树中，如果从根结点到当前结点对应一个部分解，也就是所有的颜色指派都没有冲突，则在当前结点处选择第一棵子树继续搜索，也就是为下一个顶点着颜色1，否则，对当前子树的兄弟子树继续搜索，也就是为当前顶点着下一个颜色，如果所有m种颜色都已尝试过并且都发生冲突，则回溯到当前结点的父结点处，上一个顶点的颜色被改变，依此类推。 null在回溯法的搜索过程中只需要保存已处理顶点的着色情况，设数组color[n]表示顶点的着色情况，回溯法求解m着色问题的算法如下： null8.2.2 哈密顿回路问题 在欧拉发现七桥问题之后的一个世纪，著名的爱尔兰数学家哈密顿（William Hamilton，1805—1865）提出了著名的周游世界问题。他用正十二面体的20个顶点代表20个城市，要求从一个城市出发，经过每个城市恰好一次，然后回到出发城市。图8.9所示是一个正十二面体的展开图，按照图中的顶点编号所构成的回路，就是哈密顿回路的一个解。 null 假定图G=(V, E)的顶点集为V={1, 2, …, n}，则哈密顿回路的可能解表示为n元组X=(x1, x2, …, xn)，其中，xi∈{1, 2, …, n}。根据题意，有如下约束条件： 在哈密顿回路的可能解中，考虑到约束条件xi≠xj (1≤i, j≤n，i≠j)，则可能解应该是(1, 2, …, n)的一个排列，对应的解空间树中有n!个叶子结点，n=4时哈密顿回路的解空间树如图8.3所示。 图8.10(a)所示是一个无向图，在解空间树中从根结点1开始搜索，首先将x1置为1，到达结点2，表示哈密顿回路从顶点1开始，然后将x2置为1，到达结点2，但顶点1的兄弟子树，将x2null置为2，构成哈密顿回路的部分解(1, 2)，在经过结点5和结点6的失败的尝试后，将x3置为3，将哈密顿回路的部分解扩展到(1, 2, 3)，在经过结点8、结点9和结点10的失败的尝试后，将x4置为4，将哈密顿回路的部分解扩展到(1, 2, 3, 4)，在经过结点12、结点13、结点14和结点15的失败的尝试后，将x5置为5，将哈密顿回路的部分解扩展到(1, 2, 3, 4, 5)，但是在图(a)中从顶点5到顶点1没有边，引起回溯；将x4置为5，到达结点17，构成哈密顿回路的部分解(1, 2, 3, 5)，在经过结点18、结点19和结点20的失败的尝试后，将x5置为4，将哈密顿回路的部分解扩展到(1, 2, 3, 5, 4)，而在图(a)中从顶点4到顶点1存在边，所以，找到了一条哈密顿回路(1, 2, 3, 5, 4)，搜索过程结束。注意到，解空间树中共有243个结点，而回溯法只搜索了其中的21个结点后就找到了问题的解。在解空间树中的搜索过程如图8.10(b)所示。null(a) 一个无向图 (b) 哈密顿回路的搜索空间 图8.10 回溯法求哈密顿回路示例null用回溯法求解哈密顿回路，首先把n元组的每一个分量初始化为0，然后深度优先搜索解空间树，如果满足约束条件，则继续进行搜索，否则，将引起搜索过程的回溯。 设数组x[n]存储哈密顿回路上的顶点，数组visited[n]存储顶点的访问标志，visited[i]=1表示哈密顿回路经过顶点i，算法如下： null8.3 组合问题中的回溯法 8.3.1 八皇后问题 8.3.2 批处理作业调度问题null8.3.1 八皇后问题 八皇后问题是十九世纪著名的数学家高斯于1850年提出的。问题是：在8×8的棋盘上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上。可以把八皇后问题扩展到n皇后问题，即在n×n的棋盘上摆放n个皇后，使任意两个皇后都不能处于同一行、同一列或同一斜线上。 显然，棋盘的每一行上可以而且必须摆放一个皇后，所以，n皇后问题的可能解用一个n元向量X=(x1, x2, …, xn)表示，其中，1≤i≤n并且1≤xi≤n，即第i个皇后放在第i行第xi列上。 由于两个皇后不能位于同一列上，所以，解向量X必须满足约束条件： xi≠xj （式8.1）null 若两个皇后摆放的位置分别是(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行的可能摆放位置，依此类推。 null回溯法从空棋盘开始，首先把皇后1摆放到它所在行的第一个可能的位置，也就是第一行第一列；对于皇后2，在经过第一列和第二列的失败的尝试后，把它摆放到第一个可能的位置，也就是第二行第三列；对于皇后3，把它摆放到第三行的哪一列上都会引起冲突（即违反约束条件），所以，进行回溯，回到对皇后2的处理，把皇后2摆放到下一个可能的位置，也就是第二行第四列；然而，皇后3摆放到第三行的哪一列上都会引起冲突，再次进行回溯，回到对皇后2的处理，但此时皇后2位于棋盘的最后一列，继续回溯，回到对皇后1的处理，把皇后1摆放到下一个可能null的位置，也就是第一行第二列，接下来，把皇后2摆放第二行第四列的位置，把皇后3摆放到第三行第一列的位置，把皇后4摆放到第四行第三列的位置，这就是4皇后问题的一个解，在解空间树中的搜索过程如图8.12所示。在n=4的情况下，解空间树共有65个结点、24个叶子结点，但在实际搜索过程中，遍历操作只涉及8个结点，在24个叶子结点中，仅遍历1个叶子结点就找到了满足条件的解。如果问题需要求出所有解，回溯算法继续同样的操作，或者利用棋盘的对称性来求出其他解。nullnull8.3.2 批处理作业调度问题 n个作业{1, 2, …, n}要在两台机器上处理，每个作业必须先由机器1处理，然后再由机器2处理，机器1处理作业i所需时间为ai，机器2处理作业i所需时间为bi（1≤i≤n），批处理作业调度问题要求确定这n个作业的最优处理顺序，使得从第1个作业在机器1上处理开始，到最后一个作业在机器2上处理结束所需时间最少。 显然，批处理作业的一个最优调度应使机器1没有空闲时间，且机器2的空闲时间最小。可以证明，存在一个最优作业调度使得在机器1和机器2上作业以相同次序完成。 例如，有三个作业{1, 2, 3}，这三个作业在机器1上所需的处理时间为(2, 3, 2)，在机器2上所需的处理时间为(1, 1, 3)，则这三个作业存在6种可能的调度 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 ：(1, 2, 3)、(1, 3, 2)、(2, 1, 3)、(2, 3, 1)、(3, 1, 2)、(3, 2, 1)，相应的完成时间为10, 8, 10, 9, 8, 8，如图8.13所示。nullnull对于批处理作业调度问题，由于要从n个作业的所有排列中找出具有最早完成时间的作业调度，所以，批处理作业调度问题的解空间是一棵排列树。null