深优先搜索与回溯算法

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,深度优先搜索与回溯算法,回溯是计算机解题中常用的算法，很多问题无法根据某种确定的计算法则来求解，可以利用搜索与回溯的技术求解。回溯是搜索算法中的一种控制策略。它的基本思想是：为了求得问题的解，先选择某一种可能情况向前探索，在探索过程中，一旦发现原来的选择是错误的，就退回一步重新选择，继续向前探索，如此反复进行，直至得到解或证明无解。,如迷宫问题：进入迷宫后，先随意选择一个前进方向，一步步向前试探前进,如果碰到死胡同，说明前进方向已无路可走，这时，首先看其它方向是否还有路可走，如果有路可走，则沿该方向再向前试探；如果已无路可走，则返回一步，再看其它方向是否还有路可走；如果有路可走，则沿该方向再向前试探。按此原则不断搜索回溯再搜索，直到找到新的出路或从原路返回入口处无解为止。,回溯法算法框架,Procedure dfs(s)/,访问状态,s,Begin,if,边界,then begin,判断是否为目标状态；,exit;,end;,for i,：,=,状态变换规则数,begin,si=s+,规则,I,保存局面,dfs,（,si,）,还原局面,end,；,End;,【例,1,】,设有n个整数的集合1,2,n，从中取出任意r个数（rn），试列出所有的可能的情况。,例如,1,2,3,，,r=2,。那么有,3,种可能，（,1,2,），（,1,3,），（,2,3,）,【,例,2,】,任何一个大于,1,的自然数,n,，总可以拆分成若干个小于,n,的自然数之和。,当,n=7,共,14,种拆分方法：,7=1+1+1+1+1+1+1,7=1+1+1+1+1+2,7=1+1+1+1+3,7=1+1+1+2+2,7=1+1+1+4,7=1+1+2+3,7=1+1+5,7=1+2+2+2,7=1+2+4,7=1+3+3,7=1+6,7=2+2+3,7=2+5,7=3+4,total=14,【,例,3】,素数环,:,从,1,到,n,（,2,1-3,3-1,4-3,5-2,7-4,8,【,例,6】,数的划分,(NOIP2001),【,问题描述,】,将整数,n,分成,k,份，且每份不能为空，任意两种分法不能相同,(,不考虑顺序,),。例如,:n=7,k=3,下面三种分法被认为是相同的。,1,，,1,，,5,；,1,，,5,，,1,；,5,，,1,，,1,；,问有多少种不同的分法。,【,输入格式,】,n,k (6n200,，,2k6),【,输出格式,】,一个整数，即不同的分法。,【,输入样例,】,7 3,【,输出样例,】,4,4,种分法为：,1,1,5,；,1,2,4,；,1,3,3;2,2,3,说明部分不必输出,【例,7,】,跳马问题。,在5*5格的棋盘上，有一只中国象棋的马,，从（,1,1）点出发，按日字跳马，它可以朝8个方向跳，但,不允许出界或跳到已跳过的格子,上，要求在跳遍整个棋盘。,输出前5个方案及总方案数。,输出格式示例：,1 16 21 10 25,20 11 24 15 22,17 2 19 6 9,12 7 4 23 14,3 18 13 8 5,【,课堂练习,】,1,、输出自然数,1,到,n,所有不重复的排列，即,n,的全排列。,【,参考过程,】,int Search(int i),Int j;,for(j=1;j=n;j+),if(bj),ai=j;bj=false;,if(In)Search(i+1);,else print();,bj=true;,2,、找出,n,个自然数,(1,2,3,n),中,r,个数的组合。例如，当,n=,r=3,时，所有组合为：,1 2 3,1 2 4,1 2 5,1 3 4,1 3 5,1 4 5,2 3 4,2 3 5,2 4 5,3 4 5,total=10 /,组合的总数,【,分析,】,：,设在,b1,b2,bi-1,中已固定地取了某一组值且,bi-1=k,的前提下，过程,Search(i,k),能够列出所有可能的组合。由于此时,bi,只能取,k+1,至,n-r+i,，对,j=k+1,k+2,n-r+i,，使,bi:=j,，再调用过程,Search(i+1,j),，形成递归调用。直至,i,的值大于,r,时，就可以在,b,中构成一种组合并输出。,3,、输出字母,a,、,b,、,c,、,d,，,4,个元素全排列的每一种排列。,4,、显示从前,m,个大写英文字母中取,n,个不同字母的所有种排列。,5,、有,A,、,B,、,C,、,D,、,E,五本书，要分给张、王、刘、赵、钱五位同学，每人只能选一本，事先让每人把自已喜爱的书填于下表，编程找出让每人都满意的所有方案。,【答案】四种方案,张 王 刘 赵 钱,C A B D E,D A C B E,D B C A E,D E C A B,6,、有红球,4,个，白球,3,个，黄球,3,个，将它们排成一排共有多少种排法？,【,分析,】,：,可以用回溯法来生成所有的排法。用数组,b1.3,表示尚未排列的这,3,种颜色球的个数。设共有,I-1,个球已参加排列，用子程序,Search(i),生成由第,I,个位置开始的以后,n-I+1,位置上的各种排列。对于第,I,个位置，我们对,3,种颜色的球逐一试探，看每种颜色是否还有未加入排序的球。若有，则选取一个放在第,I,个位置上，且将这种球所剩的个数减,1,，然后调用,Search(I+1),直至形成一种排列后出。对第,I,个位置上的所有颜色全部试探完后，则回溯至前一位置。,【,上机练习,】,1、全排列问题(Form.cpp),【问题描述】,输出自然数1到n所有不重复的排列，即n的全排列，要求所产生的任一数字序列中不允许出现重复的数字。,【输入格式】,n(1n9),【输出格式】,由1n组成的所有不重复的数字序列，每行一个序列。,【输入样例】Form.in,3,【输出样例】Form.out,1 2 3,1 3 2,2 1 3,2 3 1,3 1 2,3 2 1,2、组合的输出(Compages.cpp),【问题描述】,排列与组合是常用的数学方法，其中组合就是从n个元素中抽出r个元素(不分顺序且rn)，我们可以简单地将n个元素理解为自然数1，2，n，从中任取r个数。,现要求你用递归的方法输出所有组合。,例如n5，r3，所有组合为：,l 2 3 l 2 4 1 2 5 l 3 4 l 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5,【输入】,一行两个自然数n、r(1n21，1rn)。,【输出】,所有的组合，每一个组合占一行且其中的元素按由小到大的顺序排列，每个元素占三个字符的位置，所有的组合也按字典顺序。,【样例】,compages.in compages.out,5 3 1 2 3,1 2 4,1 2 5,1 3 4,1 3 5,1 4 5,2 3 4,2 3 5,2 4 5,3 4 5,3,、N皇后问题(Queen.cpp),【问题描述】,在N*N的棋盘上放置N个皇后（n=10）而彼此不受攻击（即在棋盘的任一行，任一列和任一对角线上不能放置2个皇后），编程求解所有的摆放方法。,八皇后的两组解,【,输入格式,】,输入：,n,【,输出格式,】,每行输出一种方案，每种方案顺序输出皇后所在的列号，各个数之间有空格隔开。若无方案，则输出,no solute!,【,输入样例,】Queen.in,4,【,输出样例,】Queen.out,2 4 1 3,3 1 4 2,4,、有重复元素的排列问题,【,问题描述,】,设,R=r1,r2,rn,是要进行排列的,n,个元素。其中元素,r1,r2,rn,可能相同。试设计一个算法，列出,R,的所有不同排列。,【,编程任务,】,给定,n,以及待排列的,n,个元素。计算出这,n,个元素的所有不同排列。,【,输入格式,】,由,perm.in,输入数据。文件的第,1,行是元素个数,n,，,1n500,。接下来的,1,行是待排列的,n,个元素。,【,输出格式,】,计算出的,n,个元素的所有不同排列输出到文件,perm.out,中。文件最后,1,行中的数是排列总数。,【,输入样例,】,4,aacc,【,输出样例,】,多解,aacc,acac,acca,caac,caca,ccaa,6,5,、子集和问题,【,问题描述,】,子集和问题的一个实例为,S,t,。其中，,S=x1,，,x2,，,，,xn,是一个正整数的集合，,c,是一个正整数。子集和问题判定是否存在,S,的一个子集,S1,，使得子集,S1,和等于,c,。,【,编程任务,】,对于给定的正整数的集合,S=x1,，,x2,，,，,xn,和正整数,c,，编程计算,S,的一个子集,S1,，使得子集,S1,和等于,c,。,【,输入格式,】,由文件,subsum.in,提供输入数据。文件第,1,行有,2,个正整数,n,和,c,，,n,表示,S,的个数，,c,是子集和的目标值。接下来的,1,行中，有,n,个正整数，表示集合,S,中的元素。,【,输出格式,】,程序运行结束时，将子集和问题的解输出到文件,subsum.out,中。当问题无解时，输出“,No solution!”,。,【,输入样例,】,5 10,2 2 6 5 4,【,输出样例,】,2 2 6,6,、工作分配问题,【,问题描述,】,设有,n,件工作分配给,n,个人。将工作,i,分配给第,j,个人所需的费用为,cij,。试设计一个算法，为每一个人都分配一件不同的工作，并使总费用达到最小。,【,编程任务,】,设计一个算法，对于给定的工作费用，计算最佳工作分配方案，使总费用达到最小。,【,输入格式,】,由文件,job.in,给出输入数据。第一行有,1,个正整数,n(1n20),。接下来的,n,行，每行,n,个数，第,i,行表示第,i,个人各项工作费用。,【,输出格式,】,将计算出的最小总费用输出到文件,job.out,。,【,输入样例,】,3,4 2 5,2 3 6,3 4 5,【,输出样例,】,9,7,、装载问题,【,问题描述,】,有一批共,n,个集装箱要装上艘载重量为,c,的轮船，其中集装箱,i,的重量为,wi,。找出一种最优装载方案，将轮船尽可能装满，即在装载体积不受限制的情况下，将尽可能重的集装箱装上轮船。,【,输入格式,】,由文件,load.in,给出输入数据。第一行有,2,个正整数,n,和,c,。,n,是集装箱数，,c,是轮船的载重量。接下来的,1,行中有,n,个正整数，表示集装箱的重量。,【,输出格式,】,将计算出的最大装载重量输出到文件,load.out,。,【,输入样例,】,5 10,7 2 6 5 4,【,输出样例,】,10,8、字符序列(characts),【问题描述】,从三个元素的集合A，B，C中选取元素生成一个N个字符组成的序列，使得没有两个相邻字的子序列（子序列长度=2）相同。例：N=5时ABCBA是合格的，而序列ABCBC与ABABC是不合格的，因为其中子序列BC，AB是相同的。,对于由键盘输入的N(1=N=12)，求出满足条件的N个字符的所有序列和其总数。,【输入样例】,4,【输出样例】,72,9,、试卷批分,(grade),【,问题描述,】,某学校进行了一次英语考试，共有,10,道是非题，每题为,10,分，解答用,1,表示“是”，用,0,表示“非”的方式。但老师批完卷后，发现漏批了一张试卷，而且标准答案也丢失了，手头只剩下了,3,张标有分数的试卷。,试卷一：,0 0 1 0 1 0 0 1 0 0,得分：,70,试卷二：,0 1 1 1 0 1 0 1 1 1,得分：,50,试卷三：,0 1 1 1 0 0 0 1 0 1,得分：,30,待批试卷：,0 0 1 1 1 0 0 1 1 1,得分：？,【,问题求解,】,：,请编一程序依据这三张试卷，算出漏批的那张试卷的分数。,10,、迷宫问题,(migong),【,问题描述,】,设有一个,N*N(2=N10),方格的迷宫，入口