算法第2章_穷举与回溯

《算法第2章_穷举与回溯》由会员分享，可在线阅读，更多相关《算法第2章_穷举与回溯（41页珍藏版）》请在金锄头文库上搜索。

1、算法设计与分析2.1 穷举及其应用2.2 穷举设计的优化2.3 回溯法及其描述2.4 回溯设计应用2.5 回溯设计的优化算法设计与分析2.1.1 穷举概述 穷举法又称列举法，其基本思想是逐一列举问穷举法又称列举法，其基本思想是逐一列举问 题所涉及的所有情况。题所涉及的所有情况。 穷举法常用于解决穷举法常用于解决“ “是否存在是否存在” ”或或“ “有多少种可能有多少种可能 ” ”等问题。等问题。 应用穷举法时应注意对问题所涉及的有限种情应用穷举法时应注意对问题所涉及的有限种情 形须一一列举，既不能重复，又不能遗漏。形须一一列举，既不能重复，又不能遗漏。 穷举通常应用循环结构来实现。在循环体中，

2、穷举通常应用循环结构来实现。在循环体中， 应用选择结构实施判断筛选，求得所要求的解。应用选择结构实施判断筛选，求得所要求的解。2.1 穷举及其应用算法设计与分析穷举法的框架描述：n=0;for(k=;k;k+) /* 据指定范围实施穷举 */if() /* 据约束条件实施筛选 */ printf(); /* 输出解 */n+; /* 统计解的个数 */算法设计与分析【例例2.22.2】统计分母在区间统计分母在区间 a,ba,b 的最简真分数的最简真分数( (分子小于分分子小于分 母，且分子分母无公因数母，且分子分母无公因数) )共有多少个共有多少个, ,并求最简真分数升序并求最简真分数升序 序

3、列中的第序列中的第k k项项( (正整数正整数a,b,ka,b,k从键盘输入从键盘输入) )。算法设计算法设计: : 为排序方便，设置数组 为排序方便，设置数组c c存储分子，数组存储分子，数组d d存储分母。真存储分母。真 分数升序排序后的第分数升序排序后的第k k项为项为c(k)/d(kc(k)/d(k) )。 在 在 a,ba,b 内穷举分数内穷举分数i/ji/j的分母的分母j: a,a+1,bj: a,a+1,b； 对每一个分母 对每一个分母j j穷举分子穷举分子i: 1,2,j-1i: 1,2,j-1。 若分子 若分子i i与分母与分母jj存在大于存在大于1 1的公因数的公因数, ,

