基于回溯法的宝石排序问题研究.docx

基于回溯法的宝石排列问题研究安笙华(2014152148)摘要 本文采用回溯法对排列宝石问题：设有n种不同的颜色，同一种形状的n颗宝石分别具有这种不同的颜色。现有n种不同的形状的宝石共n2棵，欲将这n2颗宝石排列成n行n列的一个方阵使方阵中每一行每一列的宝石都有n种不同的形状和n种不同颜色。进行了分析，详细描述回溯法求解问题时算法的基本思想，并给出具体的算法设计和时间复杂度分析，最后对回溯法进行了总结。关键字 回溯法；排列宝石问题；递归1、引言 因为回溯法是一个既带有系统性又带有跳跃性的搜索算法，回溯法求问题的一个解时只要搜索到问题的一个解就可以结束。它以深度优先方式系统搜索问题的解，适合求解组合数较大的问题，因此，宝石排列问题也常用回溯法来解决。2、所用到的方法简介 确定包含问题的所有解的解空间树，在包含问题所有解的空间树中，按照深度优先的策略，从开始结点（根结点）出发搜索解空间树。这个开始节点称为活结点，同时也称为当前扩展结点。在当前扩展接点处，探索向纵深方向一直一个新结点。这个新结点成为新的活结点，并成为当前扩展接点。如果当前扩展接点不能再向纵深方向移动，则当前扩展结点就成为死结点。此时，应往回移动（回溯）到最近的活结点，并使这个活结点成为当前扩展结点。回溯法以这种方式递归的在解空间中搜索，直至找到所要求的解或解空间中已无活结点为止。为了提高回溯发的搜索效率，避免无效搜索，用回溯法搜索至解空间树的任一结点时，总是用剪枝函数先判断该结点是否满足问题的约束条件。如果满足进入该子树，继续按深度优先的策略进行搜索。否则，不去搜索以该结点为根的子树，而是逐层向其祖先结点回溯。在排列宝石问题中回溯法用剪枝函数剪去导致不可行的子树。3、问题分析 该问题可以看成n*n的矩阵中每一个元素与其同一行和同一列的元素都不相同。此时我们想到n后问题要求n*n格的棋盘上放置n个彼此不收攻击的皇后。所以我们的宝石排列问题就可以看做是n后问题的扩展，即有n种不同的皇后且每种皇后有n个不同大小。实验要求方阵中每一行和每一列的宝石都有n种不同形状和n种不同颜色，所以问题可以看成n*n的矩阵中每一个元素与其同一行和同一列的元素都不相同。构造问题的解空间树由于每行每列宝石的形状颜色各不相同，是问题的隐约束，可将其转化为显约束条件，在算法Backtrack()中，当rown时，算法搜索至叶结点，得到一个新的排列宝石问题的放置方案，就使当前以找到的可行方案数cnt增加1。当rownBackTrace(row+1,col);rown5、结论#include #define N 9int shapeNN;/记录方阵宝石的形状int colorNN;/记录方阵宝石的颜色bool stoneNN;/stoneij表示i形状的j颜色的石子是否已经用过int cnt = 0;int n = 0;/row行，col列bool isOK(int row,int col)if(stoneshaperowcolcolorrowcol) /如果石子没有被用过 /检查这一行【检查将宝石放到该位置是否满足与该行其他宝石不同形状，不同颜色的条件】 for(int i=1;icol;i+) if(shaperowi=shaperowcol | colorrowi=colorrowcol) return false; /检查这一列【检查将宝石放到该位置是否满足与该列其他宝石不同形状，不同颜色的条件】 for(int j=1;jn) /排完了最后一行 cnt+; return ;else if(coln) /一行排序完毕，排序下一行 BackTrace(row+1,1);else for(int i=col;i=n;i+) /排列形状 Swap(shaperowcol,shaperowi); for(int j=col;j=n;j+) /排列颜色 Swap(colorrowcol,colorrowj); if(isOK(row,col) /表示该宝石已经被用过了 stoneshaperowcolcolorrowcol = false; BackTrace(row,col+1); stoneshaperowcolcolorrowcol = true; Swap(colorrowcol,colorrowj); Swap(shaperowcol,shaperowi); int main()while(scanf(%d,&n)!=EOF) /初始化工作 cnt = 0; for(int i=1;i=n;i+) for(int j=1;j=n;j+) colorij = j; shapeij = j; stoneij = true; BackTrace(1,1); printf(%dn,cnt);return 0;5.1算法分析本文用回溯法和递归法很好的求解了排列宝石问题。回溯法有“通用解题法”之称，在搜索过程中动态地产生问题的解空间，系统地搜索问题的所有解。当搜索到解空间树的任一结点时，判断该结点是否包含问题的解。如果该结点肯定不包含，则“见壁回头”，跳过以该结点为根的子树的搜索，逐层向其祖先结点回溯，可大大缩减无效操作，提高搜索效率。因此，结合具体案例的实际设计合适的回溯点是应用回溯法的关键所在。而递归具有回溯的功能，用递归回溯可探索出问题的所有解。回溯法的时间复杂度因案例的具体实际而异。对于不同的实例，回溯法的计算时间有很大的差异。对于很多具有大n的求解实例，应用回溯法一般可在很短的时间内求得其解，可见回溯法不失为一种快速有效的算法。5.2时间复杂度分析 对于排列宝石问题，计算可行性约束需要的时间p(n),在最优情况下需比较2n次，p(n)=2n。时间复杂度为o(2n)在最坏的情况下有n！个结点需要计算可行性约束条件，故时间复杂o(p(n)n!)回溯法的效率很大程度上依赖于以下因素：（