回溯算法的经典例题。大一的时候就有耳闻,却一直没有实现,今天终于有机会把它写出来,小有成就感啊。
这里算法采用的是深度优先搜索,从第一个节点开始,按行优先的原则逐个扫描每个点,如果该点合法,可以选择放一个queen也可以选择不放,当该点不合法时,就跳过该点接着判断下一个点。
有人把回溯算法说成是“万能算法”,这么说的原因是回溯实际上就是枚举,它的最坏情况始终是指数或阶乘级的。对它的优化主要体现在约“约束函数”和“限界函数”这两个剪枝函数上。
我曾经尝试用回溯写过背包,结果是无情的超时,与动态规划的O(NV)来说,回溯O(2^N)的时间复杂度真是不敢恭维。因此对回溯有些“偏见”。但是前面说过了,回溯的剪枝是很重要的,剪枝函数做的好可以在实际中大大降低回溯的时间复杂度。
下面是我八皇后问题的代码:
#include<stdio.h>//eight queens
#include<string.h>
#include<stdlib.h>
#define LEN 100
int mp[LEN][LEN];
int len;
int nq;
long long count;
long long countall;
int canput(int x, int y)
{
int i, j;
if(mp[x][y] == 1)
return 0;
for(i = 0; i < len; i++)
{
if(mp[x][i] == 1 || mp[i][y] == 1)
return 0;
}
for(i = x - 1, j = y - 1; i >= 0 && j >= 0; i--, j--)
if(mp[i][j] == 1)
return 0;
for(i = x + 1, j = y + 1; i < len && j < len; i++, j++)
if(mp[i][j] == 1)
return 0;
for(i = x - 1, j = y + 1; i >= 0 && j < len; i--, j++)
if(mp[i][j] == 1)
return 0;
for(i = x + 1, j = y - 1; i < len && j >= 0; i++, j--)
if(mp[i][j] == 1)
return 0;
return 1;
}
void DFS(int m)
{
countall++;
int i, j;
if(m < len * len)
{
int x = m / len;
int y = m % len;
if(canput(x, y) == 1)//can put queen in this point
{
nq++;
mp[x][y] = 1;
DFS(m + 1);
mp[x][y] = 0;
nq--;
DFS(m + 1);
}
else//can not put queen in this point
DFS(m + 1);
}
else if(nq == len)
{
count++;
printf("out end map[][]:\n");
for(i = 0; i < len; i++)
{
for(j = 0; j < len; j++)
printf("%d ", mp[i][j]);
putchar(10);
}
}
}
int main()
{
int i, j;
len = 8;
for(i = 0; i < len; i++)
for(j = 0; j < len; j++)
mp[i][j] = 0;
count = 0;
nq = 0;
countall = 0;
DFS(0);
printf("count = %ld\n", count);
//printf("countall = %ld\n", countall);
system("pause");
return 0;
}
看了书上的代码才发现自己写的效率不高。上面我写的是从棋盘的第一个位置开始,依次判每一个位置。事实上,只要这一行有皇后,该行的其余地方就不能放了,我之前的做法无疑增加了分支个数。还有,我的限界函数写的太没技术含量,看完书上利用斜率写限界函数时,真是感觉很惭愧啊。
以下是书上的经典算法,可与上面的算法对比一下,效率差距很明显。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define LEN 20
#define LENQ 8
int x[LEN];
int sum;
int Mabs(int a)
{
if(a < 0)
return -a;
return a;
}
int Place(int k)
{
for(int j = 1; j < k; j++)
if(Mabs(k - j) == Mabs(x[j] - x[k]) || x[j] == x[k])
return 0;
return 1;
}
void Queen(int t)
{
if(t > LENQ)
{
sum++;
for(int i = 1; i <= LENQ; i++)
printf("%d ", x[i]);
putchar(10);
}
else
for(int i = 1; i <= LENQ; i++)
{
x[t] = i;
if(Place(t))
Queen(t + 1);
}
}
int main()
{
int i, j;
sum = 0;
Queen(1);
printf("sum = %d\n", sum);
system("pause");
}
posted on 2012-05-11 20:24
小鼠标 阅读(399)
评论(0) 编辑 收藏 引用 所属分类:
回溯