B5-搜索与回溯算法

1、搜索与回溯算法搜索与回溯算法应用范围：遇到无法根据某种确定的计算法则来求解的问题，往往采用搜索所有可能情况的方法来进行求解。回溯是实现搜索的一种策略。回溯的基本思想：类似走迷宫，为了求得问题的解，先选择一种可能情况向前探索，一旦发现选择错误（无路可走了），则退回一步重新选择，然后继续向前探索。简单来说就是“走不通就掉头”。递归回溯算法框架int Search(int k)if (到目的地) 输出解;elsefor (i=1;i=算符种数;i+)if (满足条件) 保存当前结果;Search(k+1);恢复：撤销当前结果回溯一步搜索与回溯算法例1素数环从1到20这20个数摆成一个环，要求相邻的两

2、个数的和是一个素数。【算法分析】这是一道回溯的题目。从1开始，每个空位有20种可能，只要填进去的数合法：与前面的数不相同；与左边相邻的数的和是一个素数。第20个数还要判断和第1个数的和是否素数。【算法流程】1、数据初始化；2、递归填数：判断第i个数填入是否合法；A、合法：填数；判断是否到达目标（20个已填完）：是，打印结果；不是，填下一个数；B、不合法：选择下一种可能；有合法的数jai:=j没有合法的数a1a2ai-1a20aiai+1ai-1寻找下一个合法的数ai+1从1开始寻找合法的数搜索与回溯算法例1#include#include#include#includeusing namesp

3、ace std;#define N 10bool bN+1=0;/表示数字是否可用int total=0,aN+1=0;bool pd(int x,int y)/判断素数int k=2,i=x+y;while(ksqrt(i)return 1;else return 0;void print()/输出方案total+;couttotal;for(int j=1;j=N;j+)coutaj ;coutendl;int search(int t)/回溯过程int i;for(i=1;i=N;i+)/有N个数可选if(!bi)&(t=1|pd(at-1,i)/判断该数是否可用及与前一个数是否构成素数

