回溯与解空间树.ppt

1、回溯法有 “通用的解题法”之称。 很多问题在无法有确定的计算规则时，可以通过试探回溯的办法来求解 例如，八皇后问题，背包问题,地图着色问题 ,求幂集的问题等等。 它是一种选优搜索法，按选优条件向前搜索，以达到目标。当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，直到最终确定一个或多个解，或确定无解。 解空间树,幂集（子集）问题(组合问题)：求含N个元素的集合的幂集 如对于集合A=1,2,3,则A的幂集 ,1,2,3,1,2,1,3,2,3,1,2,3 集合A中的每一个元素，它只有两种状态：属于/不属于 幂集元素集。 故：求幂集 的元素的过程可看成是依次对集合A中元素进行“

2、取”或“舍”的过 程，叶子即为解。 求幂集元素的过程即为先序遍历这棵状态树的过程。,1 2 3,int a3=1,2,3,b3 /b 存放解 void f(int i ) if (i=3)输出b else ai b ; /取第i个 f(i+1 ); /做下一个 b - = ai /舍第i个 f(i+1 ); /做下一个 void main() f(0); ,求子集的算法思想,#include iostream.h int a3=1,2,3,b3 ,k=0,n=3; /b 存放解 void f(int i ) if (i=n) for(int j=1;jn ! 因为从0开始，=n 已是超过了叶子

3、 else b+k=ai; /取第i个 f(i+1 ); /做下一个 k-; /舍第i个 f(i+1 ); /做下一个 void main() f(0); ,求子集最简解法,include int w =1,2,3,x3, n=3 , count=0; void f(int i) if (i=n) for( int j=0;jn;j+) if(xj) cout wj;cout endl;count+;return; xi=1; /取第i个 f(i+1); /做下一个 xi=0; /舍第i个 f(i+1); /做下一个 void main() f(0); cout子集个数 count; ,求子集

4、 的规范解法,进一阶：求子集和即求和满足某个数的子集例：集合为w=2,3,6,5,4; 输出和为10 的所有子集,include int w =2,3,6,5,4, c=10, n=5, x5, cw=0; void f(int i) if (i=n) return; xi=1;cw+=wi; /取第i个 if (cwc) f(i+1); /做下一个 if (cw=c) for( int j=0;jn;j+) if(xj) cout wj;coutendl; xi=0; cw-=wi; /舍第i个 f(i+1); /做下一个 void main() f(0); ,思路：对于每一个物品i，对于该

5、物品只有选与不选2个决策，总共有n个物品，依次考虑每个物品，就形成了一棵解空间树：,0-1背包问题(练习） 假设有一个能装入总体积为C的背包和n件体积分别为w1 ,w2 , , wn 的物品，能否从n件物品中挑选若干件恰好装满背包，即使w1 +w2 + + wi=C， 找出所有满足上述条件的解。 例如：当C=10，各件物品的体积 1，8，4，3，5，2 时，可找到下列4组解： （1，4，3，2）（1，4，5） （8，2） （3，5，2）,1 8 4 3 5 2,/ 简单01背包问题：即仅满足重量W（即子集和数问题）,#include iostream.h“ int w=5,6,8,2,x4 ,

6、n=4,c=13,sum=0; void f(int i) if (i=n) return; else xi=1;sum=sum+wi; /取第i个 if (sumc) f(i+1); /做下一个 if (sum=c) for(int j=0;jn;j+) if(xj) coutwj ; cout endl; xi=0; sum-=wi; /舍第i个 f(i+1); /做下一个 void main() f(0); ,复杂01背包问题：在总重量不超过限度的前提下，求最大价值的组合例：重量集为w =16,14,25;价值集为p =45,23,37 ;重量上界为 c=42;结果为 16，25即选取第

7、一三号物品，重量和为41，价值为82编程思路？,再进一阶,/01背包；在总重量不超的前提下求最大价值的组合; #include int w =16,14,25, p =45,23,37,c=42;/重量上界 const n=3; int cw=0,cp=0,xn, bestxn,bestp=0; void f(int i) if (i=n) return; xi=1; cw+=wi;cp+=pi; /取第i个 if(cwbestp) bestp=cp; for( int j=0;jn;j+) bestxj=xj; if (cw=c) f(i+1); /做下一个 xi=0; cw-=wi;cp-

8、=pi; /舍第i个 f(i+1); /做下一个 void main() f(0); for( int j=0;jn;j+) if(bestxj) coutwj ; coutendlbestpendl; ,考过的相关的题 1、 模拟题 2.8 代码设计（满分11分） 某游戏规则中，甲乙双方每个回合的战斗总是有一方胜利，一方失败。 游戏规定：失败的一方要把自己的体力值的1/4加给胜利的一方。 例如：如果双方体力值当前都是4，则经过一轮战斗后，双方的体力值会变为：5，3。 现在已知：双方开始时的体力值甲：1000，乙：2000。 假设战斗中，甲乙获胜的概率都是50% 求解：双方经过4个回合的战斗，

9、体力值之差小于1000的理论概率。,思路： 因为甲、乙的胜率各占50%，选择2叉树。 1回合结束后，根节点-第一层有2个叶子节点（分别对应甲获胜以后的生命值、以及乙获胜以后的生命值） 以此类推，4回合以后，必定是16个叶子节点（算上根节点一共5层） 只要在叶子节点中，选择1000生命值的节点个数，最后比上分母16，即可得出概率。,#include iostream.h #include math.h int a=1000,b=2000 ,count=0,n=4; void f(int i ) int x,y; /x,y要设为局部变量 if (i=n) if (abs(a-b)1000) cou

10、nt+; return;/满足条件，计数 else x=a; y=b; /保存根 a+=b*1/4; b-=b/4; /取左分枝，即甲胜 f(i+1); /做下一回合 a=x; b=y;/回溯回上一层，取回上一层的值 b+=a/4; a-=a/4; /舍左分枝，取右分枝，即乙胜 f(i+1); /做下一回合 void main() f(0); cout(double)countendl; cout(double)count/(double)16; /注意要转为double，想想WHY?,2、2012 8 分*某电视台举办了低碳生活大奖赛。题目的计分规则相当奇怪： 每位选手需要回答10个问题（其

11、编号为1到10），越后面越有难度。答对的，当前分数翻倍； 答错了则扣掉与题号相同的分数（选手必须回答问题，不回答按错误处理）。 每位选手都有一个起步的分数为10分。 某获胜选手最终得分刚好是100分，如果不让你看比赛过程，你能推断出他（她）哪个题目答对了， 哪个题目答错了吗？如果把答对的记为1，答错的记为0，则10个题目的回答情况可以用仅含有1和0的串来表示。 例如：0010110011 就是可能的情况。,思路：,#include int cw=10，n=10; int x11; /从1开始，所以数组定义为11 void f(int i) if (in) if (cw=100)for( int

12、 j=1;j=n;j+) coutxj ; coutendl; return; int cwcopy=cw; xi=1; cw=2*cw; /取第i个 f(i+1); /做下一个 cw=cwcopy; /cw=cw/2错 cw=cw-i; xi=0; /舍第i个 if(cw0) return; else f(i+1); /做下一个 void main() f(1); /注意，此题要从1 开始 ,第二类解空间树：多枝树,对应情况：每一层有多种选择，不再是非0即1 例换硬币问题 一元钱，可换1角、2角、5角的硬币，问可以有哪些方案 相当于 w=1,2,5; c=10; 区别 wi 可取多次，如五个

