算法分析第六讲.ppt

6.2 8-皇后问题 6.3 子集和数问题 6.4 图的着色 6.5 哈密顿环 6.6 背包问题 此时，读者可能对于过程 NQueens怎么会优于硬性处理感奇怪。原因是这样的，如果硬性要求个8×8的棋盘安排出8块位置，就有C864种可能的方式，即要检查将近4.4×109个8-元组。然而过程NQueens只允许把皇后放置在不同的行和列上，因此至多需要作8!次检查，即至多只检查40320个8-元组。 可以用过程Estimate来估算NQueens所生成的结点数。要指出的是，过程Estimate所需要的假定也适用于NQueens，即使用固定的限界函数且在检索进行时函数不改变。另外，在状态空间树的同一级的所有结点都有相同的度。图6.8显示了由过程Estimate求结点估计数所用的五个8×8棋盘。如同所要求的那样，棋盘上每一个皇后的位置是随机选取的。对于每种选择方案，都记下了可以将一个皇后合法地放在各行中列的数目(即状态树的每一级没受限的结点数)。它们都列在每个棋盘下方的向量中。向量后面的数字表示过程Estimate由这些量值所产生的值。这五次试验的平均值是1625。 8-皇后状态空间树的结点总数是: 7 j 1 + ∑(∏(8-i)) = 69281 j=0 j=0 因此，不受限结点的估计数大约只是8-皇后状态空间树的结点总数的2.34％。 列 图6.8 8皇后问题的五种方案及不受限结点的估计值 子集和数问题是假定有n个不同的正数(通常称为权)，要求找出这些数中所有使得某和数为M的组合。例6.2和例6.4说明了如何用大小固定或变化的元组来表示这个问题。本节将利用大小固定的元组来研究一种回溯解法，在此情况下，解向量的元素X(i)取1或0值，它表示是否包含了权数W(i)。 生成图6.4中任一结点的子结点是很容易的。对于i级上的一个结点，其左子结点对应于X(i)=1，右子结点对应于X(i)=0。对于限界函数的一种简单选择是，当且仅当 k n ∑W(i)X(i) + ∑W(i)≥M 时，B(X(l),…,X(k))=true。 i=1 i=k+1 显然，如果这个条件不满足，X(1),…,X(k)就不能导致一个答案结点。如果假定这些W(i)一开始就是按非降次序排列的，那么这些限界函数可以被强化。在这种情况下，如果 k ∑W(i)X(i) + W(k+1)＞M i=1 则X(l),…,X(k)就不能导致一个答案结点。因此将要使用的限界函数是Bk((1),…,X(k))＝true 当且仅当 k n k ∑W(i)X(i) + ∑W(i)≥M 且 ∑W(i)X(i) + W(k+1)≤M (6.1) i=1 i=k+1 i=1 由于在即将拟制的算法中不会使用Bn，因此不必担心这个函数中会出现W(n+1)。至此已说明了直接使用6.l节介绍的两种回溯方案中任何一种方案所需要的一切。为简单起见，将算法6.2修改成适应求子集和数的需要便得到递归算法SumOfSub。 算法6.6 子集和数问题的递归回溯算法 void SumOfSub(s,k,r) { //找w(1:n)中和数为M的所有子集。进入此过程时x(1),…,X(k-1)的值已确定。 k-1 n //s=∑W(i)X(i)且r=∑W(j)。W(j)按非递减排列。假定w(1)≤M，∑W(i)≥M j=1 j=k l int M，n；float W[n]；bool X[n]； //M、W[n]、X[n]定义成全局变量 2 float r，s；int k，j； //生成左子结点。注意，由于Bk-1=true，因此s + w[k]≤M 3 X[k]=1； 4 if(s+w[k]==M)