算法课程设计

吉林财经大学课程设计报告课程名称：算法课程设计设计题目：插棒游戏所在院系：管理科学与信息工程学院计算机科学与技术指导教师：职称：副教授提交时间：2017年4月目录一、题目描述与设计要求······················11题目描述与设计要求·····················1二、问题分析···························11解空间···························12解空间结构·························23剪枝····························24回溯法的基本思想······················25回溯法的适用条件······················36回溯法的空间树·······················47回溯法的基本步骤······················4三、算法设计···························51伪代码···························5四、复杂性分析··························61时间复杂度·························62空间复杂度该························6五、样本测试、分析与总结·····················61样本测试··························62分析····························72.1、数据类型·······················72.2主要函数思路······················72.3回溯··························83总结····························8参考文献·····························9附录······························10吉林财经大学课程设计报告1一、题目描述与设计要求1题目描述与设计要求这个类似谜题的游戏在等边三角形的板上布置了15个孔。在初始时候，如下图所示，除了一个孔，所有孔都插上了插棒。一个插棒可以跳过它的直接邻居，移到一个空白的位置上。这一跳会把被跳过的邻居从板上移走。设计并实现一个回溯算法，求解该谜题的下列版本：a.已知空孔的位置，求出消去13个插棒的最短步骤，对剩下的插棒的最终位置不限。b.已知空孔的位置，求出消去13个插棒的最短步骤，剩下的插棒最终要落在最初的空孔上。图1二、问题分析1解空间由于棋盘的对称性，棋盘在变化的过程中会形成多个同构的状态。例如初始状态时，空孔只有一个，共有15种基本状态。如图2所示，任意状态与空孔位置在其它的与该空孔颜色相同的点处的状态是同构的，它们可以通过沿中位线翻转和旋转60o互相转换。也就是说，空孔所在位置的颜色相同的个状态是同构的。如空孔位置在顶点处的三个状态，他们仅通过旋转60o的操作即可互相转换。吉林财经大学课程设计报告2图2同构的状态要么都无解，要么有相同数量的解，且他们的解可以根据同构对应变化得到。本题所描述的问题可能无解，也可能有多个解，且同构状态的解也有一定关联。2解空间结构分析整个游戏的过程，发现每合法地走出一步，棋盘上就会少一个棋子,故当该问题有解时，最后都需要走13步。如果无解，必然小于或等于13步。因此，我们的状态树的深度将达到13层，每一个点的分支数量不确定。3剪枝考虑到深度确定这一点，在剪枝的时候就不能用”最短步数”这一个限制条件了。由于对称性，当一个状态被证实无解时，该状态的旋转、对称变换后的同构体也必然无解。因此，可以利用这一特性，对已经证实无解的状态不再探索而减少不必要的试探。4回溯法的基本思想回溯法又称试探法，它采用试错的思想，尝试分步的去解决一个问题。在分步解决问题的过程中，当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候，它将取消上一步甚至是上几步的计算，再通过其它的可能的分步解答再次尝试寻找问题的答案。回溯法通常用最简单的递归方法来实现，在反复重吉林财经大学课程设计报告3复上述的步骤后可能出现两种情况：找到一个可能存在的正确的答案，在尝试了所有可能的分步方法后宣告该问题没有答案。回溯法的本质是深度优先搜索，是一种组织得井井有条的、能避免不必要重复搜索的穷举式搜索算法。在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果（可能）包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。其实回溯法就是对隐式图的深度优先搜索算法。若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。5回溯法的适用条件可用回溯法求解的问题P，通常要能表达为：对于已知的由n元组（x1，x2，…，xn）组成的一个状态空间E={（x1，x2，…，xn）∣xi∈Si，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。换句话说，只要存在0≤j≤n-1，使得（x1，x2，…，xj）违反D中仅涉及到x1，x2，…，xj的约束之一，则以（x1，x2，…，xj）为前缀的任何n元组（x1，x2，…，xj，xj+1，…，xn）一定也违反D中仅涉及到x1，x2，…，xi的一个约束，n≥i≥j。因此，对于约束集D具有完备性的问题P，一旦检测断定某个j元组（x1，x2，…，xj）违反D中仅涉及x1，x2，…，xj的一个约束，就可以肯定，以（x1，x2，…，xj）为前缀的任何n元组（x1，x2，…，xj，xj+1，…，吉林财经大学课程设计报告4xn）都不会是问题P的解，因而就不必去搜索它们、检测它们。回溯法正是针对这类问题，利用这类问题的上述性质而提出来的比枚举法效率更高的算法。6回溯法的空间树回溯法首先将问题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，反之亦然。另外，对于任意的0≤i≤n-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的一个解7回溯法的基本步骤回溯法解决问题，一般有三个步骤：（1）针对所给问题，定义问题的解空间；（2）（2）确定易于搜索的解空间结构；吉林财经大学课程设计报告5（3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。三、算法设计1伪代码ALGORITHMGet_all_moves(i,j)//Get_avail_pegthenupdatesthevariablesmoveandmove_set//Input:Twononnegative,integeriandj//Output:Updatethepeg-boardFori?0tomax_peg_holedoIfpegboard[i]?-1Forj?0tonum_of_rulesdomove_set[move].move_what?peg_move_rules[j].move_what;move_set[move].del_what?peg_move_rules[j].del_what;move_set[move].move_where?peg_move_rules[j].move_where;move++ALGORITHMReset_pegboard(i)//Resetsthepegboardtotheoriginalproblem//Input:integer//Output:originalpegboardFori?0tomax_peg_holedoSwappegboard[i]andorig_pegboard[i]ALGORITHMIs_solve(i)//Judgeproblemissolvedornot//Input:integeri//Output:0or1Fori?0tomax_peg_holedoIfpegboard[i]=1Count++Ifcount=1Return1Return0吉林财经大学课程设计报告6四、复杂性分析1时间复杂度该算法在最好情况下，求得第一种解需要试探13次。因为每次的走法数目不确定，也就是状态数的子孩子数量不确定，状态总数量不确定。但是该数目不大于215-2种。无解时，就是这种情况。对于要求所有的解时，需要遍历整个状态树。2空间复杂度该算法需要维护一个状态栈和一个走法栈。走法栈的深度不超过13，为常数。状态空间树只记录当前路径有关的状态。假设树的平均子树数目为N，则该堆栈的大小约为1/N。五、样本测试、分析与总结1样本测试吉林财经大学课程设计报告72分析2.1、数据类型棋盘。正三角形的棋盘用数组很难表示。自定义最多有六个子节点的Node类，用双向多维链表构成图，表示棋盘。但是这样不适合随机读写，切在判断同构上没有太大优势，因此采用变形的数组表示棋盘。把正三角形的棋盘上的孔左对齐，用5*5的数组的左下半部分表示。此时，棋棒可以左右跳、上下跳、沿着从左上到右下的对角线方向跳。状态空间。把每一步的移动信息（从哪个坐标到哪个坐标）记录下来，构成隐式多叉树。因为用的是回溯法，故只需维护一个棋盘对象，根据走棋信息就可以得到上下的棋盘状态。堆栈。维护一个堆栈，把每一个带探测的状态点放入，方便回溯。链表。考虑到多解的可能性，用一个链表记录结果集。每个节点是一个解的全部移动棒子流程。2.2主要函数思路判断同构。先判断最内部三个点空点数量，若一致再继续判断，否则肯定不是同构。合理选择关键点，可以避免多次遍历数列。吉林财经大学课程设计报告8剪枝。判断是否剪掉该分支的依据是该