算法详解之回溯法具体实现
本文导语: 理论辅助: 回溯算法也叫试探法,它是一种系统地搜索问题的解的方法。回溯算法的基本思想是:从一条路往前走,能进则进,不能进则退回来,换一条路再试。用回溯算法解决问题的一般步骤为: 1、定义一个解空间,它包...
理论辅助:
回溯算法也叫试探法,它是一种系统地搜索问题的解的方法。回溯算法的基本思想是:从一条路往前走,能进则进,不能进则退回来,换一条路再试。用回溯算法解决问题的一般步骤为:
1、定义一个解空间,它包含问题的解。
2、利用适于搜索的方法组织解空间。
3、利用深度优先法搜索解空间。
4、利用限界函数避免移动到不可能产生解的子空间。
问题的解空间通常是在搜索问题的解的过程中动态产生的,这是回溯算法的一个重要特性。
还是那个基调,不喜欢纯理论的东西,喜欢使用例子来讲诉理论,在算法系列总结:动态规划(解公司外包成本问题) 的那一节里面 我们举得是经典的0-1背包问题,在回溯算法里面也有一些很经典的问题,当然,动态规划的0-1背包问题其实也可以使用回溯算法来解。在诸如此类似的求最优解的问题中,大部分其实都可以用回溯法来解决,可以认为回溯算法一个”通用解题法“,这是由他试探性的行为决定的,就好比求一个最优解,我可能没有很好的概念知道怎么做会更快的求出这个最优解,但是我可以尝试所有的方法,先试探性的尝试每一个组合,看看到底通不通,如果不通,则折回去,由最近的一个节点继续向前尝试其他的组合,如此反复。这样所有解都出来了,在做一下比较,能求不出最优解吗?
例子先行,现在我们来看看经典的N后问题
问题描述:在n*n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规矩,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在n*n格的棋盘上方置n个皇后,任何2个皇后不放在同一行或同一列或同一斜线上。我们需要求的是可放置的总数。
基本思路: 用n元组x[1;n]表示n后问题的解。其中,x[i]表示皇后i放置在棋盘的第i行的第x[i]列。由于不容许将2个皇后放在同一列上,所以解向量中的x[i]互不相同。2个皇后不能放在同一斜线上是问题的隐约束。对于一般的n后问题,这一隐约束条件可以化成显约束的形式。如果将n*n 格的棋盘看做二维方阵,其行号从上到下,列号从左到右依次编号为1,2,...n。从棋盘左上角到右下角的主对角线及其平行线(即斜率为-1的各斜线)上,2个下标值的差(行号-列号)值相等。同理,斜率为+1的每条斜线上,2个下标值的和(行号+列号)值相等。因此,若2个皇后放置的位置分别是(i,j)和(k,l),且 i-j = k -l 或 i+j = k+l,则说明这2个皇后处于同一斜线上。以上2个方程分别等价于i-k = j-l 和 i-k =l-j。由此可知,只要|i-k|=|l-j|成立,就表明2个皇后位于同一条斜线上。
1、从空棋盘起,逐行放置棋子。
2、每在一个布局中放下一个棋子,即推演到一个新的布局。
3、如果当前行上没有可合法放置棋子的位置,则回溯到上一行,重新布放上一行的棋子。
代码:
#include
#include
#include
static int n,x[1000];
static long sum;
int Place(int k)
{
for(int j=1;j n) sum++;
else
for(int i=1; i = 0; i--)
{
if (map[row][i] == 'o') return 0;
if (map[row][i] == 'x') break;
}
return 1;
}
void solve(int k,int tot)
{
int x,y;
if(k==n*n)
{
if(tot>best)
{
best=tot; return;
}
}
else
{
x=k/n;
y=k%n;
if((map[x][y]=='.') && (canput(x,y) ) )
{
map[x][y]='o';
solve(k+1,tot+1);
map[x][y]='.';
}
solve(k+1,tot);
}
}
int main()
{
int i,j;
scanf("%d",&n);
while(n>0)
{
for(i=0;i< n;i++)
for(j=0;j< n;j++)
scanf("%1s",&map[i][j]);
best=0;
solve(0,0);
printf("%dn",best);
n=0;
scanf("%d",&n);
}
return 0;
}
对上面的代码做一下点解释,canput是做检验的,检验放在某个地点到底行不行得通,solve才是真正进行递归回溯的函数。。