2017-10-07 21:33:16
writer；pprp
经典的回溯算法
#include<cstring>
#include<iostream>
using namespace std;
int vis[3][15],tot;
void search(int cur)
{
int i,j;
if(cur==8) tot++;
else
{
for(i=0;i<8;i++)
{
if(!vis[0][i]&&!vis[1][cur-i+8]&&!vis[2][cur+i])
{
vis[0][i]=1;
vis[1][cur-i+8]=1;
vis[2][cur+i]=1;
search(cur+1);
//改回辅助的全局变量
vis[0][i]=0;
vis[1][cur-i+8]=0;
vis[2][cur+i]=0;
}
}
}
}
int main()
{
search(0);
cout<<tot<<endl;
}
第二种
/*
@theme:搜索入门：回溯算法 - 八皇后问题
@writer：pprp
@declare:
*/
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
int num;
int sum;
int *x;
bool place(int k)
{
for(int i = 1 ; i < k ; i++)
if(abs(x[k]-x[i]) == abs(k-i)||x[i] == x[k])
return false;
return true;
}
void backtrack(int t)
{
if(t > num)
{
sum++;
for(int i = 1; i <= num ; i++)
{
cout <<‘(‘<< i <<‘,‘ << x[i] << ‘)‘;
}
cout << endl;
}
else
for(int i = 1; i <= num ; i++)
{
x[t] = i;
if(place(t))
backtrack(t+1);
}
}
int main()
{
num = 8;
sum = 0;
x = new int[num+1];
for(int i = 0; i <= num ; i++)
x[i] = 0;
backtrack(1);
cout << sum << endl;
delete []x;
return 0;
}
回溯算法的构架
非递归：
1: int a[n],i;
2: 初始化数组a[];
3: i = 1;
4: while (i>0(有路可走) and (未达到目标)) // 还未回溯到头
5: {
6: if(i > n) // 搜索到叶结点
7: {
8: 搜索到一个解，输出；
9: }
10: else // 处理第i个元素
11: {
12: a[i]第一个可能的值；
13: while(a[i]在不满足约束条件且在搜索空间内)
14: {
15: a[i]下一个可能的值；
16: }
17: if(a[i]在搜索空间内)
18: {
19: 标识占用的资源；
20: i = i+1; // 扩展下一个结点
21: }
22: else
23: {
24: 清理所占的状态空间； // 回溯
25: i = i –1;
26: }
27: }
递归：
1：int a[n];
2: try(int i)
3: {
4: if(i>n)
5: 输出结果;
6: else
7: {
8: for(j = 下界; j <= 上界; j=j+1) // 枚举i所有可能的路径
9: {
10: if(fun(j)) // 满足限界函数和约束条件
11: {
12: a[i] = j;
13: ... // 其他操作
14: try(i+1);
15: 回溯前的清理工作（如a[i]置空值等）;
16: }
17: }
18: }
19: }
原文：http://www.cnblogs.com/pprp/p/7635941.html