基于回溯法宝石排序问题研究.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( )中，当row>n时，算法搜索至叶结点，得到一个新的排列宝石问题的放置方案，就使当前以找到的可行方案数cnt增加1。
当row<n时，当前扩展结点是解空间中的内部结点。当前扩展结点的每一个儿子结点，用isOK（ ）函数检查宝石是否可放置，并以深度优先的方式递归的对可行子树搜索，并剪去不可行的子树。 剪枝约束条件：n2颗宝石排列成n行n列的一个方阵使方阵中每一行每一列的宝石都有n种不同的形状与n种不同颜色。
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>n
BackTrace(row+1,col);àrow>n

5、结论
#include <stdio.h>
#define N 9
int shape[N][N];//记录方阵宝石的形状
int color[N][N];//记录方阵宝石的颜色
bool stone[N][N];//stone[i][j]表示i形状的j颜色的石子是否已经用过
int cnt = 0;
int n = 0;
//row行，col列
bool isOK(int row,int col)
{
if(stone[shape[row][col]][color[row][col]])
{
//如果石子没有被用过
//检查这一行
【检查将宝石放到该位置是否满足与该行其他宝石不同形状，不同颜色的条件】
for(int i=1;i<col;i++)
{
if(shape[row][i]==shape[row][col] || color[row][i]==color[row][col])
{
return false;
}
}
//检查这一列
【检查将宝石放到该位置是否满足与该列其他宝石不同形状，不同颜色的条件】
for(int j=1;j<row;j++)
{
if(shape[j][col]==shape[row][col] || color[j][col]==color[row][col]) {
return false;
}
}
return true;
}
else
{
//如果石子已经被用过
return false;
}
}
void Swap(int &x,int &y)
{
int tmp = x;
x = y;
y = tmp;
}
//从上到下，从左到右回溯，row代表行，col代表列
void BackTrace(int row,int col)
{
if(row>n)
{
//排完了最后一行
cnt++;
return ;
}
else if(col>n)
{
//一行排序完毕，排序下一行
BackTrace(row+1,1);
}
else
{
for(int i=col;i<=n;i++)
{
//排列形状
Swap(shape[row][col],shape[row][i]);
for(int j=col;j<=n;j++)
{
//排列颜色
Swap(color[row][col],color[row][j]);
if(isOK(row,col))
{
//表示该宝石已经被用过了
stone[shape[row][col]][color[row][col]] = false;
BackTrace(row,col+1);
stone[shape[row][col]][color[row][col]] = true;
}
Swap(color[row][col],color[row][j]);
}
Swap(shape[row][col],shape[row][i]);
}
}

}

int main()
{
while(scanf("%d",&n)!=EOF)
{
//初始化工作
cnt = 0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
color[i][j] = j;
shape[i][j] = j;
stone[i][j] = true;
}
}
BackTrace(1,1);
printf("%d\n",cnt);
}
return 0;
}

5.1算法分析
本文用回溯法与递归法很好的求解了排列宝石问题。回溯法有“通用解题法”之称，在搜索过程中动态地产生问题的解空间，系统地搜索问题的所有解。当搜索到解空间树的任一结点时，判断该结点是否包含问题的解。如果该结点肯定不包含，则“见壁回头”，跳过以该结点为根的子树的搜索，逐层向其祖先结点回溯，可大大缩减无效操作，提高搜索效率。因此，结合具体案例的实际设计合适的回溯点是应用回溯法的关键所在。而递归具有回溯的功能，用递归回溯可探索出问题的所有解。回溯法的时间复杂度因案例的具体实际而异。对于不同的实例，回溯法的计算时间有很大的差异。对于很多具有大n的求解实例，应用回溯法一般可在很短的时间内求得其解，可见回溯法不失为一种快速有效的算法。
5.2时间复杂度分析
对于排列宝石问题，计算可行性约束需要的时间p(n),在最优情况下需比较2n次，p(n)=2n。时间复杂度为o(2n)在最坏的情况下有n！个结点需要计算可行性约束条件，故时间复杂o(p(n)n!) 回溯法的效率很大程度上依赖于以下因素： 
（1）满足显性约束的个数 
（2）计算约束函数的时间 
（3）好的约束函数能显著的减少所生成的结点数这样的约束函数往往计算量较大因此选择约束函数式通常选择生成节点数与约束函数计算量之间的折中 。
系别：计算机系
班级：201405
姓名：安笙华
学号：2014152148