算法课程设计

吉林财经大学。

课程设计报告。

一、题目描述与设计要求 1

1 题目描述与设计要求 1

二、问题分析 1

1 解空间 1

2 解空间结构 2

3 剪枝 2

4 回溯法的基本思想 2

5 回溯法的适用条件 3

6 回溯法的空间树 4

7 回溯法的基本步骤 4

三、算法设计 5

1 伪** 5

四、复杂性分析 6

1 时间复杂度 6

2 空间复杂度该 6

五、样本测试、分析与总结 6

1 样本测试 6

2 分析 7

2.1、数据类型 7

2.2 主要函数思路 7

2.3 回溯 8

3 总结 8

参考文献 9

附录 10这个类似谜题的游戏在等边三角形的板上布置了 15 个孔。在初始时候，如下图所示，除了一个孔，所有孔都插上了插棒。一个插棒可以跳过它的直接邻居，移到一个空白的位置上。

这一跳会把被跳过的邻居从板上移走。设计并实现一个回溯算法，求解该谜题的下列版本：

a.已知空孔的位置，求出消去 13 个插棒的最短步骤，对剩下的插棒的最终位置不限。

b.已知空孔的位置，求出消去 13 个插棒的最短步骤，剩下的插棒最终要落在最初的空孔上。

图1由于棋盘的对称性，棋盘在变化的过程中会形成多个同构的状态。

例如初始状态时，空孔只有一个，共有15种基本状态。如图2 所示，任意状态与空孔位置在其它的与该空孔颜色相同的点处的状态是同构的，它们可以通过沿中位线翻转和旋转60o 互相转换。也就是说，空孔所在位置的颜色相同的个状态是同构的。

如空孔位置在顶点处的三个状态，他们仅通过旋转60o的操作即可互相转换。

图2同构的状态要么都无解，要么有相同数量的解，且他们的解可以根据同构对应变化得到。

本题所描述的问题可能无解，也可能有多个解，且同构状态的解也有一定关联。

分析整个游戏的过程，发现每合法地走出一步，棋盘上就会少一个棋子，故当该问题有解时，最后都需要走13步。如果无解，必然小于或等于13步。因此，我们的状态树的深度将达到13层，每一个点的分支数量不确定。

考虑到深度确定这一点，在剪枝的时候就不能用”最短步数”这一个限制条件了。由于对称性，当一个状态被证实无解时，该状态的旋转、对称变换后的同构体也必然无解。因此，可以利用这一特性，对已经证实无解的状态不再探索而减少不必要的试探。

回溯法又称试探法，它采用试错的思想，尝试分步的去解决一个问题。在分步解决问题的过程中，当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候，它将取消上一步甚至是上几步的计算，再通过其它的可能的分步解答再次尝试寻找问题的答案。回溯法通常用最简单的递归方法来实现，在反复重复上述的步骤后可能出现两种情况：

找到一个可能存在的正确的答案，在尝试了所有可能的分步方法后宣告该问题没有答案。

回溯法的本质是深度优先搜索，是一种组织得井井有条的、能避免不必要重复搜索的穷举式搜索算法。在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果（可能）包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。

其实回溯法就是对隐式图的深度优先搜索算法。若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。

可用回溯法求解的问题p，通常要能表达为：对于已知的由n元组（x1，x2，…，xn）组成的一个状态空间e=，给定关于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，…，xn）都不会是问题p的解，因而就不必去搜索它们、检测它们。

回溯法正是针对这类问题，利用这类问题的上述性质而提出来的比枚举法效率更高的算法。

回溯法首先将问题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的一个解。

回溯法解决问题，一般有三个步骤：

1）针对所给问题，定义问题的解空间；

2）（2）确定易于搜索的解空间结构；

（3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜。

algorithm get_all_moves(i,j)

/get_**ail_peg then updates the variables move and move_set

/input :two nonnegative,integer i and j

/output:update the peg-board

fori?0 to max_peg_hole do

ifpegboard[i]?-1

for j?0 to num_of_rules do

move_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++

algorithm reset_pegboard(i)

/resets the pegboard to the original problem

/input :integer

/output:original pegboard

fori?0 to max_peg_hole do

swap pegboard[i] andorig_pegboard[i]

algorithm is_solve(i)

/judge problem is solved or not

/input :integer i

/output: 0 or 1

fori?0 to max_peg_hole do

ifpegboard[i]=1

count++

ifcount=1

return 1

算法课程设计

算法课程设计

算法课程设计

算法课程设计

其他用户还读了