4、说明说明i/ji/j非最简非最简, ,忽忽 略不计；否则赋值得一个最简真分数略不计；否则赋值得一个最简真分数c(n)/d(nc(n)/d(n) )。 数组下标数组下标 n n统计最简真分数的个数。应用冒泡法排序后即可打印出指统计最简真分数的个数。应用冒泡法排序后即可打印出指 定的第定的第k k项项c(k)/d(kc(k)/d(k) )。算法设计与分析程序片段： n=0;/n统计个数 for(j=a;j 2x+3yA试求集合A元素从小到大排列的序列的前n项。（1） 按第n项的大小循环设计 x,y可以是已产生的所有已有项中的任意两项，已产生 项越多，递推生成的新项也就越多。 穷举循环变量k从3开始

5、递增1取值,到第n项时k的终值尚 无法确定，可约定一个较大的终值（例如10000）。 若k可由已有的项a(j)，a(i) (j0) x=y%10;fx=fx+1;y=y/10;k+;gk=x; /分离各数字for (t=0,i=1;i=0)m+; printf(“%d %d %d”,p1,p2,p3);printf(“%d %d %d”,p4,p5,p6); printf(“%d(1,2,5,10,20,50)=%ldn”,n,m);算法设计与分析2.3 回溯法及其描述 2.3.1 回溯的基本概念 回溯法找出求解问题的线索往前试探，若试探成功， 即得到解；若试探失败，就逐步往回退，换其他路线

6、再往前试探。 回溯法可以形象地概括为“向前走，碰壁回头”。 与穷举法相比，回溯法的“聪明”之处在于能适时“ 回头”，若再往前走不可能得到解，就回溯，退一步 另找线路，这样可省去大量的无效操作。 应用回溯设计求解实际问题，由于解空间的结构差异 ，而且很难计算与估计回溯产生的结点数，因此回溯 计算复杂度是分析回溯法效率时遇到的主要困难。 回溯法产生的结点数通常不足解空间结点数的3%，这 也是回溯法的计算效率大大高于穷举法的原因所在。算法设计与分析 2.3.2 回溯法描述 1. 回溯的一般方法算法设计与分析 2. 回溯算法框架描述 /* 输入正整数n,m,(nm) */ i=1;ai=; while

7、 (1) g=1;for(k=i-1;k=1;k-) if( ) g=0; /* 检测,不满足则返回 */ if(g /* 输出一个解 */ if(i;continue; while(ai= /* 向前回溯 */ if(ai=n /* 退出循环，结束 */ else ai=ai+1; 算法设计与分析 2.3.3 回溯法的效益分析 回溯法的时间通常取决于状态空间树上实际生成的那 部分问题状态的数目。对于元组长度为n的问题，若其 状态空间树中结点总数为n!，则回溯算法的最坏情形 的时间复杂度可达O(p(n)n!)； 对于某一具体实际问题的回溯求解，常通过计算实际 生成结点数的方法即蒙特卡罗方法（M

8、onte carlo）来 评估其计算效率。 把所求得的随机路径上的结点数（或若干条随机路径 的结点数的平均值）与状态空间树上的总结点数进行 比较，由其比值可以初步看出回溯设计的效益。 算法设计与分析2.4 回溯设计应用 2.4.1 2.4.1 桥本分数式桥本分数式 1. 问题提出 日本数学家桥本吉彦教授于1993年10月在我国山东举行 的中日美三国数学教育研讨会上向与会者提出以下填数 趣题: 把1,2,.,9这9个数字填入下式的九个方格中( 数字不得重复),使下面的分数等式成立 + = 桥本教授当即给出了一个解答。这一分数式填数趣题究 竟共有多少个解答? 试求出所有解答。(等式左边两个 分数交

9、换次序只算一个解答)。 算法设计与分析1. 回溯算法设计 设置a数组,式中每一位置用一个数组元素来表示 . 为判断数字是否重复,设置中间变量g：若出现某两数字相同 (即a(i)=a(k)或a(1)a(4),则赋值g=0(重复标记)。 首先从a(1)=1开始,逐步给a(i)(1i9)赋值,每一个a(i) 赋值从1开始递增至9。直至a(9)赋值,判断： 若i=9,g=1,等式同时满足,则为一组解,用n统计解的个数后, 格式打印输出这组解。 若i; while (1) g=1;for(k=i-1;k=1;k-) if( ) g=0; /* 检测,不满足返回 */ if(g /* 输出一个解 */ i

10、f(i;continue; while(ai= /* 回溯 */ if(ai=n /* 退出循环，结束 */ else ai=ai+1; 算法设计与分析 算法描述 输入n=m=9; i=1; ai=1; while (1) g=1;for(k=i-1;k=1;k-) if(ai=ak|a1a4 ) g=0; /* 检测,不满足返回 */ if(g /* 输出一个解 */ if(i1) i-; /* 回溯 */ if(ai=n /* 退出循环，结束 */ else ai=ai+1; 算法设计与分析 2.4.2 排列组合 1. 实现排列A(n,m) 对指定的正整数m,n(约定11) i-; /*

11、回溯 */ if(ai=n /* 退出循环，结束 */ else ai=ai+1; 算法设计与分析 3. 程序变通 注意到组合与组成元素的顺序无关，约定组合中的组成元素 按递增排序。因而，把以上程序中的约束条件1（ aj=ai）修改为aj=ai，即可实现从n个不同元素 中取m个(约定1n+1且a(i)=1时回溯； 当i=n+1且a(i)=1时退出。 当a(n)a(m-2)已取数字时，设置h统计其中0的个数， 若hm/2-n，则返回； 若h=m/2-n，判断是否有相同的由n个数字组成的二进制数 。若存有相同的，标注t=1；若不存在有相同的，保持t=0, 作打印输出。 算法设计与分析 3算法描述

12、输入正整数n,计算m=2n; an=1; am-1=1; i=n+1; while (1) if(aj=ai ) g=0; /* 检测,不满足返回 */ if(i=m-2 /* 输出一个解 */ if(in+1) i-; /* 回溯 */ if(ai=1 /* 退出，结束 */ else ai=ai+1; 算法设计与分析 1. n皇后问题 要求在nn方格棋盘放置n个皇后使它们不相互攻击(即 任意两个皇后不允许处在同一横排,同一纵列,也不允许处在 同一与棋盘边框成45度角的斜线上。正整数n从键盘输入 ,n2)。 2. 回溯探求设计 设置数组a(n),数组元素a(i)表示第i行的皇后位于第 a(i

13、)列.求n皇后问题的一个解,即寻求a数组的一组取值,该 组取值中每一元素的值互不相同(即没有任两个皇后在同一 列),且第i个元素与第k个元素相差不为abs(i-k),(即任两个 皇后不在同一45度角的斜线上)。2.4.4 高斯皇后问题及其拓广算法设计与分析 首先a(1)从1 开始取值。然后从小到大选择一个不同于 a(1)且与a(1)相差不为1的整数赋给a(2)。再从小到大选择 一个不同于a(1),a(2)且与a(1)相差不为2,与a(2)相差不为 1的整数赋给a(3)。依此类推,至a(n)也作了满足要求的赋值 ,打印该数组即为找到的一个n皇后的解。 为了检验a(i)是否满足上述要求,设置标志变

14、量g,g赋初 值1。若不满足上述要求,则g=0。按以下步骤操作: 令 x=abs(a(i)-a(k) (k=1,2,.,i-1)判别:若x=0 或 x=i-k ,则g=0。 若出现g=0,则表明a(i)不满足要求,a(i)调整增1后再 试,依此类推。 若i=n且g=1,则满足要求,用s统计解的个数后，格式 打印输出这组解。 若i=1;k+) x=absf(ai-ak); if(ak=ai /* 检测,不满足返回 */ if(g /* 输出一个解 */ if(i1) i-; /* 回溯 */ if(ai=n /* 退出，结束 */ else ai=ai+1; 算法设计与分析4. 时间测试算法设计与分析2.5 回溯设计的优化回溯算法在搜索执行的同时产生解空间，是一种系 统地搜索问题解答的方法。回溯算法避免了生成那 些不可能产生解的状态，不断去除那些实际上不可 能产生所需解的结点，