算法课程设计

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吉林财经大学课

2、程设计报告一、题目描述与设计要求1 题目描述与设计要求 这个类似谜题的游戏在等边三角形的板上布置了 15 个孔。在初始时候，如下图所示，除了一个孔，所有孔都插上了插棒。一个插棒可以跳过它的直接邻居，移到一个空白的位置上。这一跳会把被跳过的邻居从板上移走。设计并实现一个回溯算法，求解该谜题的下列版本：a.已知空孔的位置，求出消去 13 个插棒的最短步骤，对剩下的插棒的最终位置不限。b.已知空孔的位置，求出消去 13 个插棒的最短步骤，剩下的插棒最终要落在最初的空孔上。图12、 问题分析1 解空间 由于棋盘的对称性，棋盘在变化的过程中会形成多个同构的状态。 例如初始状态时，空孔只有一个，共有15种

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

4、每一个点的分支数量不确定。3 剪枝考虑到深度确定这一点，在剪枝的时候就不能用”最短步数”这一个限制条件了。由于对称性，当一个状态被证实无解时，该状态的旋转、对称变换后的同构体也必然无解。因此，可以利用这一特性，对已经证实无解的状态不再探索而减少不必要的试探。4 回溯法的基本思想回溯法又称试探法，它采用试错的思想，尝试分步的去解决一个问题。在分步解决问题的过程中，当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候，它将取消上一步甚至是上几步的计算，再通过其它的可能的分步解答再次尝试寻找问题的答案。回溯法通常用最简单的递归方法来实现，在反复重复上述的步骤后可能出现两种情况：找到一个可能存

5、在的正确的答案，在尝试了所有可能的分步方法后宣告该问题没有答案。回溯法的本质是深度优先搜索，是一种组织得井井有条的、能避免不必要重复搜索的穷举式搜索算法。在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果（可能）包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。其实回溯法就是对隐式图的深度优先搜索算法。 若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。 而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。5 回溯法的适用条

6、件可用回溯法求解的问题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中仅涉及到x

7、1，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的解，因而

8、就不必去搜索它们、检测它们。回溯法正是针对这类问题，利用这类问题的上述性质而提出来的比枚举法效率更高的算法。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中的一个

9、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中搜索所要求的叶子结点，很自然的一种方式是从根出发，

10、按深度优先的策略逐步深入，即依次搜索满足约束条件的前缀1元组（x1i）、前缀2元组（x1，x2）、，前缀I元组（x1，x2，xi），直到i=n为止。在回溯法中，上述引入的树被称为问题P的状态空间树；树T上任意一个结点被称为问题P的状态结点；树T上的任意一个叶子结点被称为问题P的一个解状态结点；树T上满足约束集D的全部约束的任意一个叶子结点被称为问题P的一个回答状态结点，它对应于问题P的一个解7 回溯法的基本步骤回溯法解决问题，一般有三个步骤：（1） 针对所给问题，定义问题的解空间；（2） （2）确定易于搜索的解空间结构； （3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。3

11、、 算法设计1 伪代码ALGORITHM Get_all_moves(i,j)/Get_avail_peg then updates the variables move and move_set/Input :Two nonnegative,integer i and j/Output:Update the peg-boardFori?0 to max_peg_hole doIfpegboardi?-1For j?0 to num_of_rules domove_setmove.move_what?peg_move_rulesj.move_what;move_setmove.del_what

12、?peg_move_rulesj.del_what;move_setmove.move_where?peg_move_rulesj.move_where;move+ALGORITHM Reset_pegboard(i)/Resets the pegboard to the original problem/Input :integer /Output:original pegboardFori?0 to max_peg_hole doSwap pegboardi andorig_pegboardiALGORITHM Is_solve(i)/Judge problem is solved or

13、not /Input :integer i/Output: 0 or 1Fori?0 to max_peg_hole do Ifpegboardi=1 Count+ Ifcount=1 Return 1Return 0四、复杂性分析1 时间复杂度该算法在最好情况下，求得第一种解需要试探13次。因为每次的走法数目不确定，也就是状态数的子孩子数量不确定，状态总数量不确定。但是该数目不大于 215-2种。无解时，就是这种情况。对于要求所有的解时，需要遍历整个状态树。2 空间复杂度该算法需要维护一个状态栈和一个走法栈。走法栈的深度不超过13，为常数。状态空间树只记录当前路径有关的状态。假设树的平均子树

