**回溯算法:**在包含问题的所有可能解的解空间树中，从根节点出发，按照深度优先遍历的策略进行搜索,对于解空间树种的某个节点，如果该节点满足问题的约束条件，则进入该子树继续进行搜索，否则将以该节点为根节点的子树进行剪枝。回溯法常常可以避免所有的可能解，所以，适用于求解组合数中较大的问题。回溯法从解空间树的根节点出发，按照深度优先遍历策略搜索满足约束条件的解。在搜索至树种某节点时，先判断该节点对应的部分是否满足约束条件.也就是判断该节点是否包含问题的(最优)解，如果肯定不包含，则跳过该节点为跟的子树，即所谓剪枝;否则，进入以该节点为跟的子树，继续按照深度优先遍历策略进行搜索。
设计
代码:
#include <iostream>
#include<math.h>
using namespace std;
/*
约束条件:(1)与已经填写的数不重复
(2)与前一个数的和是素数
(3)最后一个数与第一个数的和是素数
*/
bool isPrime(int x);
void Backtracking(int n);
bool check(int t);
static int n=20;
int arr[20];
int main()
{
Backtracking(20);
return 0;
}
void Backtracking(int n)
{
for(int i=0;i<n;i++)//将数组每个数初始化为0
{
arr[i]=0;
}
int k=1;
arr[0]=1;//将第一个位置置为1,素数环从1开始
while(k>=1)
{
arr[k]+=1;
while(arr[k]<n)//填写第k个位置
{
if(check(k)==1)
{
break;
}
else
{
arr[k]+=1;
}
}
if(arr[k]<=n&&k==n-1)//求解完,输出
{
cout<<"素数环为:";
for(int i=0;i<n;i++)
{
cout<<arr[i]<<" ";
}
return;
}
if(arr[k]<=n&&k<n-1)//第k个位置填写完,继续填写第K+1个位置
{
k+=1;
}
else
{
k--; //回溯到K-1个位置
arr[k]+=1;//从原来填写的数+1开始
}
}
}
//检查当前选择的数与前面选的数是否重复,并且判断是否与前一个数的和为素数
bool check(int t)
{
bool flag;
for(int i=0;i<t;i++)
{
if(arr[i]==arr[t])
{
return 0;
}
}
flag=isPrime((arr[t]+arr[t-1]));
if(flag&&t==n-1)//最后一个数与第一个数的和为素数
{
flag=isPrime((arr[1]+arr[n-1]));
}
return flag;
}
bool isPrime(int x)//判断一个数是否是素数
{
int k= (int)sqrt(x);
for(int i=2;i<=k;i++)
{
if(x%i==0)
{
return false;
}
}
return true;
}
结果
分析
n个位置,每个位置可以填写的情况有n种,因此素数环问题的解空间是一颗完全n叉树,树的深度2为n,
最坏情况下的时间复杂度为O(n^n)
总结:
通过本次实验加深了我对回溯算法所给的模式的理解，同时对用回溯算法解决一个实际问题有了一个更深层次的认识。回溯算法非递归的模式通用，用它解决一个问题的关键是找出合法解与部分解.的判断条件，在合法解时书写相应程序段，在部分解时书写相应程序段。另外注意有些条件部分解和合法解都要满足，此时要排除掉非法解，即要给它剪去。另外需要注意的是回溯的过程。总之，通过本次实验使我掌握了回溯算法非递归的一般模式，以后在解决一类问题时可以照着这个模式编写程序。