周娟回朔(dog、装载、n后)

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第五章 回朔法,软件理论教研室 周娟,1.,搜索问题,这类问题的解，就是一个合法状态的序列，其中序列中第一个状态是问题的初始状态，而最后一个状态则是问题的结束状态。如图所示即搜索问题的示意图：,S,g,S,0,解路径,搜索空间,全状态空间,2.,搜索方法分类,不可撤回方法,试探性方法,回溯方法,图搜索方法,3.,回溯法,回溯方法，属于盲目搜索的一种，它是这样一种策略：首先将规则给出一个固定的排序，在搜索时，对当前状态依次检测每一条规则，在当前状态未使用过的规则中找到第一条可应用规则，应用于当前状态，得到的新状态重新设置为当前状态，并重复以上搜索。如果当前状态无规则可用，或者所有规则已经被试探过仍未找到问题的解，则将当前状态的前一个状态（即直接生成该状态的状态）设置为当前状态。重复以上搜索，直到找到问题的解，或已试探过所有可能仍找不到问题的解为止。,问题的解空间,问题的解向量：回溯法希望一个问题的解能够表示成一个,n,元式,(x1,x2,xn,),的形式。,显约束：对分量,xi,的取值限定。,隐约束：为满足问题的解而对不同分量之间施加的约束。,解空间：对于问题的一个实例，解向量满足显式约束条件的所有多元组，构成了该实例的一个解空间。,n=3,时的,0-1,背包问题用完全二叉树表示的解空间,0-1,背包问题，其解空间由长度为,n,的,0-1,向量组成。,（,0,0,0,），（,0,1,0,），（,1,0,0,），,(1,0,1),，,(1,1,0),，,(1,1,1),剪枝,Tempter of the Bone,装载问题,N,后问题,Problem Description,The doggie found a bone in an ancient maze,which fascinated him a lot.However,when he picked it up,the maze began to shake,and the doggie could feel the ground sinking.He realized that the bone was a trap,and he tried desperately to get out of this maze.The maze was a rectangle with sizes N by M.There was a door in the maze.At the beginning,the door was closed and it would open at the T-,th,second for a short period of time(less than 1 second).Therefore the doggie had to arrive at the door on exactly the T-,th,second.In every second,he could move one block to one of the upper,lower,left and right neighboring blocks.Once he entered a block,the ground of this block would start to sink and disappear in the next second.He could not stay at one block for more than one second,nor could he move into a visited block.Can the poor doggie survive?Please help him.,Tempter of the Bone,Input,The input consists of multiple test cases.The first line of each test case contains three integers N,M,and T(1 N,M 7;0 T 1,或,1-0,必然是奇数步,0-0,走,1-1,必然是偶数步,所以当遇到从,0,走向,0,但是要求时间是奇数的，或者，从,1,走向,0,但是要求时间是偶数的 都可以直接判断不可达！,结论：,#include,#include#include,char map99;,int n,m,t,di,dj;,bool escape;,int dir42=0,-1,0,1,1,0,-1,0;,void dfs(int si,int sj,int cnt),int,i,temp;,if(si,n|sj,m|si,=0|sj=0)return;,if(cnt=t&si=di&sj=dj),escape=1;,if(escape)return;,temp=(,t-cnt)-abs(si-di)-abs(sj-dj,);,if(temp0|temp,for(i=0;inmt),if(n=0&m=0&t=0),break;,int,wall=0;,for(i=1;i=n;i+),for(j=1;jmapij;,if(mapij=S),si,=i;,sj,=j;,else if(mapij=D),di,=i;,dj,=j;,else if(mapij=X),wall+;,if(n*m-wall=t),cout,NO,endl,;,continue;,escape=0;,mapsisj=X;,dfs(si,sj,0);,if(escape)cout,YES,endl,;,else,cout,NO n)/,到达叶结点,if(cw,bestw)bestw,=,cw;return,;,/,搜索子树,if,(,cw,+,wi,n)/,到达叶结点,if(cw,bestw)bestw,=,cw;return,;,/,搜索子树,if,(,cw,+,wi,n)/,到达叶结点,if(cw,bestw)bestw,=,cw;return,;,/,搜索子树,if,(,cw,+,wi,n)/,到达叶结点,if(cw,bestw)bestw,=,cw;return,;,/,搜索子树,if,(,cw,+,wi,n)/,到达叶结点,if(cw,bestw)bestw,=,cw;return,;,/,搜索子树,if,(,cw,+,wi,n)/,到达叶结点,if(cw,bestw)bestw,=,cw;return,;,/,搜索子树,if,(,cw,+,wi,n)/,到达叶结点,更新最优解,bestx,bestw,;return;,r-=wi;,if,(,cw,+wi,bestw,),xi=0;/,搜索右子树,backtrack,(i+1);,r+=wi;,当,cw+r,bestw)bestw,=,cw,;,for(j,=1;j=,n;j+)bestxj,=,xj,;,4.3,最优装载,有一批集装箱要装上一艘载重量为,c,的轮船。其中集装箱,i,的重量为,Wi,。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。,1.,算法描述,最优装载问题可用贪心算法求解。采用重量最轻者先装的贪心选择策略，可产生最优装载问题的最优解。,尽可能多的个数,p107,5.2,装载问题,有一批共,n,个集装箱要装上,2,艘载重量分别为,c1,和,c2,的轮船，其中集装箱,i,的重量为,wi,，且,装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这,2,艘轮船。如果有，找出一种装载方案。,容易证明，如果一个给定装载问题有解，则采用下面的策略可得到最优装载方案。,(1),首先将第一艘轮船尽可能装满；,(2),将剩余的集装箱装上第二艘轮船。,将第一艘轮船尽可能装满等价于选取全体集装箱的一个子集，使该子集中集装箱重量之和最接近。由此可知，装载问题等价于以下特殊的,0-1,背包问题。,尽可能多的重量,p143,4.3,最优装载,public static float,loading,(float c,float w,int,x),int,n=w.length;,Element d=new Element n;,for(,int,i=0;i n;i+),di=new Element(wi,i);,MergeSort.mergeSort(d,);,float opt=0;,for(,int,i=0;i n;i+)xi=0;,for(,int,i=0;i n i+),xdi.i=1;,opt+=di.w;,c-=di.w;,return opt;,最轻者先装的贪心选择策略，产生最优装载问题的最优解,p108,n,后问题,在,nn,格的棋盘上放置彼此不受攻击的,n,个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。,n,后问题等价于在,nn,格的棋盘上放置,n,个皇后，任何,2,个皇后不放在同一行或同一列或同一斜线上。,1 2 3 4 5 6 7 8,1,2,3,4,5,6,7,8,Q,Q,Q,Q,Q,Q,Q,Q,以,n=4,为例,假定第一行的棋子在,h,列，第二、三、四行的棋子在,i,j,k,列，所以一个布局可用,hijk,来表示。,Hijk,等价于,1,，,2,，,3,，,4,的某一个排列。,总状态数（排列数）是？,4,！,=24,，它们是：,1234 1243 1324 1342 1423 1432,2134 2143 2314 2341 2413 2431,3124 3142 3214 3241 3412 3421,4123 4132 4213 4231 4312 4321,Q,Q,Q,Q,3142,n,后问题,Q,Q,Q,Q,N,后问题,N,后问题,(),(),(),(),(1,1),Q,N,后问题,(),(),(1,1),(1,1)(2,3),Q,Q,N,后问题,(),(),(1,1),(1,1)(2,3),Q,N,后问题,(),(),(1,1),(1,1)(2,3),(1,1)(2,4),Q,Q,N,后问题,(),(),(1,1),(1,1)(2,3),(1,1)(2,4),(1,1)(2,4)(3.2),Q,Q,Q,N,后问题,(),(),(1,1),(1,1)(2,3),(1,1)(2,4),(1,1)(2,4)(3.2),Q,Q,N,后问题,(),(),(1,1),(1,1)(2,3),(1,1)(2,4),(1,1)(2,4)(3.2),Q,N,后问题,(),(),(1,1),(1,1)(2,3),(1,1)(2,4),(1,1)(2,4)(3.2),N,后问题,(),(),(1,1),(1,1)(2,3),(1,1)(2,4),(1,1)(2,4)(3.2),(1,2),Q,N,后问题,(),(),(1,1),(1,1)(2,3),(1,1)(2,4),(1,1)(2,4)(3.2),(1,2),(1,2)(2,4),Q,Q,N,后问题,(),(),(1,1),(1,1)(2,3),(1,1)(2,4),(1,1)(2,4)(3.2),(1,2),(1,2)(2,4),(1,2)(2,4)(3,1),Q,Q,Q,N,后问题,(),(),(1,1),(1,1)(2,3),(1,1)(2,4),(1,1)(2,4)(3.2),(1,2),(1,2)(2,4),(1,2)(2,4)(3,1),(1,2)(2,4)(3,1)(4,3),Q,Q,Q,Q,N,后问题,解向量：,(x,1,x,2,x,n,),显约束：,x,i,=1,2,n,隐约束：,1),不同列：,x,i,x,j,2),不处于同一正、反对角线：,|,i-j|,|x,i,-x,j,|,n,后问题,private static,boolean,place,(,int,k),for,(,int,j=1;jn)sum+;,else,