算法课程设计.docx

《算法课程设计.docx》由会员分享，可在线阅读，更多相关《算法课程设计.docx（18页珍藏版）》请在第一文库网上搜索。

1、课程名称：设计题目：所在院系：指导教师：职称：提交时间：副教授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题目描述与设计要求这个类似谜题的游戏在等边三角

2、形的板上布置了15个孔。在初始时候，如下图所示，除了一个孔，所有孔都插上了插棒。一个插棒可以跳过它的直接邻居，移到一个空白的位置上。这一跳会把被跳过的邻居从板上移走。设计并实现一个回溯算法，求解该谜题的下列版本：a.已知空孔的位置，求出消去13个插棒的最短步骤，对剩下的插棒的最终位置不限。b.已知空孔的位置，求出消去13个插棒的最短步骤，剩下的插棒最终要落在最初的空孔上。O二、问题分析1解空间由于棋盘的对称性，棋盘在变化的过程中会形成多个同构的状态。例如初始状态时，空孔只有一个，共有15种基本状态。如图2所示，任意状态与空孔位置在其它的与该空孔颜色相同的点处的状态是同构的，它们可以通过沿中位线

3、翻转和旋转60o互相转换。也就是说，空孔所在位置的颜色相同的个状态是同构的。如空孔位置在顶点处的三个状态，他们仅通过旋转60。的操作即可互相转换。图2同构的状态要么都无解，要么有相同数量的解，且他们的解可以根据同构对应变化得到。本题所描述的问题可能无解，也可能有多个解，且同构状态的解也有一定关联。2解空间结构分析整个游戏的过程，发现每合法地走出一步，棋盘上就会少一个棋子，故当该问题有解时，最后都需要走13步。如果无解，必然小于或等于13步。因此,我们的状态树的深度将达到13层，每一个点的分支数量不确定。3剪枝考虑到深度确定这一点，在剪枝的时候就不能用”最短步数”这一个限制条件了。由于对称性，当

4、一个状态被证实无解时，该状态的旋转、对称变换后的同构体也必然无解。因此，可以利用这一特性，对已经证实无解的状态不再探索而减少不必要的试探。4回溯法的基本思想回溯法又称试探法，它采用试错的思想，尝试分步的去解决一个问题。在分步解决问题的过程中，当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候，它将取消上一步甚至是上几步的计算，再通过其它的可能的分步解答再次尝试寻找问题的答案。回溯法通常用最简单的递归方法来实现，在反复重复上述的步骤后可能出现两种情况：找到一个可能存在的正确的答案，在尝试了所有可能的分步方法后宣告该问题没有答案。回溯法的本质是深度优先搜索，是一种组织得井井有条的、能避免

5、不必要重复搜索的穷举式搜索算法。在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果（可能）包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。其实回溯法就是对隐式图的深度优先搜索算法。若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。5回溯法的适用条件可用回溯法求解的问题P,通常要能表达为:对于已知的由n元组（x,X2,，Xn）组成的一个状态空间E=（X1，X2，X）IXjS

6、i,i=1,2,，）,给定关于n元组中的一个分量的一个约束集D,要求E中满足D的全部约束条件的所有n元组。其中Si是分量Xi的定义域，且ISi1有限，i=1,2,，n0我们称E中满足D的全部约束条件的任一n元组为问题P的一个解。解问题P的最朴素的方法就是枚举法，即对E中的所有n元组逐一地检测其是否满足D的全部约束，若满足，则为问题P的一个解。但显然，其计算量是相当大的。我们发现，对于许多问题，所给定的约束集D具有完备性，即i元组（x“X2,，Xi）满足D中仅涉及到小,x2,，Xi的所有约束意味着j（j=i）元组（x,x2,Xj）一定也满足D中仅涉及到Xi,X2,，Xj的所有约束，i=1,2,，

7、no换句话说，只要存在0jn-1,使得（X1，X2,，Xj）违反D中仅涉及到x,X2,，Xj的约束之一，则以（x,X2,，Xj）为前缀的任何n元组（XI，X2，Xj，Xj+1，Xn）一定也违反D中仅涉及到X,X2，Xi的一个约束，nijo因此，对于约束集D具有完备性的问题P,一旦检测断定某个j元组（XI，X2,，Xj）违反D中仅涉及X1,X2,，Xj的一个约束，就可以肯定，以（XI，X2,，Xj）为前缀的任何n元组（X”X2,，Xj,Xj1,，Xn)都不会是问题P的解，因而就不必去搜索它们、检测它们。回溯法正是针对这类问题，利用这类问题的上述性质而提出来的比枚举法效率更高的算法。6回溯法的空间

