Betsy解题报告.doc

Betsy解题报告试题一个正方形的小镇被分成N2个小方格，Betsy要从左上角的方格到达左下角的方格，并且经过每个方格恰好一次。编程对于给定的N，计算出Betsy能采用的所有的旅行路线的数目思路这道题目很明显是道搜索题，关键在于优化。而搜索题的优化主要就是剪枝。首先很容易想到，因为Betsy是任意的走，当取到或时，它的方案总数就已经很大了，方案数越是大，搜索时，不要用的枝就会越多，而且这些枝占方案总数的比例相当大。如果能知道什么情况下，会出现必然无解，就能很好的提高效率了。于是由此知道，此题用剪枝的方法做是正确的。具体解法首先从题目的条件入手，题目要求每一个各自都必须走到，而且每一个格子只能走一遍。这两个条件就指出了这道题目的可剪的枝条中的两个。然后从这两条出发，仔细分析一下，到底在什么情况下会不满足题目的要求。第二个条件要求每个格子只能走一遍，这很简单，用一个数组记录一下到底有哪些格子是已经经过了的，那些是还没有经过的，在Betsy移动时，就只移动到那些还没有经过的格子中去，这样就避免了一个格子走两遍。第一个条件要求每个格子都要经过一次，这是个很难满足的条件，有很多无解的情况就是因为不满足它，那到底有哪些情况会导致不满足着一个条件呢。比方说下面的几个图。图中箭头表示Betsy的行走路线。如图，其中的黄色区是不能达到的，如果到达了黄色区，就别再想到最左下角了，因为，这个区域只有一个入口，没有出口，进得去，出不来。于是，就一般的情况来说，每一个还没有到过得格子（除开终点）都必须要有两个空格子与之相连接（Betsy当前所在的格子算是个空格子），这样才能保证Betsy既可以移进这个格子又可以移出这个格子。图再如图，其中的红色格子是不可能达到了，虽然它满足每一个格子都有两个相邻的空格子，但是，Betsy是不可能移动到这些红格子中去了，这几个格子被隔断了。一般化，Betsy行走的路径不能够圈出一个独立的块出来，否则这一块是没有办法走到的。 图图中的独立的一块要如何判断，难道要进行一次搜索求得？不。看一下的几种情况，仅当出现这几种情况时，会分割出一个独立的块。图中绿色格子表示Betsy现在所在的格子，黑色格子表示Betsy已经走过的格子，空格子是没有经过的格子。仅当Betsy沿箭头方向移动时会分割出两块相对独立的块，Betsy只能到达其中的一块，而另一块是不可能到达的，于是这种情况不满足条件二，应当予以排除。当然，还有一种情况，如果想到了，程序速度可以加快很多，就是，最左下角的格子必须是最后走，如果还没把所有的格子都走到就到了终点是不合要求的。有了这三条剪枝，速度就可以猛增了。下面进行一下对比。数据n答案没有用任何剪枝的程序耗时用了三种剪枝的程序耗时110 s0 s210 s0 s320 s0 s480 s0 s5480 s0 s61770372 s0 s78841830 min083 s其实这个题目还有其它的剪枝，但是对于这些数据，不能取得很明显的效果，就不与介绍，但是如果要计算更大的数据，还是有枝可剪的。程序$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q-,R-,S-,T-,V+,X+,Y+$M 16384,0,655360const ai : array 1.4 of -1.1 = (-1,0,1,0); aj : array 1.4 of -1.1 = (0,1,0,-1); bi : array 1.4,-1.1 of -1.1 = (-1,-1,-1),(-1,0,1),(1,1,1),(1,0,-1); bj : array 1.4,-1.1 of -1.1 = (-1,0,1),(1,1,1),(1,0,-1),(-1,-1,-1); n = 7;数据输入type type_tag = array 0.n+1,0.n+1 of boolean; type_many = array 0.n+1,0.n+1 of byte;var tag : type_tag; tagx,y为真表示(x,y)这个格子已经走过了 many : type_many; manyx,y表示(x,y)这个格子与多少个空格子相邻 result : longint;结果 n2 : integer;n的平方 procedure search(deep,x,y : integer); 搜索过程，Betsy通过deep次移动到了格子(x,y)，并开始搜索下一步 var j,k,dir,all,u : integer; go : boolean; begin if (x=n) and (y=1) then if deep=n2 then begin inc(result); exit;end else exit;第三条剪枝 tagx,y:=true; 准备图1的剪枝 all:=0; u:=0; for dir:=1 to 4 do begin j:=x+aidir; k:=y+ajdir; if not tagj,k then begin dec(manyj,k); if manyj,k=1 then begin u:=dir; inc(all); end; end; end;图1的剪枝完成 case all of 1 : search(deep+1,x+aiu,y+aju); 0 : for dir:=1 to 4 do begin j:=x+aidir; k:=y+ajdir; if not tagj,k then begin 准备图2的剪枝 if tagj+bidir,0,k+bjdir,0 and not tagx+bidir,-1,y+bjdir,-1 and not tagx+bidir,1,y+bjdir,1 then continue else if not tagj+bidir,0,k+bjdir,0 then if tagj+bidir,-1,k+bjdir,-1 and not tagx+bidir,-1,y+bjdir,-1 then continue else if tagj+bidir,1,k+bjdir,1 and not tagx+bidir,1,y+bjdir,1 then continue; 图2的剪枝完成 search(deep+1,j,k); end end; end; tagx,y:=false; for dir:=1 to 4 do begin j:=x+aidir; k:=y+ajdir; if not tagj,k then inc(manyj,k); end; end; procedure ready; var i : integer; begin n2:=n*n; fillchar(tag,sizeof(tag),0); fillchar(many,sizeof(many),4); for i:=1 to n do begin many1,i:=3; manyn,i:=3; manyi,1:=3; manyi,n:=3;end; many1,1:=2; many1,n:=2; manyn,1:=4;特别值得注意不能赋2 manyn,n:=2; for i:=0 to n+1 do begin many0,i:=0; manyi,0:=0; manyn+1,i:=0; manyi,n+1:=0; tag0,i:=true