回溯算法：
回溯算法实际上是一个类似枚举的搜索尝试方法，它的思想是在搜索尝试中寻找问题的解，当发现不满足求解条件时，就“回溯”返回，尝试别的路径。之前介绍的基础算法中的贪婪算法，动态规划等都具有“无后效性”，也就是在分段处理问题时，某状态一旦确定，将不再改变。而多数问题很难找到"无后效性”的阶段划分和相应决策，而是通过深入搜索尝试和回溯操作完成的。八皇后问题：8*8的国际象棋棋盘中放八个皇后，是任意两个皇后不能互相吃掉。规则：皇后能吃掉同一行，同一列，同一对角线的任意棋子。
模型建立：不妨设八个皇后分别在第i行，那么解空间就是一个八个皇后所在列的序号，为n元一维向量（x1，x2，x3，x4，x5，x6，x7，x8），搜索空间是1<=Xi<=8,共8^8个状态。但正如之前所说，回溯法采用“走不通就掉头”，故实际算法不必搜索那么多的状态，例如，（1，1，x3，x4，x5，x6，x7，x8）的状态共有8^6个，由于1,2皇后不能在同一列，那么这8^6个状态是不会搜索的。
算法设计1：加约束条件的枚举算法
约束条件有三个：不在同一列（Xi不等于Xj）不在同一主对角线（Xi-i不等于Xj-j）不在同以负对角线（Xi+i不等于Xj+j）后两项可合并为fabs（Xi-Xj）不等于fabs(i-j)那么直接贴代码了（此处代码较多，故以4皇后为例）#include#include #include using namespace std;int check(int a[],int n);int main(){ int a[9],i; for(a[1]=1;a[1]<=4;a[1]++) { for(a[2]=1;a[2]<=4;a[2]++) { if(check(a,2)==0)continue; for(a[3]=1;a[3]<=4;a[3]++) { if((check(a,3)==0))continue; for(a[4]=1;a[4]<=4;a[4]++) { if(check(a,4)==0)continue; else { for(i=1;i<=4;i++) cout << a[i]<< ' '; cout << endl;} } } } } return 0;}int check(int a[],int n){ int i; for(i=1;i<=n-1;i++) { if(fabs((double)(a[i]-a[n]))==fabs((double)(i-n))||a[i]==a[n])return 0; } return 1;}
运行结果：
2 4 1 33 1 4 2
八皇后问题模版（非递归回溯算法）
#include#include using namespace std;int a[20],n,cnt=0;void backdate(int n);int check(int k);void output(int);int main(){ cin >> n; backdate(n); return 0;}void backdate(int n){ int k; a[1]=0; k=1; while(k>0) { a[k]++; while( (a[k]<=n) && (check(k)==0) ) //为第k个皇后搜索位置 { a[k]++; } if(a[k]<=n) { if(k==n) //找到一组解 output(n); else { k=k+1; //前k个皇后找到位置，继续为第k+1个皇后找到位置 a[k]=0; //注意下一个皇后一定要从头开始搜索 } } else k=k-1; //回溯（务必留意，此算法精华尽在于此！） }}int check(int k){ int i; for(i=1;i<=k-1;i++) { if(fabs((double)(a[i]-a[k]))==fabs((double)(i-k))||a[i]==a[k]) return 0; } return 1;}void output(int){ int i; cnt++; //测试用格外加的计数器 for(i=1;i<=n;i++) { cout << a[i] << ' '; } cout << cnt << endl;}
运行结果：
4（enter|）2 4 1 33 1 4 2