资源描述：
《Betsy解题报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、Betsy解题报告试题一个正方形的小镇被分成N2个小方格，Betsy要从左上角的方格到达左下角的方格，并且经过每个方格恰好一次。编程对于给定的N，计算出Betsy能采用的所有的旅行路线的数目思路 这道题目很明显是道搜索题，关键在于优化。而搜索题的优化主要就是剪枝。首先很容易想到，因为Betsy是任意的走，当ｎ取到５或６时，它的方案总数就已经很大了，方案数越是大，搜索时，不要用的枝就会越多，而且这些枝占方案总数的比例相当大。如果能知道什么情况下，会出现必然无解，就能很好的提高效率了。于是由此知道，此题用剪枝的方法做是正确的。具体解法首先从题目的条件入手，题目要求每一个各
2、自都必须走到，而且每一个格子只能走一遍。这两个条件就指出了这道题目的可剪的枝条中的两个。然后从这两条出发，仔细分析一下，到底在什么情况下会不满足题目的要求。第二个条件要求每个格子只能走一遍，这很简单，用一个数组记录一下到底有哪些格子是已经经过了的，那些是还没有经过的，在Betsy移动时，就只移动到那些还没有经过的格子中去，这样就避免了一个格子走两遍。第一个条件要求每个格子都要经过一次，这是个很难满足的条件，有很多无解的情况就是因为不满足它，那到底有哪些情况会导致不满足着一个条件呢。比方说下面的几个图。图中箭头表示Betsy的行走路线。如图１，其中的黄色区是不能达到的，如
3、果到达了黄色区，就别再想到最左下角了，因为，这个区域只有一个入口，没有出口，进得去，出不来。于是，就一般的情况来说，每一个还没有到过得格子（除开终点）都必须要有两个空格子与之相连接（Betsy当前所在的格子算是个空格子），这样才能保证Betsy既可以移进这个格子又可以移出这个格子。 图１ 再如图２，其中的红色格子是不可能达到了，虽然它满足每一个格子都有两个相邻的空格子，但是，Betsy是不可能移动到这些红格子中去了，这几个格子被隔断了。一般化，Betsy行走的路径不能够圈出一个独立的块出来，否则这一块是没有办法走到的。 图２图２中的独立的一块
4、要如何判断，难道要进行一次搜索求得？不。看一下的几种情况，仅当出现这几种情况时，会分割出一个独立的块。图中绿色格子表示Betsy现在所在的格子，黑色格子表示Betsy已经走过的格子，空格子是没有经过的格子。仅当Betsy沿箭头方向移动时会分割出两块相对独立的块，Betsy只能到达其中的一块，而另一块是不可能到达的，于是这种情况不满足条件二，应当予以排除。当然，还有一种情况，如果想到了，程序速度可以加快很多，就是，最左下角的格子必须是最后走，如果还没把所有的格子都走到就到了终点是不合要求的。有了这三条剪枝，速度就可以猛增了。下面进行一下对比。数据n答案没有用任何剪枝的程序
5、耗时用了三种剪枝的程序耗时110s0s210s0s320s0s480s0s5480s0s617703．72s0s788418〉30min0．83s其实这个题目还有其它的剪枝，但是对于这些数据，不能取得很明显的效果，就不与介绍，但是如果要计算更大的数据，还是有枝可剪的。程序{$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q-,R-,S-,T-,V+,X+,Y+}{$M16384,0,655360}constai:array[1..4]of-1..1=(-1,0,1,0);aj:array[1..4]of-1..1=(0,1,0,-1);bi:arra
6、y[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;{数据输入}typetype_tag=array[0..n+1,0..n+1]ofboolean;type_many=array[0..n+1,0..n+1]ofbyte;vartag:type_tag;{tag[x,y]为真表示(x,y)这个格子已经走过了}many:type_many;{many[x,y]表示
7、(x,y)这个格子与多少个空格子相邻}result:longint;{结果}n2:integer;{n的平方}proceduresearch(deep,x,y:integer);{搜索过程，Betsy通过deep次移动到了格子(x,y)，并开始搜索下一步}varj,k,dir,all,u:integer;go:boolean;beginif(x=n)and(y=1)thenifdeep=n2thenbegininc(result);exit;endelseexit;{第三条剪枝}tag[x,y]:=true;{准备图1的剪枝}all:=0
