回溯是搜索算法中的一种控制策略。它的基本思想是：为了求得问题的解，先选择某一种可能情况向前探索，在探索过程中，一旦发现原来的选择是错误的，就退回一步重新选择，继续向前探索，如此反复进行，直至得到解或证明无解。
如迷宫问题：进入迷宫后，先随意选择一个前进方向，一步步向前试探前进,如果碰到死胡同，说明前进方向已无路可走，这时，首先看其它方向是否还有路可走，如果有路可走，则沿该方向再向前试探；如果已无路可走，则返回一步，再看其它方向是否还有路可走；如果有路可走，则沿该方向再向前试探。按此原则不断搜索回溯再搜索，直到找到新的出路或从原路返回入口处无解为止。
1. //递归回溯算法框架 一 2. void search(int k) 3. { 4. for(i=1;i<=算符种数;i++) 5. if(满足条件) 6. { 7. 保存结果; 8. if(到目的地)输出解; 9. else search(k+1); 10. 恢复 保存结果之前的状态{回溯一步;} 11. } 12. } 13. //递归回溯算法框架 二 14. void search(int k) 15. { 16. if(到目的地)输出解; 17. else 18. for(i=1;i<=算符种数;i++) 19. if(满足条件) 20. { 21. 保存结果; 22. search(k+1); 23. 恢复 保存结果之前的状态{回溯一步;} 24. } 25. }
【例1】素数环:从1到20这20个数摆成一个环，要求相邻的两个数的和是一个素数。
【算法分析】 非常明显，这是一道回溯的题目。从1开始，每个空位有20种可能，只要填进去的数合法：与前面的数不相同；与左边相邻的数的和是一个素数。第20个数还要判断和第1个数的和是否素数。
【算法流程】 1、数据初始化；2、递归填数：判断第i个数填入是否合法； A、如果合法：填数；判断是否到达目标（20个已填完）：是，打印结果；不是，递归填下一个； B、如果不合法：选择下一种可能；
1~20 组合太多 这里改成了1~6：
1. #include<iostream> 2. #include<cstdio> 3. #include<cmath> 4. using namespace std; 5. int a[7]={0}; 6. int b[7]={0}; 7. int t=0; 8. bool check(int x,int y)//判断素数 9. { 10. int z=x+y; 11. int k=2; 12. while((z%k!=0)&&(k<=sqrt(z))) k++; 13. if(k>sqrt(z)) return true; 14. else return false; 15. } 16. void print()//输出及统计 17. { 18. t++; 19. cout<<t<<"-> "; 20. for(int j=1;j<6;j++) cout<<a[j]<<" "; 21. cout<<a[6]<<endl; 22. } 23. void search(int n) 24. { 25. for(int i=1;i<=6;i++)//由1-6 个可选数 26. //与前一个数构成素数 且未使用过 27. if(check(a[n-1],i)&&(b[i]==0)) 28. { 29. a[n]=i; 30. b[i]=1; 31. //是最后一个数 且与第一个数构成素数 32. if(n==6&&check(a[6],a[1])) print(); 33. search(n+1);//调用下一个 34. b[i]=0; //取消使用标记 35. } 36. } 37. int main() 38. { 39. search(1); 40. cout<<t; 41. return 0; 42. }
【例2】设有n个整数的集合｛1,2,…,n｝，从中取出任意r个数进行排列（r<n），试列出所有的排列。
1. #include<iostream> 2. #include<cstdio> 3. #include<cmath> 4. using namespace std; 5. int n,r,t=0; 6. int a[101]={0},b[101]={0}; 7. void search(int m) 8. { 9. for(int i=1;i<=n;i++){ 10. if(b[i]==0){ 11. b[i]=1; 12. a[m]=i; 13. if(m==r){ 14. for(int j=1;j<r;j++) cout<<a[j]<<" "; 15. cout<<a[r]<<endl; 16. t++; 17. } 18. search(m+1); 19. b[i]=0; 20. } 21. } 22. } 23. int main() 24. { 25. cin>>n>>r; 26. search(1); 27. cout<<t<<endl; 28. return 0; 29. }
【例3】任何一个大于1的自然数n，总可以拆分成若干个小于n的自然数之和。
当n=7共14种拆分方法：
7=1+1+1+1+1+1+1
7=1+1+1+1+1+2
7=1+1+1+1+3
7=1+1+1+2+2
7=1+1+1+4
7=1+1+2+3
7=1+1+5
7=1+2+2+2
7=1+2+4
7=1+3+3
7=1+6
7=2+2+3
7=2+5
7=3+4
total=14
1. #include<iostream> 2. #include<cstdio> 3. #include<cmath> 4. using namespace std; 5. int s[101]={1}; 6. int n,sum=0; 7. void print(int m) 8. { 9. cout<<n<<"="; 10. for(int j=1;j<m;j++) cout<<s[j]<<"+"; 11. cout<<s[m]<<endl; 12. sum++; 13. } 14. void search(int a,int m) 15. { 16. int i; 17. for(i=s[m-1];i<=a;i++){ 18. if(i<n){ 19. s[m]=i; 20. a-=i; 21. if(a==0) print(m); 22. else search(a,m+1); 23. a+=i; 24. } 25. } 26. } 27. int main() 28. { 29. cin>>n; 30. search(n,1); 31. cout<<"total="<<sum; 32. return 0; 33. }
