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

《基于回溯法的宝石排序问题研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、基于回溯法的宝石排列问题研究安笙华(2014152148)  摘要本文采用回溯法对排列宝石问题：设有n种不同的颜色，同一种形状的n颗宝石分别具有这种不同的颜色。现有n种不同的形状的宝石共n2棵，欲将这n2颗宝石排列成n行n列的一个方阵使方阵中每一行每一列的宝石都有n种不同的形状和n种不同颜色。进行了分析，详细描述回溯法求解问题时算法的基本思想，并给出具体的算法设计和时间复杂度分析，最后对回溯法进行了总结。关键字 回溯法；排列宝石问题；递归 1、引言因为回溯法是一个既带有系统性又带有跳跃性的搜索算法，回溯法求问题的一个解时只要搜索到问题的一个解就可以结束。它以深度优先方式系统搜索问题

2、的解，适合求解组合数较大的问题，因此，宝石排列问题也常用回溯法来解决。2、所用到的方法简介确定包含问题的所有解的解空间树，在包含问题所有解的空间树中，按照深度优先的策略，从开始结点（根结点）出发搜索解空间树。这个开始节点称为活结点，同时也称为当前扩展结点。在当前扩展接点处，探索向纵深方向一直一个新结点。这个新结点成为新的活结点，并成为当前扩展接点。如果当前扩展接点不能再向纵深方向移动，则当前扩展结点就成为死结点。此时，应往回移动（回溯）到最近的活结点，并使这个活结点成为当前扩展结点。回溯法以这种方式递归的在解空间中搜索，直至找到所要求的解或解空间中已无活结点为止。为了提高回溯发的搜

3、索效率，避免无效搜索，用回溯法搜索至解空间树的任一结点时，总是用剪枝函数先判断该结点是否满足问题的约束条件。如果满足进入该子树，继续按深度优先的策略进行搜索。否则，不去搜索以该结点为根的子树，而是逐层向其祖先结点回溯。在排列宝石问题中回溯法用剪枝函数剪去导致不可行的子树。3、问题分析该问题可以看成n*n的矩阵中每一个元素与其同一行和同一列的元素都不相同。此时我们想到n后问题要求n*n格的棋盘上放置n个彼此不收攻击的皇后。所以我们的宝石排列问题就可以看做是n后问题的扩展，即有n种不同的皇后且每种皇后有n个不同大小。 实验要求方阵中每一行和每一列的宝石都有n种不同形状和n种不同颜色，所

4、以问题可以看成n*n的矩阵中每一个元素与其同一行和同一列的元素都不相同。构造问题的解空间树由于每行每列宝石的形状颜色各不相同，是问题的隐约束，可将其转化为显约束条件，在算法Backtrack( )中，当row>n时，算法搜索至叶结点，得到一个新的排列宝石问题的放置方案，就使当前以找到的可行方案数cnt增加1。当row

5、种不同颜色。4、算法BackTrace(row,col);if(isOK(row,col)){stone[shape[row][col]][color[row][col]]=false;BackTrace(row,col+1);stone[shape[row][col]][color[row][col]]=true;}BackTrace(row,col+1);àcol>nBackTrace(row+1,col);àrow>n5、结论#include#defineN9intshape[N][N];//记录方阵宝石的形状intcolor[N][N];//记录方阵宝石的

6、颜色boolstone[N][N];//stone[i][j]表示i形状的j颜色的石子是否已经用过intcnt=0;intn=0;//row行，col列boolisOK(introw,intcol){if(stone[shape[row][col]][color[row][col]]){//如果石子没有被用过//检查这一行【检查将宝石放到该位置是否满足与该行其他宝石不同形状，不同颜色的条件】for(inti=1;i

7、

8、color[row][i]==color[row][col]){returnfa

9、lse;}}//检查这一列【检查将宝石放到该位置是否满足与该列其他宝石不同形状，不同颜色的条件】for(intj=1;j

10、

11、color[j][col]==color[row][col]){returnfalse;}}returntrue;}else{//如果石子已经被用过returnfalse;}}voidSwap(int&x,int&y){inttmp=x;x=y;y=tmp;}/