14、数目为N，则该堆栈的大小约为1/N。5、 样本测试、分析与总结1 样本测试2 分析2.1、数据类型棋盘。正三角形的棋盘用数组很难表示。自定义最多有六个子节点的Node类，用双向多维链表构成图，表示棋盘。但是这样不适合随机读写，切在判断同构上没有太大优势，因此采用变形的数组表示棋盘。把正三角形的棋盘上的孔左对齐，用5*5的数组的左下半部分表示。此时，棋棒可以左右跳、上下跳、沿着从左上到右下的对角线方向跳。状态空间。把每一步的移动信息（从哪个坐标到哪个坐标）记录下来，构成隐式多叉树。因为用的是回溯法，故只需维护一个棋盘对象，根据走棋信息就可以得到上下的棋盘状态。堆栈。维护一个堆栈，把每一个带探测的

15、状态点放入，方便回溯。链表。考虑到多解的可能性，用一个链表记录结果集。每个节点是一个解的全部移动棒子流程。2.2 主要函数思路判断同构。先判断最内部三个点空点数量，若一致再继续判断，否则肯定不是同构。合理选择关键点，可以避免多次遍历数列。剪枝。判断是否剪掉该分支的依据是该状态是否与无解状态集合中的某个元素同构。其本质是查找，按照含有棋子数量、中心三角形元素个数、外顶点状态等信息可以对无解状态集合构建二叉书，查找时效率就会高狠多。2.3 回溯把初始状态放入堆栈。把堆栈最顶上元素取出，判断棋盘状态，若：棋盘只剩一个元素。把全部堆栈信息复制，作为一个解记录到解集中。棋盘剩多个元素还有孩子节点。把该节

16、点的所有不与空解状态集合中同构的下一状态的走法记录到堆栈中。没有孩子节点。把这时的棋盘复制，放到空解状态集合中若堆栈不为空，重复b。根据问题A、B筛选解集，并打印。3 总结回溯算法主要是通过深度试探查询的方法，找到解空间，并对不满足条件和不是最优组合的方法进行剪枝，从而得到最优解的方法。 通过这次运用回溯算法的课程设计，使我们对回溯算法原理和特点有了更深的理解和掌握。并且通过这次合作形式的作业，我们更加懂得了分工合作的意义，增强了自己的协作能力和团队合作的意识。参考文献1. 侯焯明.面向教育云平台的智能排课系统的设计与实现D中山大学出版社.20152. 刘彦.基于优先级与回溯算法的排课系统的设

17、计与实现D黑龙江大学出版社.20123. (美) Anany Levitin .算法设计与分析基础（第三版 影印版）清华大学出版社.2013附录/pegsolve.cpp#include #include #include #include #include using namespace std;const int MAX_PEG_HOLE=15;const int NUM_OF_RULES=36;const int MOVES=0;const int DATA_OFFSET=1;const int INVALID_PEG=-1;/pegboard to play onstatic int

18、pegboard15;/default pegboard/(1 means there is a peg; 0 means there is no peg)static int orig_pegboard15 =1,1 , 1,1 , 1 , 1,1 , 1 , 1 , 1,1 , 1 , 1 , 1 , 1;#define VALID_HOLE(x) (x=0 & x=14)/* Layout of the pegboard:* 00,* 01, 02* 03, 04, 05,* 06, 07, 08, 09,* 10, 11, 12, 13, 14*/static int move;/da

19、ta structure representing a movestruct _move_setint move_what;int del_what;int move_where;typedef _move_set MOVE_SET;static MOVE_SET move_setMAX_PEG_HOLE;static MOVE_SET peg_move_rulesNUM_OF_RULES=/* move_what OVER del_what TO move_where* = , */0,1,3, 0,2,5,1,4,8, 1,3,6,2,4,7, 2,5,9,3,1,0, 3,4,5, 3,

