第2章 穷举与回溯.ppt

Visual FoxPro 例子1：百钱买百鸡问题 一百个铜钱买了一百只鸡，其中公鸡一只5钱，母鸡一只3钱，小鸡一钱3只，问一百只鸡中公鸡、母鸡、小鸡各多少） 例子2：换零钱 计算把一张1元整币兑换成1分,2分,5分,1角,2角,5角共6种零币的不同兑换种数。 （２） 按项数循环设计 已知前2项，t循环从3开始递增1取值到指定的项数n。 第一项的值k从2开始递增取值，对每一个k取值，标记h=0赋值； 若k可由已有的项a(j)，a(i) (ji)推得，即若k满足条件k=2*a[j]+3*a[i] 或 k=2*a[i]+3*a[j]，说明k是a数列中的一项，赋值给a(t)，同时标记h=1赋值。 对某项数t若h=0时，则t减1后循环，即对于原t使k增值后继续，直到达到规定项数n为止。 2.2.1 优选穷举对象 选择合适的穷举对象是穷举优化的首要条件。 【例2.4】 把一个6位整数分为前后两个3位数,若该数等于所分两个3位数和的平方,则称该数为6位分段和平方数。试求出所有6位分段和平方数。 （1) 对所有6位数穷举 （2) 对3位数穷举 2.2.2 优化穷举循环参量 优化穷举循环参量可减少无效循环，提高穷举效率。 【例2.6】 求解高斯八皇后问题。 在国际象棋的8×8方格的棋盘上如何放置8个皇后,使得这8个皇后不能相互攻击。 算法设计： 高斯八后问题的一个解用一个八位数表示,八位数解的第k个数字为j,表示棋盘上的第k行的第j格放置一个皇后。 两个皇后不允许处在同一横排,同一纵列，要求八位数中数字1—8各出现一次，不能重复。 因而解的范围区间应为87654321]。注意到数字1—8的任意一个排列的数字和为9的倍数，即数字1—8的任意一个排列均为9的倍数，因而穷举a循环的穷举范围定为87654321]，其循环步长可定为9。 2.2.3 精简穷举循环 精简一些不必要的循环，可大大提高穷举的效率。 【例2.7】 整币兑零求解。 计算把一张1元整币兑换成1分,2分,5分,1角,2角,5角共6种零币的不同兑换种数。 （1） 穷举设计求解 设面值为1，2，5，10，20，50单位零币的个数分别为p1,p2,p3,p4,p5,p6。设置穷举的6重循环。 （2） 精简穷举循环设计 在上述程序的6重循环中，我们可精简p1循环。 （3） 穷举设计的进一步优化 在循环设置中，p3循环从0—n/5可改进为0—(n-2*p2)/5。 2.3 回溯法及其描述 2.3.1 回溯的基本概念 回溯法找出求解问题的线索往前试探，若试探成功，即得到解；若试探失败，就逐步往回退，换其他路线再往前试探。 回溯法可以形象地概括为“向前走，碰壁回头”。 与穷举法相比，回溯法的“聪明”之处在于能适时“回头”，若再往前走不可能得到解，就回溯，退一步另找线路，这样可省去大量的无效操作。 应用回溯设计求解实际问题，由于解空间的结构差异，而且很难计算与估计回溯产生的结点数，因此回溯计算复杂度是分析回溯法效率时遇到的主要困难。 回溯法产生的结点数通常不足解空间结点数的3%，这也是回溯法的计算效率大大高于穷举法的原因所在。 2.3.2 回溯法描述 1. 回溯的一般方法 2. 回溯算法框架描述 /* 输入正整数n,m,(n≥m) */ i=1;a[i]=元素初值; while (1) { g=1;for(k=i-1;k=1;k--) if( 约束条件1 ) g=0; /* 检测,不满足则返回 */ if(g 约束条件2) printf(a[1-m]); /* 输出一个解 */ if(in g) {i++;a[i]=取值点;continue;} while(a[i]==回溯点 i1) i--; /* 向前回溯 */ if(a[i]==n i==1) break; /* 退出循环，结束 */ else a[i]=a[i]+1; } 2.3.3 回溯法的效益分析 回溯法的时间通常取决于状态空间树上实际生成的那部分问题状态的数目。对于元组长度为n的问题，若其状态空间树中结点总数为n!，则回溯算法的最坏情形的时间复杂度可达O(p(n)n!)； 对于某一具体实际问题的回溯求解，常通过计算实际生成结点数的方法即蒙特卡罗方法（Monte carlo）来评估其计算效率。 把所求得的随机路径上的结点数（或若干条随机路径的结点数的平均值）与状态空间树上的总结点数进行比较，由其比值可以初步看出回溯设计的效益。 2.4 回溯设计应用 2.4.1 桥本分数式 1. 问题提出 日本数学家桥本吉彦教授于1993年10月在