算法设计与分析_插棒游戏.docx

算法设计与分析插棒游戏学 院： 信息工程学院 姓 名： 程文毅 学 号： Sxxxxxx 电 话： 152xxxxxxxx 实验室： 理工楼908 2013年12月22日 一、问题描述有一个等边三角形的板上布置了15个孔，初始的时候除了一个孔，其它孔都插上了棒。图1所示为一种可能的情况，空孔的位置不限。一个棒可以跳过它的直接邻居，移到一个空白的位置上。这一跳会把被跳过的邻居从板上移走。要求在下列条件下，求问题的解：A. 已知空孔的位置，求出消去13个棒的最短步骤，对剩下的插棒位置不限制。B. 已知空孔的位置，求出消去13个插棒的最短步骤，剩下的插棒最终要落在最初的空孔位置上。图1 棋盘示例二、回溯法2.1 回溯法的基本思想回溯法又称试探法，它采用试错的思想，尝试分步的去解决一个问题。在分步解决问题的过程中，当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候，它将取消上一步甚至是上几步的计算，再通过其它的可能的分步解答再次尝试寻找问题的答案。回溯法通常用最简单的递归方法来实现，在反复重复上述的步骤后可能出现两种情况：l 找到一个可能存在的正确的答案l 在尝试了所有可能的分步方法后宣告该问题没有答案回溯法的本质是深度优先搜索，是一种组织得井井有条的、能避免不必要重复搜索的穷举式搜索算法。在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果（可能）包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。其实回溯法就是对隐式图的深度优先搜索算法。 若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。 而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。2.2 回溯法的适用条件可用回溯法求解的问题P，通常要能表达为：对于已知的由n元组（x1，x2，xn）组成的一个状态空间E=（x1，x2，xn）xiSi ，i=1，2，n，给定关于n元组中的一个分量的一个约束集D，要求E中满足D的全部约束条件的所有n元组。其中Si是分量xi的定义域，且 |Si| 有限，i=1，2，n。我们称E中满足D的全部约束条件的任一n元组为问题P的一个解。解问题P的最朴素的方法就是枚举法，即对E中的所有n元组逐一地检测其是否满足D的全部约束，若满足，则为问题P的一个解。但显然，其计算量是相当大的。我们发现，对于许多问题，所给定的约束集D具有完备性，即i元组（x1，x2，xi）满足D中仅涉及到x1，x2，xi的所有约束意味着j（j=i）元组（x1，x2，xj）一定也满足D中仅涉及到x1，x2，xj的所有约束，i=1，2，n。换句话说，只要存在0jn-1，使得（x1，x2，xj）违反D中仅涉及到x1，x2，xj的约束之一，则以（x1，x2，xj）为前缀的任何n元组（x1，x2，xj，xj+1，xn）一定也违反D中仅涉及到x1，x2，xi的一个约束，nij。因此，对于约束集D具有完备性的问题P，一旦检测断定某个j元组（x1，x2，xj）违反D中仅涉及x1，x2，xj的一个约束，就可以肯定，以（x1，x2，xj）为前缀的任何n元组（x1，x2，xj，xj+1，xn）都不会是问题P的解，因而就不必去搜索它们、检测它们。回溯法正是针对这类问题，利用这类问题的上述性质而提出来的比枚举法效率更高的算法。2.2 回溯法的空间树回溯法首先将问题P的n元组的状态空间E表示成一棵高为n的带权有序树T，把在E中求问题P的所有解转化为在T中搜索问题P的所有解。树T类似于检索树，它可以这样构造：设Si中的元素可排成xi(1) ，xi(2) ，xi(mi-1) ，|Si| =mi，i=1，2，n。从根开始，让T的第I层的每一个结点都有mi个儿子。这mi个儿子到它们的双亲的边，按从左到右的次序，分别带权xi+1(1) ，xi+1(2) ，xi+1(mi) ，i=0，1，2，n-1。照这种构造方式，E中的一个n元组（x1，x2，xn）对应于T中的一个叶子结点，T的根到这个叶子结点的路径上依次的n条边的权分别为x1，x2，xn，反之亦然。另外，对于任意的0in-1，E中n元组（x1，x2，xn）的一个前缀I元组（x1，x2，xi）对应于T中的一个非叶子结点，T的根到这个非叶子结点的路径上依次的I条边的权分别为x1，x2，xi，反之亦然。特别，E中的任意一个n元组的空前缀（），对应于T的根。因而，在E中寻找问题P的一个解等价于在T中搜索一个叶子结点，要求从T的根到该叶子结点的路径上依次的n条边相应带的n个权x1，x2，xn满足约束集D的全部约束。在T中搜索所要求的叶子结点，很自然的一种方式是从根出发，按深度优先的策略逐步深入，即依次搜索满足约束条件的前缀1元组（x1i）、前缀2元组（x1，x2）、，前缀I元组（x1，x2，xi），直到i=n为止。在回溯法中，上述引入的树被称为问题P的状态空间树；树T上任意一个结点被称为问题P的状态结点；树T上的任意一个叶子结点被称为问题P的一个解状态结点；树T上满足约束集D的全部约束的任意一个叶子结点被称为问题P的一个回答状态结点，它对应于问题P的一个解2.4 回溯法的基本步骤回溯法解决问题，一般有三个步骤：（1）针对所给问题，定义问题的解空间；（2）确定易于搜索的解空间结构；（3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。三、本题解题思路 本题所用的算法思想就是回溯法。3.1 解空间由于棋盘的对称性，棋盘在变化的过程中会形成多个同构的状态。例如初始状态时，空孔只有一个，共有15种基本状态。如图2 所示，任意状态与空孔位置在其它的与该空孔颜色相同的点处的状态是同构的，它们可以通过沿中位线翻转和旋转60o 互相转换。也就是说，空孔所在位置的颜色相同的个状态是同构的。如空孔位置在顶点处的三个状态，他们仅通过旋转60o的操作即可互相转换。 图 2 初始状态空孔位置同构图同构的状态要么都无解，要么有相同数量的解，且他们的解可以根据同构对应变化得到。本题所描述的问题可能无解，也可能有多个解，且同构状态的解也有一定关联。3.2 解空间结构分析整个游戏的过程，发现每合法地走出一步，棋盘上就会少一个棋子,故当该问题有解时，最后都需要走13步。如果无解，必然小于或等于13步。因此，我们的状态树的深度将达到13层，每一个点的分支数量不确定。3.3 剪枝考虑到深度确定这一点，在剪枝的时候就不能用”最短步数”这一个限制条件了。由于对称性，当一个状态被证实无解时，该状态的旋转、对称变换后的同构体也必然无解。因此，可以利用这一特性，对已经证实无解的状态不再探索而减少不必要的试探。四、编程提要 4.1 数据类型1、 棋盘。正三角形的棋盘用数组很难表示。自定义最多有六个子节点的Node类，用双向多维链表构成图，表示棋盘。但是这样不适合随机读写，切在判断同构上没有太大优势，因此采用变形的数组表示棋盘。把正三角形的棋盘上的孔左对齐，用5*5的数组的左下半部分表示。此时，棋棒可以左右跳、上下跳、沿着从左上到右下的对角线方向跳。2、 状态空间。把每一步的移动信息（从哪个坐标到哪个坐标）记录下来，构成隐式多叉树。因为用的是回溯法，故只需维护一个棋盘对象，根据走棋信息就可以得到上下的棋盘状态。3、 堆栈。维护一个堆栈，把每一个带探测的状态点放入，方便回溯。4、 链表。考虑到多解的可能性，用一个链表记录结果集。每个节点是一个解的全部移动棒子流程。4.2 主要函数思路1. 判断同构。先判断最内部三个点空点数量，若一致再继续判断，否则肯定不是同构。合理选择关键点，可以避免多次遍历数列。2. 剪枝。判断是否剪掉该分支的依据是该状态是否与无解状态集合中的某个元素同构。其本质是查找，按照含有棋子数量、中心三角形元素个数、外顶点状态等信息可以对无解状态集合构建二叉书，查找时效率就会高狠多。3. 回溯a) 把初始状态放入堆栈。b) 把堆栈最顶上元素取出，判断棋盘状态，若：i. 棋盘只剩一个元素。把全部堆栈信息复制，作为一个解记录到解集中。ii. 棋盘剩多个元素1. 还有孩子节点。把该节点的所有不与空解状态集合中同构的下一状态的走法记录到堆栈中。2. 没有孩子节点。把这时的棋盘复制，放到空解状态集合中c) 若堆栈不为空，重复b。根据问题A、B筛选解集，并打印。4.3 关键算法实现1. Game.init();/初始化棋盘2. Game.recall()/回溯法求解3. 4. /记录走法的堆栈5. Stack steps = new Stack();6. /记录棋盘状态的的堆栈7. Stack boards = new Stack();8. /保存下一次走法的变量。重复使用。9. ArrayList moves = new ArrayList();10. Board b = new Board();11. /初始化棋盘堆栈，为回溯做准备。12. boards.push(board);13. /开始回溯求解14. while (!boards.empty() 15. b = boards.pop();16. /*17. * 到上一次探索的节点的父节点的位置了。该节点的子孩子一遍历完，对该解法已经探索完了，故该把它对应的走法取消。18. */19. if(b=null)20. steps.pop();21. continue;22. 23. / 记录走棋过程24. steps.push(b.getLastMove();25. /当前状态是正确的终止状态26. if (b.count = 1) 27. / 记录解法。28. boolean isB = false;29. if(b.lastMove.y2=y&b.lastMove.x2 = x)30. 31. t_succeed_B+;32. isB = true;33. 提示已经找到B方案的解34. ;35. 提示已经找到A方案的解36. /演示流程，记录当前解法。37. ArrayList solution = new ArrayList();38. Board sb = board;39. for (int i = 0; i steps.size(); i+) 40. if(i!=0)/第一条记录是初始棋盘的最后一步，无意义41. sb = sb.move(steps.get(i);42. steps.get(i).show();43. sb.show();44. solution.add(steps.get(i);45. 46. 记录solution 或者展示。47. steps.pop();/ 取消最后一步走法，继续48. else 49. moves = b.getMoves();50. / 没有走法可以继续了。状态被迫终止，取消走法，回溯51. if (moves.size() = 0) 52. steps.pop();53. 54. else 55. / 还有其他走法。则把所有子孩子状态入栈。继续回溯56. boards.push(null);57. for (Move m : moves) 58. boards.push(b.move(m);59. 60. 61. 62. /end - while 63.64. 输出结果：65. System.out.print