回溯算法（试探法）

骑猪看日落 2022-09-06 15:27 134阅读 0赞

## 算法思路 ##

*  基本思想：
 *  为了求得问题的解，先选择某一种可能情况进行试探，在试探过程中，一旦发现原来选择的假设情况是错误的，就退回一步重新选择，继续向另一个方向试探，如此反复进行，直至得到解或证明无解。

--------------------

*  编程经验
 *  对于常见的迷宫问题，就可使用试探法来求解，具体过程为：进入迷宫后，先任意选择一个方向，一步步向前试探前进，如果遇到死胡同，说明前进方向已无路可走，这时，首先看其他方向是否还有路可走；如果有路可走，则沿该方向再向前试探。按此原则不断试探，回溯，再搜索，直到找到新的出路或从原路返回入口处无解可至。

--------------------

## 结构 ##

对解集合中的各解进行试探
     { 
            if（满足条件）
            { 
                保存结果
                if（完成集合中所有解的试探）
                    输出解
                else
                    重复本过程进行下一步骤的试探（递归调用本函数）
                }else
                 恢复至上一步保存结果之前的状态，进行另一步的试探（递归调用本函数）
     }

--------------------

## 实例 ##

*  生成彩票号码组合  
    【使用嵌套循环】

#include <bits/stdc++.h>
    using namespace std;
    int main(){ 
    	int i[7],j;
    	for(i[0]=1;i[0]<=29;i[0]++)
    	    for(i[1]=1;i[1]<=29;i[1]++){ 
    		if(i[0]==i[1])
    		    continue;
    		for(i[2]=1;i[2]<=29;i[2]++){ 
    			if(i[2]==i[0]||i[1]==i[2])
    			   continue;
    			for(i[3]=1;i[3]<=29;i[3]++){ 
    				if(i[3]==i[1]||i[3]==i[0]||i[3]==i[2])
    				    continue;
    				for(i[4]=1;i[4]<=29;i[4]++){ 
    					if(i[4]==i[3]||i[4]==i[2]||i[4]==i[1]||i[4]==i[0])
    					   continue;
    					for(i[5]=1;i[5]<=29;i[5]++){ 
    						if(i[5]==i[4]||i[5]==i[3]||i[5]==i[2]||i[5]==i[1]||i[5]==i[0])
    						    continue;
    						for(i[6]=1;i[6]<=29;i[6]++){ 
    							if(i[6]==i[5]||i[6]==i[4]||i[6]==i[3]||i[6]==i[2]||i[6]==i[1]||i[6]==i[0])
    							     continue;
    							for(j=0;j<7;j++)
    							    printf("%3d",i[j]);
    							cout<<endl;
    							system("pause");
    						}
    					}
    				}
    			}
    		}
    	}
    }

--------------------

【试探法】

#include <bits/stdc++.h>
    #define maxn 7 //设置每一注彩票的位数 
    #define NUM 29 //设置组成彩票的数字 
    using namespace std;
    int num[NUM];
    int lottery[maxn];
    void combine(int n,int m){ 
    	int i,j;
    	for(i=n;i>=m;i--){ 
    		lottery[m-1]=num[i-1];     //保存一位数字 
    		if(m>1)
    		    combine(i-1,m-1);
    		else{                       //若 m = 1 ，输出一注号码 
    			for(j=maxn-1;j>=0;j--)
    			     cout<<setw(3)<<lottery[j];
    			    system("pause");
    			    cout<<endl;
    		}
    	}
    }
    int main(){ 
    	int i,j;
    	for(i=0;i<NUM;i++)       //设置彩票各位数字 
    	    num[i]=i+1;
    	memset(lottery,0,sizeof(lottery));
    	combine(NUM,maxn);
    	getchar();
    	return 0;
    }

--------------------

*  递归函数
 *  用来生成彩票组合。
 *  若还未生成足够的位数，则递归调用生成下一位号码。当生成完指定位数的号码后，输出该注彩票号码。