回溯法的应用范围:只要能把待求解的问题分成不太多的步骤,每个步骤又只有不太多的选择就可以考虑使用回溯法。
若用回溯法求问题的所有解时,要回溯到根,且根结点的所有可行的子树都要已被搜索遍才结束。 而若使用回溯法求任一个解时,只要搜索到问题的一个解就可以结束。
回溯法将问题的候选解按照某一顺序逐一枚举和检验。当发现当前候选解不可能是解时,就选择下一个候选解,若当前候选解符合要求,且还未达到求解的规模,则继续扩展当前候
选解的规模,如果候选解已经满足了所有要求,并且也达到了问题的规模,那么该候选解就是问题的一个解。
例、在9(3*3)的方格内填入1到N(N>=10)内的某9个数字,每个方格填入一个数字,使方格内所有相邻的两个数的和为质数,试求出满足要求的所有填法。
伪代码:
1 int m=0; //已经填入m个数
2 bool ok=true;//ture表示已经填入的前m个数都符合要求
3 int n=8; //填入最后一个数字的下标
4 do
5 {
6 if(ok)
7 {
8 if(m==n)
9 {
10 print();//输出这个解
11 change();//调整最后一个值,找下一个解
12 }
13 else
14 {
15 extend();//往下一个空的方格中填入数字
16 }
17 }
18 else
19 {
20 change();//调整最近填入的一个值
21 }
22 ok=检查前m个数是否都符合要求;
23 }while(m>=0)//由于是求解所有解,所以必须回溯到根的所有情况才算结束
程序如下:
1 #include<iostream>
2 #include<math.h>
3 using namespace std;
4 const int N=12;
5 int a[10];//记录符合条件的数
6 bool b[N+1];//记录某个数是否已经被用过true,被用过,false,没被用过
7 int checkmatrix[][3]={{-1},{0,-1},{1,-1},
8 {0,-1},{3,1,-1},{4,2,-1},
9 {3,-1},{6,4,-1},{7,5,-1}};//checkmatirx用来验证相邻的两个数的和是否为指数用的,-1是人为添加的截止符号
10 int m;//已经符合条件的个数
11 void print(int * a)
12 {
13 for(int i=0;i<3;i++)
14 {
15 for(int j=0;j<3;j++)
16 {
17 cout<<a[i+j*3]<<" ";
18 }
19 cout<<endl;
20 }
21 }
22 bool isprime(int m)
23 {
24 if(1==m)
25 {
26 return false;
27 }
28 if(2==m)
29 {
30 return true;
31 }
32 int n=sqrt((float)m);
33 for(int i=2;i<=n;i++)
34 {
35 if(m%i==0)
36 {
37 return false;
38 }
39 }
40 return true;
41 }
42 //返回从start开始的第一个没被用过的数
43 int select(int start)
44 {
45 for(int i=start;i<=N;i++)
46 {
47 if(b[i]==false)
48 {
49 return i;
50 }
51 }
52 return 0;//如果全都被使用过了就返回0
53 }
54 int extend(int m)
55 {
56 a[++m]=select(1);
57 b[a[m]]=true;
58 return m;
59 }
60 int change(int m)
61 {
62 int pos;
63 while(m>=0 && (pos=select(a[m]+1))==0)
64 {
65 b[a[m--]]=false;
66 }
67 if(m<0)
68 {
69 return -1;
70 }
71 else
72 {
73 b[a[m]]=false;
74 a[m]=pos;
75 b[a[m]]=true;
76 }
77 return m;
78 }
79 bool check(int m)
80 {
81 int j;
82 if(m<0)
83 {
84 return false;
85 }
86 int k=m;
87 while(k>=0)
88 {
89 for(int i=0;(j=checkmatrix[k][i])>=0;i++)
90 {
91 if(!isprime(a[k]+j))
92 {
93 return false;
94 }
95 }
96 k--;
97 }
98
99 return true;
100 }
101 int main()
102 {
103 //先全都初始化为未使用过
104 for(int i=0;i<N+1;i++)
105 {
106 b[i]=false;
107 }
108 m=0;
109 a[m]=1;
110 b[a[m]]=true;
111 bool ok=true;//前m个数都满足条件的话ok为true否则为false
112 do
113 {
114 if(ok)
115 {
116 if(8==m)
117 {
118 print(a);
119 //调整
120 m=change(m);
121
122 }
123 else
124 {
125 //扩展
126 m=extend(m);
127 }
128 }
129 else
130 {
131 //调整
132 m=change(m);
133 }
134 //检查前m个数是否都满足条件
135 ok=check(m);
136 }while(m>=0);
137
138 return 0;
139 }
如果将题目改成找出一种填法,则不需要回溯到根,而是找到一个解就可以结束了 伪代码如下:
1 int m=0;
2 bool ok=true;
3 int n=8;
4 do
5 {
6 if(ok)
7 {
8 extend()//扩展解
9 }
10 else
11 {
12 change();//调整最近填入的数字
13 }
14 ok=检查填入的m个数的合理性;
15 }while((m!=n||!ok)&&m!=0)
16 if(m==n)
17 {
18 print();//输出解
19 }
20 else
21 {
22 无解;
23 }