4、at=i;bi=1;if(t=N)if(pd(aN,a1) print();else search(t+1);bi=0;int main()search(1);couttotalendl;/输出总方案数搜索与回溯算法例2设有n个整数的集合1,2,n，从中取出任意r个数进行排列（rn），试列出所有的排列。#include#include#includeusing namespace std;int num=0,a10001=0,n,r;bool b10001=0;int print()/输出方案num+;for (int i=1;i=r;i+)coutsetw(3)ai;coutendl; in

5、t search(int k)/回溯过程int i;for (i=1;i=n;i+)if(!bi)/判断i是否可用ak=i;/保存结果bi=1; /标记i不可用if (k=r) print();else search(k+1);bi=0; /标记i可用int main()coutnr;search(1);coutnumber=numendl;搜索与回溯算法例3自然数的拆分任何一个大于1的自然数n，总可以拆分成若干个小于n的自然数之和。根据n的值，输出拆分的方法总数。当n=7时，共有14种拆分方法：7=1+1+1+1+1+1+17=1+1+1+1+1+27=1+1+1+1+37=1+1+1+2+

6、27=1+1+1+47=1+1+2+37=1+1+57=1+2+2+27=1+2+47=1+3+37=1+67=2+2+37=2+57=3+4total=14搜索与回溯算法例3#include#include#includeusing namespace std;int a10001=1,n,total;int search(int,int);int print(int);/输出一种拆分方案int print(int t)coutn=;for (int i=1;i=t-1;i+)coutai+;coutatendl;total+;/方案数累加1/回溯过程，s为待拆分的数，t表示第几个拆分数in

7、t search(int s,int t)int i;/i是当前拆分出来的数for (i=at-1;i=s;i+) /i要大于等于前1位数if (in;search(n,1);/将待拆分的数n传递给scouttotal=totalendl;搜索与回溯算法例4八皇后问题要在国际象棋棋盘中放八个皇后，使任意两个皇后都不能互相吃。（提示：皇后能吃同一行、同一列、同一对角线的任意棋子。）1234567812345678搜索与回溯算法例4【算法分析】显然，每行有且仅有一个皇后。我们规定第i个皇后放置在第i行，用ai=j表示第i行皇后处于j列，然后逐行来放置皇后，即对每个i搜索合适的j值。/放置第i个(行

8、)皇后int search(i)；int j;for (第i个皇后的列位置j=1;j=8;j+ )if (i行j列允许放置皇后)放置第i个皇后，对放置皇后的位置进行标记；if (i=8) 输出/已经放完8个皇后elsesearch(i+1)；/放置第i+1个皇后取消放置，释放位置标记，尝试下一个位置是否可行；搜索与回溯算法例4第i个皇后能放置在j列的条件：j列没有其它皇后，j不重复，用数组b1.8判断对角线1没有其它皇后，i+j不重复：用数组c1.16判断对角线2没有其它皇后，i-j不重复：用数组d-7.7判断，但C数组下标从0开始，修正为i-j+7不重复，用数组d0.14判断12345678

9、12345678对角线2对角线1搜索与回溯算法例4#include#include#includeusing namespace std;bool d100=0,b100=0,c100=0;int sum=0,a100;int print()int i;sum+;/方案数累加1coutsum=sumendl;for (i=1;i=8;i+)/输出一种方案coutsetw(4)ai;coutendl;int search(int i)/放置第i个(行)皇后int j;for (j=1;j2,1-3,3-1,4-3,5-2,7-4,80123456784321搜索与回溯算法例5【算法分析】马最多有

10、四个方向，若原来的横坐标为j、纵坐标为i,则四个方向的移动可表示为：1:(i,j)(i+2,j+1)； (i3,j8)2:(i,j)(i+1,j+2)； (i4,j0,j1,j8)搜索策略：S1:A1:=(0,0);S2:从A1出发，按移动规则依次选定某个方向，如果达到的是(4,8)则转向S3,否则继续搜索下一个到达的顶点；S3:打印路径。(i,j)(i+2,j+1)(i+1,j+2)(i-1,j+2)(i-2,j+1)搜索与回溯算法例5#include#includeusing namespace std;int a100100,t=0;/a路径，t路径总数int x4=2,1,-1,-2,

11、y4=1,2,2,1; /四种移动规则坐标偏移量int print(int ii)t+;coutt: ;for (int i=1;i=ii-1;i+)coutai1,ai2;cout4,8endl;int search(int i)/搜索第i步for (int j=0;j=0/判断马不越界&ai-11+xj=0&ai-12+yj5：判断效益是否大于max，若大于max，则更新g及max逐级回溯step5,step4,step1，直至所有可能的选择都被尝试过J1J2J3J4J5A13111047B13101085C59774D151210115E1011884搜索与回溯算法例6#include#

12、includeusing namespace std;int data66=0,0,0,0,0,0,0,13,11,10,4,7,0,13,10,10,8,5,0,5,9,7,7,4,0,15,12,10,11,5,0,10,11,8,8,4;int max1=0,g10,f10;bool p6=0;int go(int,int); int main()go(1,0); /从第1个人，总效益为0开始for (int i=1;i=5;i+)coutchar(64+i):Jgisetw(3);/输出安排情况coutendl;coutsupply:max1endl;/安排第step个人的工作，t是之

13、前已得的效益int go(int step,int t)for (int i=1;i=5;i+)if (!pi)/判断第i项工作没人选择fstep=i;/第step个人，选第i项工作pi=1; /标记第i项工作被人安排了t+=datastepi;/计算效益值if(stepmax1)/如果当前效益最佳max1=t;/保存最佳效益值for (int j=1;j=5;j+)gj=fj; /保存方案/回溯，第setp人不安排i项工作t-=datastepi;/清除i项工作效益pi=0;/第i项工作未安排搜索与回溯算法例7选书学校放寒假时，信息学竞赛辅导老师有A，B，C，D，E五本书，要分给参加培训的张

14、、王、刘、孙、李五位同学，每人只能选一本书。老师事先让每个人将自己喜欢的书填写在如下的表格中。然后根据他们填写的表来分配书本，希望设计一个程序帮助老师求出所有可能的分配方案，使每个学生都满意。ABCDE张YY王YYY刘YY孙Y李YY搜索与回溯算法例7【算法分析】可用穷举法，先不考虑“每人都满意”这一条件，这样只剩“每人选一本且只能选一本”这一条件。在这个条件下，可行解就是五本书的所有全排列，一共有5!=120种。然后在120种可行解中一一删去不符合“每人都满意”的解，留下的就是本题的解答。为了编程方便，设1，2，3，4，5分别表示这五本书。这五个数的一种全排列就是五本书的一种分发。例如5432

15、1就表示第5本书（即E）分给张，第4本书（即D）分给王，第1本书（即A）分给李。“喜爱书表”可以用二维数组来表示，1表示喜爱，0表示不喜爱。算法设计：S1：产生5个数字的一个全排列；S2：检查是否符合“喜爱书表”的条件，如果符合就打印出来；S3：检查是否所有的排列都产生了，如果没有产生完，则返回S1；S4：结束。ABCDE张YY王YYY刘YY孙Y李YY搜索与回溯算法例7【算法分析】上述算法有可以改进的地方。比如产生了一个全排列12345，从表中可以看出，第一本书不可能是1的，因为张只喜欢第3、4本书。这就是说，1一类的分法都不符合条件。由此想到，如果选定第一本书后，就立即检查一下是否符合条件，

16、发现1是不符合的，后面的四个数字就不必选了，这样就减少了运算量。换句话说，第一个数字只在3、4中选择，这样就可以减少3/5的运算量。同理，每选择了一个数字后，就立即检查是否符合条件。例如，第一个数选3，第二个数选4后，立即检查，发现不符合条件，就应另选第二个数。这样就把34一类的分法在产生前就删去了。又减少了一部分运算量。 ABCDE张YY王YYY刘YY孙Y李YY搜索与回溯算法例7#include#include#includeusing namespace std;int book6,c;bool flag6,like66=0,0,0,0,0,0,0,0,0,1,1,0,0,1,1,0,0,

17、1,0,0,1,1,0,0,0,0,0,0,1,0,0,0,1,0,0,1;int print()c+;/方案数累加1cout answer c :n;for(int i=1;i=5;i+)cout i : /输出方案char(64+booki)endl;int search(int i)/分配第i人的书 for(int j=1;j=5; j+)/共有5本书if (flagj&likeij)/j可选flagj=0;/标记第j本书已选booki=j;/第i个人选中第j本if (i=5)/所有的人都分到书print();/输出方案 else/还有人没分配到书search(i+1);/分配下一个人f

18、lagj=1;/回溯，放回第j本书int main()for(int i=1;i=5;i+) flagi=1;search(1);/从第1个开始选书，递归。搜索与回溯算法例8跳马问题。在5*5格的棋盘上，有一只中国象棋的马，从(1,1)点出发，按日字跳马，它可以朝8个方向跳，但不允许出界或跳到已跳过的格子上，要求跳遍整个棋盘。输出前5个方案及总方案数。11621102520112415221721969127413143181385搜索与回溯算法例8#include#includeusing namespace std;int u8=1,2,2,1,-1,-2,-2,-1,/8个方向v8=-2

19、,-1,1,2,2,1,-1,-2;/x,y增量int a100100=0,/每一格的在第几步走到num=0;/总方案数int print()/打印方案num+;/统计总方案if(num=5)/打印出前5种方案 for (int k=1;k=5;k+)/打印方案 for(int kk=1;kk=5;kk+)coutsetw(5)akkk; cout25)/已做完所有格子print();return 0;/打印方案for (k=0;k=7;k+)/尝试往8个方向走x=i+uk;y=j+vk;/往k方向走的新坐标if(x=1&y=1&(!axy)/如果新坐标可以走axy=n;/第n步走到(x,y)

20、search(x,y,n+1);/从(x,y)搜n+1步走法axy=0;/回溯，第n步不走(x,y)int main() a11=1;/第1步在(1,1)search(1,1,2);/从(1,1)开始搜第2步走法coutnumendl;/输出总方案(共304)搜索与回溯算法例9数的划分(Noip2001)将整数n分成k份，且每份不能为空，任意两份不能相同(不考虑顺序)。例如：n=7，k=3，下面三种分法被认为是相同的。1,1,51,5,15,1,1问有多少种不同的分法。【输入格式】n，k (6n=200，2=k=6)【输出格式】一个整数，即不同的分法。【输入样例】73【输出样例】4四种分法为：

21、1,1,5；1,2,4;；1,3,3；2,2,3搜索与回溯算法例9【算法分析1回溯】考虑采用回溯法对k个数的值逐一进行枚举，当k个数的和等于n，找到了一个解。以n=7，k=3为例，初步判断每个数的范围为15，先考虑怎么枚举出由15组成的3个数组合：1 1 12 1 13 1 14 1 15 1 11 1 22 1 23 1 24 1 25 1 21 1 32 1 33 1 34 1 35 1 31 1 4 2 1 43 1 44 1 45 1 41 1 52 1 53 1 54 1 55 1 51 2 12 2 13 2 14 2 15 2 11 2 22 2 23 2 24 2 25 2 2

22、1 5 32 5 33 5 34 5 35 5 31 5 42 5 43 5 44 5 45 5 41 5 52 5 53 5 54 5 55 5 5观察上面的列表，结合我们的思维习惯，我们一般的枚举方法是：从每个数都是最小数的组合1 1 1开始最后一个数逐渐加1，依次枚举出1 1 2，1 1 3，直到加到6(超出最大限制)，转倒数第二个数加1，最后一个数置为最小：1 2 1，转，若倒数第二个数加到6(超出最大限制)，转倒数第三个数加1，其后的数全置为最小：2 1 1，转，若倒数第三个数加到6(超出最大限制)，结束搜索与回溯算法例9编程实现，枚举k个数的组合，假设每个数的范围为1Ms1.k存储

23、第1.k个数，i表示正在对第几个数进行操作s1=0;/初始化i=1;while(i)/若i=0，说明第一位已超过极限，结束si+;/第i个数加1if (si=m) /当前数未超过极限值if (i=k) /如果加1的是最后一个数，此时已产生一个新的组合根据需要，对新的组合进行相应操作;else/如果加1的不是最后一个数，则还需将其后的数置为最小数i+;/i指向下一个数，下一个循环将对si加1si=0;/在下一个循环加1后即成为最小数else i-; /如果当前数超过极限，在下一个循环中将对前一个数加1搜索与回溯算法例9本题指出，数字相同但顺序不同的组合视为同一个组合，而用前面的方法枚举出的组合是

24、有重复的，不能满足本题的要求。那么，怎样才不会产生重复的组合呢？只要保证每次产生的新组合都是不下降序列（后面的数不小于前面的数）即可避免重复，即在枚举组合中的每一数时，其最小值必须与前一个数相等，而不一定是1了。s1=0;/初始化i=1;while(i)/若i=0，说明第一位已超过极限，结束si+;/第i个数加1if (si=m) /当前数未超过极限值if (i=k) /如果加1的是最后一个数，此时已产生一个新的组合根据需要，对新的组合进行相应操作;else/如果加1的不是最后一个数，则还需将其后的数置为最小数i+;/i指向下一个数，下一个循环将对si加1si=si-1-1;/在下一个循环加1

25、后即等于前一个数，保证了数值的不下降else i-; /如果当前数超过极限，在下一个循环中将对前一个数加1搜索与回溯算法例9#includeusing namespace std;int n,i,j,k,sum,total;int s201;int main()cinnk;total=0;s1=0; i=1;while(i)si+;if(si=n-k+1)if (i=k)sum=0;for(j=1;j=k;j+) sum+=sj;if(n=sum) total+;else i+; si=si-1-1; else i-;couttotal;return 0;共有k个数，每个数大概有n种可能选择，

26、所以算法的时间复杂度为O(nk)题目的数据规模为(6n=200，2=k=6)，在最坏的情况下将会超时搜索与回溯算法例9搜索与回溯算法例9#includeusing namespace std;int n,k;int f(int a,int b,int c)int g=0,i;if (b=1)/递归边界，只划分1份g=1;elsefor (i=c;i n k;coutf(n,k,1);return 0;时间复杂度：由于在搜索每一位数字的数值时做到了保证有解没有重复，整个搜索过程没有无用或重复的搜索分支，因此时间复杂度跟本题的答案是同一个数量级别。答案的数量级别估算如下：1、不排除重复，把n分为k

27、份，有C(n-1,k-1)种分法2、n和k的数字越大，其中重复的比例越接近于A(k,k)所以估计本题的时间复杂度为O(C(n-1,k-1)/k!)当n=200，k=6时，时间复杂度为106搜索与回溯算法例9【算法分析3动态循环枚举】回到第一种思路，枚举出所有组合，然后逐一判断组合是否满足条件。在数据规模较大时，将因为组合数量很大而超时。事实上，绝大部分的组合是不满足条件的，如果能减少或不枚举不满足条件的组合，那么将极大地节省运行时间，这在搜索中称为剪枝。以n=7，k=3为例：第1个数的枚举范围为12第2个数的枚举范围根据第1个数动态调整1 ：剩余6，第2个数的枚举范围为132 ：剩余5，第2个

28、数的枚举范围为22第3个数即最后1个数必须等于剩余的数，不需枚举假设在枚举第dep个数时，还剩余rest，第det-1个数为last，若depk，则第i个数的枚举范围是lastrest/(k-dep+1)若dep=k，则第i个数等于rest，得到一个满足条件的组合搜索与回溯算法例9#includeusing namespace std;int n,k,total;void select(int dep,int rest,int last)int i;if (dep=k)/最后1个数只能等于rest，不需枚举，得到一个解total+;else for (i=last;ink;total=0;select(1,n,1);/从第一个数开始枚举couttotal;return 0; 时间复杂度参照上一个解法上机练习1、全排列问题：输出自然数1到n所有不重复的排列，即n的全排列，要求所产生的任一数字序列中不允许出现重复的数字。2、组合的输出：排列与组合是常用的数学方法，其中组合就是从n个元素中抽出r个元素(不分顺序且rn)，我们可以简单地将n个元素理解为自然数1，2，n，从中任取r个数。现要求你用递归的方法输出所有组合。3、N皇后问题：在N*N的棋盘上放置N个皇后（n=10）而彼此不受攻击（即在棋盘的任一行，任一列和任一对角线上不能放置2个皇后），编程求解所有的