实验7 蛇和梯子问题的算法设计与实现

1、实验7蛇和梯子问题的算法设计与实现一、实验目的1、掌握深度优先和广度优先搜索算法的基本思想和设计方法；2、理解贪心算法的局限性；3、提高分析与解决问题的能力。二、实验内容【实验题】“蛇和梯子”是一个在NXN （0N=20）的方格棋盘上进行的游戏。（见下图）方格从1到N的平方编号。除了第1号和最后编号的方格，其它的格子都有可能有蛇或梯子 存在（蛇和梯子的数量及具体位置由输入确定，它们的数量都在100之内并且蛇和梯子不能 临近放置,也就是在任何了放置两者首尾的方格之间至少还有一个未放置任何东西的格子）。 开始的时候玩家把他们的标志物放在1号格子中。玩家轮流以扔骰子的方式移动他们的指示 物。如果一个

2、指示物到达了一条蛇的嘴部，则把它移回蛇的尾部。如果一个指示物到达了一 个梯子的底部则将它移动到梯子的顶部。如果你是一个可以自由控制骰子的高手，现在请求 出你至少需要扔几次骰子才能到这标为22的格子。（比如在上图所示例一中，你的方案应 该是走4步到达5并由梯子上升到16,再走4步到达20并由梯子上升到33,然后走3步。 这样，你一共需要扔3次骰子。而在例二中，你的方案应该是连扔4个6。）三、算法的原理方法从上面的实验题中很容易看出，这个问题是不能用贪心算法解决的，因为你不能保证 在这步到达一个数码比较大的格子就意味着最好的效率（即使是通过梯子到这了一个这步所 能到这的最大号码的格子），也就是说，

3、号码的大小并不能代表从这个格子到达终点所需要 的步数上的多少，这就带给我们一个启发：蛇和梯子真的需要看成是两个东西来分别处理 么？实际上确实是不需要的，蛇和梯子的本质就是我们经常在游戏中说的“单向传送点”， 只不过梯子的底部是入I I而顶部是出I I,蛇的嘴部是入I I而尾部是出I I罢了，对于他们的描 述完全可以选择相同的结构： struct SnakeAndLadderint from, to;；接下来要考虑的是解决问题的方法。贪心算法被否定之后，我们的选择可能会是搜索， 对于本题所采用的搜索显然应该以广度优先的方式进行，但是稍加分析我们就会发现如果单 纯地采用广度优先搜索会产生许多重复的

4、结点，现在我们将指示物处于某格的结点简称为结 点X,那么比如在例1中，第1步过后，队列中存放的结点是2, 23, 4, 16, 6, 7,在第二 步时，当结点2成为扩展结点时将生成结点23、4、16、6、7、8,其中只有8不存在于当 前活结点队列中，即使加以判断，不把重复的结点再次加入队列中，那至少也需要对活结点 队列进行搜索。实际上我们完全有更好的方法。应该意识到，采用树状结构和搜索的方法处理问题其重要的一点是利用祖先结点的差异 性来对儿子结点做不同的处理。然而在本实验中，儿子结点的生成只依赖于父结点的信息而 与其它祖先结点无关，所以采用树来描述这个过程其实是多余的。在走了若干步之后，对于

5、一个特定的格子实际上只有两种状态的区分：1、在走了这些步数之后存在一种方案使指示物位于此格中；2、不存在这样的一种方案。所以我们可以用一个NXN大小的数组来描述若干步之后可以到达的格子的集合，其中 每一个元素描述一个格子的状态，0表示不存在一种方案到达，1表示存在至少一种方案到 达。这样，我们从表示第n步状态的数组，完全可以推出表示第n+1步状态的数组，而旦在 第n+1步状态的数组得到之后，表示第n步状态的数组也就不再存在利用价值了。一旦数组 中表示最后一个格子的元素成为1,就表示可以通过这个步数完成任务了。比如在例1中，描述棋盘状态的数组其变化过程应该为:描述状态数组元素的内容（从表示第1个

6、格的元素排列到表示最后一个格的元素）起始状态100000000000000000000000000000000000第1步之后010101100000000100000010000000000000第2步之后000101111111100111101111111110001000第3步之后000001111111111111101111111111111101到第3步之后，数组的最后一个元素己经变为了 1,这即表明存在一种方案，使得我们扔3次骰子就可以完成任务。以下是实现此算法的主要部分代码，数组下.标0一 size*size-l的元素分别表示了从第1格到最后一格的状态，step记录步数，ob

7、stacle是 struct SnakeAndLadder的向量，描述了蛇和梯子的传送入I I和出I I:四、实验程序的功能模块typedef stmct snakeladder; /蛇与梯子的结构void Slove();广度优先遍历搜索最少步数五、详细代码#iiicludeusing namespace std;typedef stmct snakeladderint from;int to; snakeladder; /定义蛇与梯子的类型hit n,step,obNum;int grid1001;snakeladder obstacle1001;void Slove()int l,j,k

8、,test;int giidbak1001;for(j=2jn*nj-H-)gridj=O;gnd0=l;step=O;while(grid n*n-l =0)for(j=ljvn*n;j+)/而且在第n+1步状态的数组得到之后，表示第n步状态的数组 也就不再存在利用价值了(giidbakj=gridlj;coutgridbakj;)coutendl;Rr(J=Ojvn*n;j+)gridj=O;for(j=0jvn*n-lj+) 搜索所有的格子(最后一格不用搜索因为在过程结束前它一 定为0)(if(gndbakj=O) /若在上一步无法到达此格则跳出continue;for(k=l ;kn*

9、n-l)break:for(l=0;lobNum;l-H-) 如果此格是一个传送入I I,将传送出I I的格子可达 if(o bstacle 1. fiom=j +k)gridobstaclel.to=l;test=l;break:1Jif(test=O & gridj+k=O) gndj+k=l;)step+; / 步数加一coutstependl;hitint snakeJadderJoca,value;mtij;while(cmn) 棋盘边界obNum=0;cinsnakeladder; 蛇数，梯子数fbr(i=O;isnake;i+)(ciiilocavalue;/输入蛇数据obsta

10、cleloca.fiom=loca;obstacle loca.to=value;obNum+;)fbr(j=0 j ladder;j+)(ciiilocavalue;/输入梯子数据obstacleloca.fiom=loca;obstacle loca.to=value;obNum+;)Slove();return 0;六、提供测试数据和相应的实验结果6 1335 253 235 1620 3300000000000000000000000000000000000 11011100000000000000001000000000000 11011111111100000000001111111000000结臬3七、思考题1、试针对该问题，用深度优先的方式求解，并分析求解时存在的问题。当遍历到传送入II,直接从传送出II继续遍历知道遍历结束，否则回溯到Wlnle(jn*n-1) 只要未搜索到最后就继续搜索for(k= l;k n*n-1) /完成遍历break:test=