20、7,12, 3,6,10,4,8,13, 4,7,11,5,9,14, 5,2,0, 5,4,3, 5,8,12,6,3,1, 6,7,8,7,4,2, 7,8,9,8,4,1, 8,7,6,9,5,2, 9,8,7,10,6,3, 10,11,12,11,7,4, 11,12,13,12,7,3, 12,8,5, 12,11,10, 12,13,14,13,8,4, 13,12,11,14,9,5, 14,13,12;/*=reset_pegboard() resetsthe pegboard to theoriginal problem.=*/void reset_pegboard( )i

21、nt i;for( i = 0; i MAX_PEG_HOLE; i+ )pegboardi = orig_pegboardi;/end of reset_pegboard/*=is_solved() returns TRUEif pegboard is solved.=*/unsigned char is_solved( )int i;int count = 0; /count how many pegs there arefor( i = 0; i MAX_PEG_HOLE; i+ )if ( pegboardi ) count+ ;if ( count = 1 ) return 1; /

22、pegboard solved!return 0;/end of is_solved/*=display_pegboard displaysthe current statusof the pegboard.=*/void display_pegboard( )printf( n );printf( %dn , pegboard0 );printf( %d %dn , pegboard1 , pegboard2 );printf( %d %d %dn , pegboard3 , pegboard4 , pegboard5 );printf( %d %d %d %dn , pegboard6 ,

23、 pegboard7 , pegboard8 , pegboard9 );printf( %d %d %d %d %dn,pegboard10 , pegboard11 , pegboard12 , pegboard13 , pegboard14 );printf( n );/end of display_pegboard/*=get_avail_peg updatesthe variables move andmove_set=*/void get_all_moves( )int i , j; /loop countersmove = 0; /initialize # of movesmov

24、e_setmove.move_what = -1;move_setmove.del_what = -1;move_setmove.move_where = -1;for( i = 0; i MAX_PEG_HOLE; i+ ) /check all holesif ( !pegboardi ) /if there is a holefor( j = 0; j NUM_OF_RULES; j+)if (i=peg_move_rulesj.move_where) &(pegboardpeg_move_rulesj.del_what)/* can we move a peg to this hole

25、? */if (pegboardpeg_move_rulesj.move_what)move_setmove.move_what=peg_move_rulesj.move_what;move_setmove.del_what=peg_move_rulesj.del_what;move_setmove.move_where=peg_move_rulesj.move_where;move+; /increment move count /end of if /end of if/end of for/end of if/end of for/end of get_avail_peg/*=movep

26、eg() does theactual moving of a peg.=*/void movepeg( int move_what , int del_what , int move_where )pegboardmove_what = 0;pegboarddel_what = 0;pegboardmove_where = 1;/end of movepeg/*=usage() displayshow this app canbe invoked.=*/void usage()printf(The Pegboard Solvern);printf(Usage:n);printf(tpegso

27、lve n);printf(where,n);printf(ttis the empty hole on the pegboard.n);printf(ttHole# is between 1 and 15, inclusive.n);printf(nLayout of the pegboard:n);printf( 01,n);printf( 02, 03n);printf( 04, 05, 06,n);printf( 07, 08, 09, 10,n);printf(11, 12, 13, 14, 15n);/end of usage()/*=main starts here=*/int

28、main( )int argc;int hole_num; / initial hole numbertime_t t; / seed value for the random generatorunsigned long l = 0; / attempt number to solve problemint trace = 0; / when a solution is found, remember the stepsint i; / loop counterint s;MOVE_SET step_to_solve100; / steps to the solutionint rnd_mo

29、ve; / for random selection in a move seta/* check if the user gave a valid scenario*/cout请输入孔洞的位置：argc;/couts;/* validate the hole# */hole_num = argc-1;if(!VALID_HOLE(hole_num)usage();exit(1);/* create the hole on the pegboard */orig_pegboardhole_num = 0;srand(unsigned)time(NULL);/play until a solution is reached/while(step_to_solvetrace.move_where=13)dowhile ( ! is_solved() )/ while(step_to_solvetrace.move_where=13)l+;reset_pegboard(); /reset to the original problemget_all_moves(); /get # of moves, and the set of movestrace =