回溯算法.doc

就让昨日成流水,就让往事随风飞,今日的杯中别再盛着昨日的残痕;唯有珍惜现在,才能收获明天。五、回溯法回溯法也称为试探法,该方法首先暂时放弃关于问题规模大小的限制, 并将问题的候选解按某种顺序逐一枚举和检验。当发现当前候选解不可能是解时, 就选择下一个候选解; 倘若当前候选解除了还不满足问题规模要求外, 满足所有其他要求时, 继续扩大当前候选解的规模, 并继续试探。如果当前候选解满足包括问题规模在内的所有要求时,该候选解就是问题的一个解。在回溯法中,放弃当前候选解,寻找下一个候选解的过程称为回溯。扩大当前候选解的规模, 以继续试探的过程称为向前试探。 1 、回溯法的一般描述可用回溯法求解的问题P, 通常要能表达为: 对于已知的由n 元组( x1, x2,…, xn) 组成的一个状态空间 E={ ( x1, x2,…, xn)∣ xi∈ Si, i=1 ,2,…, n} ,给定关于 n 元组中的一个分量的一个约束集 D,要求E 中满足 D 的全部约束条件的所有 n 元组。其中 Si 是分量 xi 的定义域,且|Si| 有限, i=1 ,2,…,n 。我们称 E 中满足 D 的全部约束条件的任一 n 元组为问题 P 的一个解。解问题 P 的最朴素的方法就是枚举法, 即对 E 中的所有 n 元组逐一地检测其是否满足 D 的全部约束, 若满足, 则为问题 P 的一个解。但显然,其计算量是相当大的。我们发现, 对于许多问题, 所给定的约束集 D 具有完备性,即i 元组( x1, x2,…, xi )满足 D 中仅涉及到 x1, x2,…, xi 的所有约束意味着 j( j<i )元组( x1, x2,…, xj )一定也满足 D 中仅涉及到 x1, x2,…, xj 的所有约束, i=1 ,2,…,n。换句话说, 只要存在 0≤j≤ n-1 , 使得( x1, x2,…, xj) 违反 D 中仅涉及到 x1, x2,…, xj 的约束之一, 则以( x1, x2,…, xj) 为前缀的任何 n 元组( x1, x2,…, xj, xj+1 ,…, xn) 一定也违反 D 中仅涉及到 x1, x2,…, xi 的一个约束, n≥ i>j 。因此,对于约束集 D 具有完备性的问题 P, 一旦检测断定某个 j 元组( x1, x2,…, xj )违反 D 中仅涉及 x1, x2,…, xj 的一个约束,就可以肯定,以( x1, x2,…, xj )为前缀的任何 n 元组( x1, x2,…, xj, xj+1 ,…, xn) 都不会是问题 P 的解, 因而就不必去搜索它们、检测它们。回溯法正是针对这类问题, 利用这类问题的上述性质而提出来的比枚举法效率更高的算法。回溯法首先将问题P的n 元组的状态空间E 表示成一棵高为n 的带权有序树 T, 把在 E 中求问题 P 的所有解转化为在 T 中搜索问题 P 的所有解。树 T 类似于检索树,它可以这样构造: 设 Si 中的元素可排成 xi(1) , xi(2) ,…, xi(mi-1) , |Si| =mi , i=1 ,2,…,n。从根开始,让T 的第 I 层的每一个结点都有 mi 个儿子。这 mi 个儿子到它们的双亲的边,按从左到右的次序,分别带权 xi+1(1) , xi+1(2) ,…, xi+1(mi) , i=0 ,1,2,…, n-1 。照这种构造方式,E 中的一个 n 元组( x1, x2,…, xn) 对应于 T 中的一个叶子结点,T 的根到这个叶子结点的路径上依次的 n 条边的权分别为 x1, x2,…, xn, 反之亦然。另外, 对于任意的 0≤i≤ n-1 ,E中 n 元组( x1, x2,…, xn )的一个前缀 I 元组( x1, x2,…, xi)对应于 T 中的一个非叶子结点,T 的根到这个非叶子结点的路径上依次的I 条边的权分别为 x1, x2,…, xi ,反之亦然。特别, E 中的任意一个 n 元组的空前缀( ) ,对应于 T 的根。因而,在 E 中寻找问题 P 的一个解等价于在 T 中搜索一个叶子结点, 要求从 T 的根到该叶子结点的路径上依次的 n 条边相应带的 n个权 x1, x2,…, xn 满足约束集 D 的全部约束。在 T 中搜索所要求的叶子结点, 很自然的一种方式是从根出发, 按深度优先的策略逐步深入, 即依次搜索满足约束条件的前缀 1 元组( x1i ) 、前缀 2 元组( x1, x2)、…,前缀 I 元组( x1, x2,…, xi),…,直到 i=n 为止。在回溯法中, 上述引入的树被称为问题 P 的状态空间树;树T 上任意一个结点被称为问题 P 的状态结点;树T 上的任意一个叶子结点被称为问题 P 的一个解状态