6--回溯法.ppt

第五章 回溯法 * 2. 算法设计 对n后问题，可用n元组x[1:n]表示它的解。其中，x[i]表示皇后i放在棋盘的第i行的第x[i]列。 若2个皇后放置的位置分别是(i,x[i])和(k,x[k])，则约束条件为： x[i]≠ x[k] (不在同一列) x[i]-i≠ x[k]-k , i+ x[i] ≠k+ x[k] (不在同一斜线) 即|i- k|≠|j- l| 用回溯法解n后问题时，可以用一棵完全n叉树来表示其解空间。用可行性约束函数Place可剪去不满足行、列和斜线约束的子树。 * #includestdio.h ?? #define?N?15 ?? int?n;?//皇后个数 ?? int?sum?=?0;?//可行解个数 int?x[N];?//皇后放置的列数 ?? int?place(int?k) ?? {int?i; ?? ?for(i=1;ik;i++) ?? ???if(abs(k-i)==abs(x[k]x[i])?||?x[k]?==?x[i]) ?? ????????return?0; ?? ?return?1; ?? }??? ? * int Backtrack(int m){ int sum=0; if (m n)  { sum++;  for (int i=1;i=n;i++)  cout x[i] ’ ’ ;  cout endl;  }  else  for (int i=1;i=n;i++)  { x[m]=i;  if (Place(m) )  Backtrack(m+1) ; } return sum;} * int?main() ?? { ?? t?=?Backtrack(1); ?if(n?==?0) t?=?0; //如果n=0，则可行解个数为0，这种情况一定不要忽略 ?? ???printf(%d,t); ?????return?0; ?? }?? ? * 算法分析: 解空间树中内结点个数： 对每个内结点，函数Place检查当前扩展结点的每一个儿子是否可放当前列需耗时O(n2)。 总的时间耗费是 = =O(nn+1) 回溯法的一般框架——递归形式 Backtrack(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是部分解) Backtrack(k+1); 主算法 1．X={ }; 2. flag=false; 3. Backtrack(1); 4. if (flag) 输出解X; else输出“无解”; 6.3 回溯法一般框架 在问题的解向量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!)时间。 6.4 回溯法的时间性能 6.5 回溯法的其它问题 6.5.1 素数环问题 6.5.2 图中的回溯问题 6.5.3 组合数学中的回溯问题 6.5.1 回溯法的其它问题之素数环问题 1 2 3 4 【问题】把整数{1, 2, …, 20}填写到一个环中，要求每个整数只填写一次，并且相邻的两个整数之和是一个素数。 【想法】这个素数环有20个位置，每个位置可以填写的整数有1~20共20种可能，可以对每个位置从1开始进行试探，约束条件是正在试探的数满足如下条件： （1）与已经填写到素数环中的整数不重复； （2）与前面相邻的整数之和是一个素数； （3）最后一个填写到素数环中的整数与第一个填写的整数之和是一个素数。 在填写第k个位置时，如果满足上述约束条件，则继续填写第k+1个位置；如果1~20个数都无法填写到第k个位