搜索与回溯算法(C++)ppt课件.ppt
《搜索与回溯算法(C++)ppt课件.ppt》由会员分享,可在线阅读,更多相关《搜索与回溯算法(C++)ppt课件.ppt(45页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、第五章第五章 搜索与回溯算法搜索与回溯算法资金是运动的价值,资金的价值是随时间变化而变化的,是时间的函数,随时间的推移而增值,其增值的这部分资金就是原有资金的时间价值 搜索与回溯是计算机解题中常用的算法,很多问题无法根据搜索与回溯是计算机解题中常用的算法,很多问题无法根据某种确定的计算法则来求解,可以利用搜索与回溯的技术求解。某种确定的计算法则来求解,可以利用搜索与回溯的技术求解。回溯是搜索算法中的一种控制策略。它的基本思想是:为了求得回溯是搜索算法中的一种控制策略。它的基本思想是:为了求得问题的解,先选择某一种可能情况向前探索,在探索过程中,一问题的解,先选择某一种可能情况向前探索,在探索过
2、程中,一旦发现原来的选择是错误的,就退回一步重新选择,继续向前探旦发现原来的选择是错误的,就退回一步重新选择,继续向前探索,如此反复进行,直至得到解或证明无解。索,如此反复进行,直至得到解或证明无解。如迷宫问题:进入迷宫后,先随意选择一个前进方向,一步如迷宫问题:进入迷宫后,先随意选择一个前进方向,一步步向前试探前进步向前试探前进,如果碰到死胡同,说明前进方向已无路可走,如果碰到死胡同,说明前进方向已无路可走,这时,首先看其它方向是否还有路可走,如果有路可走,则沿该这时,首先看其它方向是否还有路可走,如果有路可走,则沿该方向再向前试探;如果已无路可走,则返回一步,再看其它方向方向再向前试探;如
3、果已无路可走,则返回一步,再看其它方向是否还有路可走;如果有路可走,则沿该方向再向前试探。按此是否还有路可走;如果有路可走,则沿该方向再向前试探。按此原则不断搜索回溯再搜索,直到找到新的出路或从原路返回入口原则不断搜索回溯再搜索,直到找到新的出路或从原路返回入口处无解为止。处无解为止。资金是运动的价值,资金的价值是随时间变化而变化的,是时间的函数,随时间的推移而增值,其增值的这部分资金就是原有资金的时间价值递归回溯法算法框架递归回溯法算法框架一一int Search(int k)for(i=1;i=算符种数算符种数;i+)if(满足条件满足条件)保存结果保存结果if(到目的地到目的地)输出解输
4、出解;else Search(k+1);恢复:保存结果之前的状态恢复:保存结果之前的状态回溯一步回溯一步 递归回溯法算法框架递归回溯法算法框架二二int Search(int k)if (到目的地到目的地)输出解输出解;elsefor(i=1;i=算符种数算符种数;i+)if (满足条件满足条件)保存结果保存结果;Search(k+1);恢复:保存结果之前的状态恢复:保存结果之前的状态回溯一步回溯一步资金是运动的价值,资金的价值是随时间变化而变化的,是时间的函数,随时间的推移而增值,其增值的这部分资金就是原有资金的时间价值【例例1】素数环素数环:从从1到到20这这20个数摆成一个环,要求相邻的
5、两个数的和是一个素个数摆成一个环,要求相邻的两个数的和是一个素数。数。【算法分析算法分析】非常明显,这是一道回溯的题目。从1开始,每个空位有20种可能,只要填进去的数合法:与前面的数不相同;与左边相邻的数的和是一个素数。第20个数还要判断和第1个数的和是否素数。【算法流程】1、数据初始化;2、递归填数:判断第i个数填入是否合法;A、如果合法:填数;判断是否到达目标(20个已填完):是,打印结果;不是,递归填下一个;B、如果不合法:选择下一种可能;【参考程序参考程序】#include#include#include#includeusing namespace std;bool b21=0;in
6、t total=0,a21=0;int search(int);/回溯过程回溯过程int print();/输出方案输出方案bool pd(int,int);/判断素数判断素数 资金是运动的价值,资金的价值是随时间变化而变化的,是时间的函数,随时间的推移而增值,其增值的这部分资金就是原有资金的时间价值int main()search(1);couttotalendl;/输出总方案数输出总方案数 system(pause);int search(int t)int i;for(i=1;i=20;i+)/有有20个数可选个数可选 if(pd(at-1,i)&(!bi)/判断与前一个数是否构成素数及
7、该数是否可用判断与前一个数是否构成素数及该数是否可用 at=i;bi=1;if(t=20)if(pd(a20,a1)print();else search(t+1);bi=0;int print()total+;couttotal;for(int j=1;j=20;j+)coutaj;coutendl;bool pd(int x,int y)int k=2,i=x+y;while(ksqrt(i)return 1;else return 0;资金是运动的价值,资金的价值是随时间变化而变化的,是时间的函数,随时间的推移而增值,其增值的这部分资金就是原有资金的时间价值【例【例2】设有设有n个整数的
8、集合个整数的集合1,2,n,从中取出任意,从中取出任意r个数进行排列个数进行排列(rn),试列出所有的排列。),试列出所有的排列。#include#include#includeusing namespace std;int num=0,a10001=0,n,r;bool b10001=0;int search(int);/回溯过程回溯过程int print();/输出方案输出方案int main()coutnr;search(1);coutnumber=numendl;/输出方案总数输出方案总数资金是运动的价值,资金的价值是随时间变化而变化的,是时间的函数,随时间的推移而增值,其增值的这部分
9、资金就是原有资金的时间价值intsearch(intk)inti;for(i=1;i=n;i+)if(!bi)/判断i是否可用ak=i;/保存结果bi=1;if(k=r)print();elsesearch(k+1);bi=0;intprint()num+;for(inti=1;i=r;i+)coutsetw(3)ai;coutendl;资金是运动的价值,资金的价值是随时间变化而变化的,是时间的函数,随时间的推移而增值,其增值的这部分资金就是原有资金的时间价值【例【例3】任何一个大于任何一个大于1的自然数的自然数n,总可以拆分成若干个小于,总可以拆分成若干个小于n的自然数之和。的自然数之和。当
10、当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+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资金是运动的价值,资金的价值是随时间变化而变化的,是时间的函数,随时间的推移而增值,其增值的这部分资金就是原有资金的时间价值【参考程序】【参考程序】#include#include#includeusingnamespacestd;inta10001=1,n,total;intsearch(int,in
11、t);intprint(int);intmain()cinn;search(n,1);/将要拆分的数n传递给scouttotal=totalendl;/输出拆分的方案数system(pause);intsearch(ints,intt)inti;for(i=at-1;i=s;i+)if(i0时,继续递归s+=i;/回溯:加上拆分的数,以便产分所有可能的拆分intprint(intt)coutn=;for(inti=1;i=t-1;i+)/输出一种拆分方案coutai+;coutatendl;total+;/方案数累加1资金是运动的价值,资金的价值是随时间变化而变化的,是时间的函数,随时间的推移
12、而增值,其增值的这部分资金就是原有资金的时间价值【例例4】八皇后问题:要在国际象棋棋盘中放八个皇后,使任意两个皇后八皇后问题:要在国际象棋棋盘中放八个皇后,使任意两个皇后都不能互相吃。(提示:皇后能吃同一行、同一列、同一对角线的任意都不能互相吃。(提示:皇后能吃同一行、同一列、同一对角线的任意棋子。)棋子。)放置第个(行)皇后的算法为:intsearch(i);intj;for(第i个皇后的位置j=1;j=8;j+)/在本行的8列中去试if(本行本列允许放置皇后)放置第i个皇后;对放置皇后的位置进行标记;if(i=8)输出/已经放完个皇后elsesearch(i+1);/放置第i+1个皇后对放
13、置皇后的位置释放标记,尝试下一个位置是否可行;资金是运动的价值,资金的价值是随时间变化而变化的,是时间的函数,随时间的推移而增值,其增值的这部分资金就是原有资金的时间价值【算法分析】【算法分析】显然问题的关键在于如何判定某个皇后所在的行、列、斜线上是否有别的皇后;可以从矩阵的特点上找到规律,如果在同一行,则行号相同;如果在同一列上,则列号相同;如果同在斜线上的行列值之和相同;如果同在斜线上的行列值之差相同;从下图可验证:考虑每行有且仅有一个皇后,设一维数组1.8表示皇后的放置:第行皇后放在第列,用ij来表示,即下标是行数,内容是列数。例如:A3=5就表示第3个皇后在第3行第5列上。资金是运动的
14、价值,资金的价值是随时间变化而变化的,是时间的函数,随时间的推移而增值,其增值的这部分资金就是原有资金的时间价值判断皇后是否安全,即检查同一列、同一对角线是否已有皇后,建立标志数组1.8控制同一列只能有一个皇后,若两皇后在同一对角线上,则其行列坐标之和或行列坐标之差相等,故亦可建立标志数组1.16、-7.7控制同一对角线上只能有一个皇后。如果斜线不分方向,则同一斜线上两皇后的行号之差的绝对值与列号之差的绝对值相同。在这种方式下,要表示两个皇后I和J不在同一列或斜线上的条件可以描述为:AIAJANDABS(I-J)ABS(AI-AJ)I和J分别表示两个皇后的行号【参考程序】#include#in
15、clude#include#includeusingnamespacestd;boold100=0,b100=0,c100=0;intsum=0,a100;intsearch(int);intprint();intmain()search(1);/从第1个皇后开始放置system(pause);资金是运动的价值,资金的价值是随时间变化而变化的,是时间的函数,随时间的推移而增值,其增值的这部分资金就是原有资金的时间价值intsearch(inti)intj;for(j=1;j=8;j+)/每个皇后都有8位置(列)可以试放if(!bj)&(!ci+j)&(!di-j+7)/寻找放置皇后的位置/由于
16、C+不能操作负数组,因此考虑加7/放置皇后,建立相应标志值ai=j;/摆放皇后bj=1;/宣布占领第j列ci+j=1;/占领两个对角线di-j+7=1;if(i=8)print();/个皇后都放置好,输出elsesearch(i+1);/继续递归放置下一个皇后bj=0;/递归返回即为回溯一步,当前皇后退出ci+j=0;di-j+7=0;intprint()inti;sum+;/方案数累加1coutsum=sumendl;for(i=1;i=8;i+)/输出一种方案coutsetw(4)ai;cout2,1-3,3-1,4-3,5-2,7-4,8【算法分析】【算法分析】如图4(b),马最多有四个
17、方向,若原来的横坐标为j、纵坐标为i,则四个方向的移动可表示为:1:(i,j)(i+2,j+1);(i3,j8)2:(i,j)(i+1,j+2);(i4,j0,j1,j8)搜索策略:S1:=(0,0);S2:从1出发,按移动规则依次选定某个方向,如果达到的是(4,8)则转向S3,否则继续搜索下一个到达的顶点;S3:打印路径。资金是运动的价值,资金的价值是随时间变化而变化的,是时间的函数,随时间的推移而增值,其增值的这部分资金就是原有资金的时间价值【参考程序】【参考程序】#include#include#includeusingnamespacestd;inta100100,t=0;/路径总数和
18、路径intx4=2,1,-1,-2,/四种移动规则y4=1,2,2,1;intsearch(int);/搜索intprint(int);/打印intmain()/主程序a11=0;a12=0;/从坐标(0,0)开始往右跳第二步search(2);system(pause);资金是运动的价值,资金的价值是随时间变化而变化的,是时间的函数,随时间的推移而增值,其增值的这部分资金就是原有资金的时间价值intsearch(inti)for(intj=0;j=0&ai-11+xj=0&ai-12+yj=8)/判断马不越界ai1=ai-11+xj;/保存当前马的位置ai2=ai-12+yj;if(ai1=
19、4&ai2=8)print(i);elsesearch(i+1);/搜索下一步intprint(intii)t+;coutt:;for(inti=1;i=ii-1;i+)coutai1,ai2;cout4,8endl;资金是运动的价值,资金的价值是随时间变化而变化的,是时间的函数,随时间的推移而增值,其增值的这部分资金就是原有资金的时间价值【例例6】设有设有A,B,C,D,E五人从事五人从事J1,J2,J3,J4,J5五项工作,每五项工作,每人只能从事一项,他们的效益如下。人只能从事一项,他们的效益如下。每人选择五项工作中的一项,在各种选择的组合中,找到效益最高的的一种组合输出。【算法分析算法
20、分析】用数组储存工作选择的方案;数组存放最优的工作选择方案;数组用于表示某项工作有没有被选择了。(1)选择(i)=0的第i项工作;(2)判断效益是否高于max已记录的效益,若高于则更新数组及max的值。搜索策略:回溯法(深度优先搜索dfs)。资金是运动的价值,资金的价值是随时间变化而变化的,是时间的函数,随时间的推移而增值,其增值的这部分资金就是原有资金的时间价值【参考程序】【参考程序】#include#include#include#includeusing namespace std;int data66=0,0,0,0,0,0,0,13,11,10,4,7,0,13,10,10,8,5,
21、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 step,int t)/step是第几个人,是第几个人,t是之前已得的效益是之前已得的效益 for(int i=1;i=5;i+)if(!pi)/判断第判断第i项工作没人选择项工作没人选择 fstep=i;/第第step个人,就选第个人,就选第i项工作项工作 pi=1;/标记第标记第i项工作被人安排了项工作被人安排了 t+=datastepi;/计算效益值计算效益值 if(stepmax1)/保存最佳效益值保存最佳效益值 max1=
22、t;for(int j=1;j=5;j+)gj=fj;/保存最优效益下的工作选择方案保存最优效益下的工作选择方案 t-=datastepi;/回溯回溯 pi=0;资金是运动的价值,资金的价值是随时间变化而变化的,是时间的函数,随时间的推移而增值,其增值的这部分资金就是原有资金的时间价值int main()go(1,0);/从第从第1个人,总效益为个人,总效益为0开始开始 for(int i=1;i=5;i+)coutchar(64+i):Jgisetw(3);/输出各项工作安排情况输出各项工作安排情况 coutendl;coutsupply:max1endl;/输出最佳效益值输出最佳效益值资金
23、是运动的价值,资金的价值是随时间变化而变化的,是时间的函数,随时间的推移而增值,其增值的这部分资金就是原有资金的时间价值【例【例7】选书】选书学校放寒假时,信息学竞赛辅导老师有A,B,C,D,E五本书,要分给参加培训的张、王、刘、孙、李五位同学,每人只能选一本书。老师事先让每个人将自己喜欢的书填写在如下的表格中。然后根据他们填写的表来分配书本,希望设计一个程序帮助老师求出所有可能的分配方案,使每个学生都满意。【算法分析】【算法分析】可用穷举法,先不考虑“每人都满意”这一条件,这样只剩“每人选一本且只能选一本”这一条件。在这个条件下,可行解就是五本书的所有全排列,一共有5!=120种。然后在12
24、0种可行解中一一删去不符合“每人都满意”的解,留下的就是本题的解答。为了编程方便,设1,2,3,4,5分别表示这五本书。这五个数的一种全排列就是五本书的一种分发。例如54321就表示第5本书(即E)分给张,第4本书(即D)分给王,第1本书(即A)分给李。“喜爱书表”可以用二维数组来表示,1表示喜爱,0表示不喜爱。资金是运动的价值,资金的价值是随时间变化而变化的,是时间的函数,随时间的推移而增值,其增值的这部分资金就是原有资金的时间价值算法设计:S1:产生5个数字的一个全排列;S2:检查是否符合“喜爱书表”的条件,如果符合就打印出来;S3:检查是否所有的排列都产生了,如果没有产生完,则返回S1;
25、S4:结束。intSearch(i)for(j=1;j=5;j+)if(第i个同学分给第j本书符合条件)记录第i个数if(i=5)打印一个解;elseSearch(i+1);删去第i个数上述算法有可以改进的地方。比如产生了一个全排列12345,从表中可以看出,选第一本书即给张同学的书,1是不可能的,因为张只喜欢第3、4本书。这就是说,1一类的分法都不符合条件。由此想到,如果选定第一本书后,就立即检查一下是否符合条件,发现1是不符合的,后面的四个数字就不必选了,这样就减少了运算量。换句话说,第一个数字只在3、4中选择,这样就可以减少3/5的运算量。同理,选定了第一个数字后,也不应该把其他4个数字
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 搜索 回溯 算法 ppt 课件
限制150内