13、2角，所以是多枝树 解题思路，每一层做一个循环,#include int count=0, x3,c=10,w=1,2,5; void f (int i) if (i = 3) /到叶子，处理结果 if (c=x0*1 + x1*2 + x2*5) count+; coutcount种:1角 x0个, 2角 x1个, 5角 x2个endl; /return; else for(int j=0; j=c/wi; j+) /做分枝 xi=j; f(i+1); /做下一层 void main() f(0);,4皇后问题，阅读程序,练习：2011-9. 程序设计（满分16分） 公司发了某商店的购物券1

14、000元，限定只能购买店中的m种商品。每种商品的价格分别为w1,w2,， 要求程序列出所有的正好能消费完该购物券的不同购物方法 例如：m=2,价格w=200,300,# include const n=2; int w=200,300, xn，c=1000;/购物券 void f(int i) if (i=n) /到叶子,处理结果 int sum=0;for (int k=0;ki;k+) sum+=xk*wk; /算总值 if (sum=c) /满足条件则输出 for (int k=0;ki;k+) coutxk个 wk ; coutendl; else for(int j=0; j=c/w

15、i; j+) /不到叶子，处理分枝 xi=j; f(i+1); /处理下一层 void main(void) f(0); ,排列树,当所给问题是从n个元素的集合S中找出满足某种性质的子集时，解空间为 子集树。这类子集树通常有2n个节叶节点。所需要的时间复杂度是O（2n）;当所给的问题确定n个元素满足某种性质的排列时，相应的解空间树成为排列树。排列树有n！个叶结点。因此遍历该树所用的时间复杂度是O（n!）,回溯法搜索子集树算法描述为： void backtrack (int t) if (tn) output(x); else for (int i=0;i=1;i+) xt=i; if (leg

16、al(t) backtrack(t+1); ,回溯法搜索排列树的描述为： void backtrack (int t) if (tn) output(x); else for (int i=t;i=n;i+) swap(xt, xi); if (legal(t) backtrack(t+1); swap(xt, xi); 在调用Backtrack(1)执行回溯调用之前，先将变量数组x初始化单位排列(1,2,n)。,例：给定一个字符串，其含有的字符各不相同。程序输出该字符串的所有排列（全排列）情形。例如：给定字符串xyz，则程序输出： xyz xzy yxz yzx zyx zxy,#include const n=3; char temp ,x=A,B,C; int count=0; void f(int i) if (i = n) /到叶子，处理结果 count+; for(int