数据结构回溯法求装载问题.docxVIP

数据结构与算法分析回溯法求解装载问题回溯法求解装载问题一、方法一般原理基本思想：在回溯法中,每次扩大当前部分解时，都面临一个可选的状态集合，新的部分解救通过在该集合中进行选择结构而成的。这样的状态集合，结构上是一颗多叉树，每个树结点代表一个可能的部分解，她的儿子是在他的基础上生成其他部分解。树根为初始状态。这样的状态集合，称为状态空间树。回溯法对任一解的生成，一般都采用逐步扩大解的方式。每前进一部，都试图在当前部分解的基础上扩大该部分解。它在问题的状态空间树中，从开始结点（根结点）出发，一深度优先有哪些信誉好的足球投注网站整个状态空间。这个开始结点成为活结点，同时也成为当前的扩展结点。在当前扩展结点处，有哪些信誉好的足球投注网站向纵深方向移动一个新的结点。这个新的结点为新的活结点，并成为当前的中结点。如果在当前扩展结点处不能再向纵深方向移动，则当前的扩展结点就成为死结点。此时，应往回移动（回溯）至最近的活结点处，并使这个活结点成为当前扩展结点。回溯法以这种工作方式递归地在状态空间中有哪些信誉好的足球投注网站，直到找到所要求的解或解空间中以无活结点时为止。回溯法与穷举法有某些联系，他们都是基于试探。穷举法要将一个解的各个部分全都生成后，才检查是否满足条件，若不满足，则直接放弃该完整解、然后再尝试另一个可能的完整解，没有沿着一个可能的完整解的各个部分逐步回退生成解的过程。而对于回溯法，一个解的各个部分是逐步生成的，当发现当前生成的某部分不满足约束条件，就放弃该部所做的工作，退到上一步进行新的尝试，而不是放弃整个解重来。一般来说，回溯法要比穷举法效率高一些。可用回溯法求解的问题P，通常要能表达为：对于已知的由n元组（1， 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（ji）元组（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≥ij。因此，对于约束集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中有哪些信誉好的足球投注网站所要求的叶子结点，很自然的一种方式是从根出发，按深度优先的策略逐步深入，即依次有哪些信誉好的足球投注网站满足