8、树回溯法首先将问题P的n元组的状态空间E表示成一棵高为n的带权有序树T,把在E中求问题P的所有解转化为在T中搜索问题P的所有解。树T类似于检索树，它可以这样构造：设Si中的元素可排成Xi成)，Xi(2),，xi(mi-1),Si=mi,i=1,2,n0从根开始，让T的第I层的每一个结点都有Ini个儿子。这mi个儿子到它们的双亲的边，按从左到右的次序，分别带权Xi+1(1),xi+1(2),xi+1(mi),i=0,1,2,n-10照这种构造方式，E中的一个n元组(x1，x2,xn)对应于T中的一个叶子结点，T的根到这个叶子结点的路径上依次的n条边的权分别为x,X2，Xn,反之亦然。另外，对于任

9、意的OWiWnT,E中n元组(X1,X2，Xn)的一个前缀I元组(X1,X2，Xi)对应于T中的一个非叶子结点，T的根到这个非叶子结点的路径上依次的I条边的权分别为X”x2,，Xi,反之亦然。特别，E中的任意一个n元组的空前缀()，对应于T的根。因而，在E中寻找问题P的一个解等价于在T中搜索一个叶子结点，要求从T的根到该叶子结点的路径上依次的n条边相应带的n个权Xi,X2,，Xn满足约束集D的全部约束。在T中搜索所要求的叶子结点，很自然的一种方式是从根出发,按深度优先的策略逐步深入，即依次搜索满足约束条件的前缀1元组(xh)、前缀2元组(x,X2)、，前缀I元组(X1，X2，Xi),，直到i=

10、n为止。在回溯法中，上述引入的树被称为问题P的状态空间树；树T上任意一个结点被称为问题P的状态结点；树T上的任意一个叶子结点被称为问题P的一个解状态结点；树T上满足约束集D的全部约束的任意一个叶子结点被称为问题P的一个回答状态结点，它对应于问题P的一个解7回溯法的基本步骤回溯法解决问题，一般有三个步骤：(1)针对所给问题，定义问题的解空间；(2) (2)确定易于搜索的解空间结构；(3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索三、算法设计1伪代码A1GORITHMGet_a11_moves(ij)/Get_avai1_pegthenupdatesthevariab1esmo

11、veandmove_set/Input:Twononnegativejntegeriandj/OutputiUpdatethepeg-boardFori?0tomax_peg_ho1edo1fpegboardi7-1Forj?0tonum_of_ru1esdomove_setmove.move_what?peg_move_ru1esO.move_what;move_setmove.de1_what?peg_move_ru1esO.de1_what;move_setmove.move_where?peg_move_ru1esj.move_where;move+A1GORITHMReset_peg

12、board(i)/Resetsthepegboardtotheorigina1prob1em/InputJnteger/Outputiongina1pegboardFori?0tomax_peg_ho1edoSwappegboardiandorig_pegboardiA1GORITHM1s_so1ve(i)/Judgeprob1emisso1vedornot/InputJntegeri/Output:Oor1Fori?0tomax_peg_ho1edo1fpegboardi=1Count+Ifcount=IReturn1ReturnO四、复杂性分析1时间复杂度该算法在最好情况下，求得第一种解需

13、要试探13次。因为每次的走法数目不确定，也就是状态数的子孩子数量不确定，状态总数量不确定。但是该数目不大于2、2种。无解时，就是这种情况。对于要求所有的解时，需要遍历整个状态树。2空间复杂度该算法需要维护一个状态栈和一个走法栈。走法栈的深度不超过13,为常数。状态空间树只记录当前路径有关的状态。假设树的平均子树数目为N,则该堆栈的大小约为1/No五、样本测试、分析与总结1样本测试精输人孔洞留位置:12Theinitia1pegboadsetup：000100000000000So1utiontothepegboardprob1em：initerationsStepStepStepStepSte

14、pStepStep：05：07：:MoueMoueMoueMoueMoueMoueMoue14To110?03120601ToToToToToTo12Step13Step09Step10Step05Step04Step04:06：:MOUeMoveMoueMoveMoueMoue05To14To10To02To15To07To1412080?0602P*essAnykey.Theinitia1pegboardsetup：000000000000100So1utiontothepegboardprob1em：initerationsStep01：Moue14To05Step:Moue12To14Step：Moue04To13-Step:MOUe11To04Step05：Moue02To07Step:Moue14To12Step:Moue03To08Step:Moue10To03Step：Moue01To06