回溯算法（一点点）

148 阅读 0 评论 98 点赞

我是靠谱客的博主落后黑裤，这篇文章主要介绍回溯算法（一点点），现在分享给大家，希望可以做个参考。

解决回溯问题的方法：
（1）针对所给问题，定义问题的解空间；

（2）确定易于搜索的解空间结构；

（3）以深度优先的方式搜索解空间；

（4）回溯法搜遍整个解空间，最后得到最优解。

N皇后问题

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<math.h>
 int n,m=1;
 int a[1024]={0};
 int check(int a[],int n) 
 {  
    for(int i=1;i<n;i++)  
    {  
        if(abs(a[i]-a[n])==abs(i-n) || a[i]==a[n])//见下面注释  
            return 0;  
    }  
    return 1;  
}
 int fun(int i){
 	int j,k;
 	for(j=1;j<=n;j++)
 	{
 		a[i]=j;
		if(check(a,i))
		{
			if(i<n)
				fun(i+1);
			else
			{
				printf("第%d个排列方法：n",m);
				
				for(k=1;k<=n;k++)
				{
					printf("第%d个皇后的位置：%dn",k,a[k]);
				}
				printf("n");
				m++; 
			}
				
		}	
	}
 }
 
 
 int main(){
 printf("请输入皇后数：n");
 scanf("%d",&n);
 fun(1);
}