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

1、实验 7蛇和梯子问题的算法设计与实现实验学时：2实验类型：设计一、实验目的1、掌握深度优先和广度优先搜索算法的基本和设计方法；2、理解贪心算法的局限性；3、提高分析与解决问题的能力。二、预习与参考1、认真阅读或参考书, 掌握贪心算法、深度优先和广度优先搜索算法的基本；2、写出求解“蛇和梯子”的程序；3、设计好测试用例。【实验题】“蛇和梯子”是一个在 NN（0N=20)的方格棋盘上进行的。（见下图）方格从 1 到N 的平方。除了第 1 号和最后的方格，其它的格子都有可能有蛇或梯子存在（蛇和梯子的数量及具置由输入确定，它们的数量都在 100 之内并且蛇和梯子不能放置，也就是在任何了放置两者首尾的方

2、格之间至少还有一个未放置任何东西的格子）。开始的时候玩家把他们的标志物放在 1 号格子中。玩家轮流以扔的方式移动他们的指示物。如果一个指示物到达了一条蛇的嘴部，则把它移回蛇的尾部。如果一个指示物到达了一个梯子的底部则将它移动到梯子的顶部。如果你是一个可以控制的高手，现在请求出你至少需要扔几次才能到达标为 N2 的格子。（比如在上图所示例一中，你的方案应该是走 4 步到达 5 并由梯子上升到 16，再走 4 步到达 20 并由梯子上升到 33，然后走 3 步。这样，你一共需要扔 3 次。而在例二中，你的方案应该是连扔 4 个 6。）【实验提示】从上面的实验题中很容易看出，这个问题是不能用贪心算法

3、解决的，因为你不能保证在这步到达一个数码比较大的格子就意味着最好的效率（即使是通过梯子到达了一个这步所能到达的最大号码的格子），也就是说，号码的大小并不能代表从这个格子到达终点所需要的步数上的多少，这就带给一个启发：蛇和梯子真的需要看成是两个东西来分别处理么？实际上确实是不需要的，蛇和梯子的本质就是经常在中说的“单向传送点”，只不过梯子的底部是而顶部是出口，蛇的嘴部是而尾部是出口罢了，对于他们的描述完全可以选择相同的结构：struct SnakeAndLadderfrom,to;接下来要考虑的是解决问题的方法。贪心算法被否定之后，的选择可能会是搜索，对于本题所采用的搜索显然应该以广度优先的方式

4、进行，但是稍加分析就会发现如果单纯地采用广度优先搜索会产生许多重复的结点，现在指示物处于某格的结点简称为结点 X，那么比如在例 1 中，第 1 步过后，队列中存放的结点是 2，23，4，16，6，7，在第二步时，当结点 2 成为扩展结点时将生成结点 23、4、16、6、7、8，其中只有 8 不存在于当前活结点队列中，即使加以判断，不把重复的结点再次加入队列中，那至少也需要对活结点队列进行搜索。实际上完全有更好的方法。应该，采用树状结构和搜索的方法处理问题其重要的一点是利用祖先结点的差异性来对儿子结点做不同的处理。然而在本实验中，儿子结点的生成只依赖于父结点的信息而与其它祖先结点无关，所以采用树

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

6、：描述状态数组元素的内容（从表示第 1 个格的元素排列到表示最后一个格的元素）起始状态000000000000000000第 1 步之后000010000000000000第 2 步之后000111111110001000到第 3 步之后，数组的最后一个元素已经变为了 1，这即表明存在案，使得扔 3 次就可以完成任务。以下是实现此算法的主要部分代码， 数组下标 0 size*size-1 的元素分别表示了从第 1 格到最后一格的状态，step步数，obstacle 是struct SnakeAndLadder 的向量，描述了蛇和梯子的传送和出口：/初始化状态数组和步数for (j=1;jsiz

7、e*size;j+)gridj=0;grid0=1;step=0;while (gridsize*size-1=0)for (j=0;jsize*size;j+)gridbakj=gridj;for (j=0;jsize*size;j+)gridj=0;for (j=0;jsize*size-1;j+)/搜索所有的格子（最后一格不用搜索因为在过程结束前它一定为 0）if (gridbakj=0)/若在上一步无法到达此格则跳出continue;for (k=1;ksize*size-1)break;for (l=0;lobstacle.size();l+)/如果此格是一个传送，将传送出口的格子可

8、达if (obstaclel.from=j+k)gridobstaclel.to=1;test=1;break;第 3 步之后000001111111111101if (test=0 & gridj+k=0)gridj+k=1;step+;/步数加一过程执行完毕后，输出 step 即可。另外，此题规定棋盘为 N*N 大小只是为了输入方便，举例画图方便，实际上多大的棋盘都是一样可以看作一条直线，数组用一维的便可以了。三、实验要求上机实验时，一人一组，独立上机。采用树状结构和搜索的方法处理问题。四、实验步骤1、先用广度优先的方式求解该问题，并测试你的程序，直至正确为止；。五、测试样例输入 6 1 335 253 235 1620 33样例输