回溯法的含义 百度百科
回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）。 若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。 而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束
（1）针对所给问题，定义问题的解空间；//解答树？ （2）确定易于搜索的解空间结构； （3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。
例子1
N皇后问题
方法1就是动态判断
void search(int cur)
{
if(cur==n+1)//说明已经处理完成了(cur==n-1时正在处理最后一排)
{
tot++;
if(tot<=3)
{
for(int i=1;
i<=n;
i++)
{
printf("%d ",map[i]);
}
putchar('\n');
}
}
else
{
//尝试填入i于第cur行
for(int i=1;
i<=n;
i++)
{
int ok=1;
//开始检查是否在之前的皇后的攻击范围之内
for(int j=1;
j但是此处因为每次动态判断的列，对角线有重复，所以会效率低下 下面采取了一种用二维数组进行记忆化判断的方法，此种方法可以提高效率。
int vis[3][50];
//此处的20是用n-1+1+n-1 估算出来的
//vis[0][i]记录的是i列是否属于攻击范围
//vis[1][i]记录的是i号正对角线是否属于攻击范围
//vis[2][i]记录的是i号副对角线是否属于攻击范围
void search2(int cur)
{
if(cur==n+1)//说明已经处理完成了(cur==n-1时正在处理最后一排)
{
tot++;
if(tot<=3)
{
for(int i=1;
i<=n;
i++)
{
printf("%d ",map[i]);
}
putchar('\n');
}
}
else
{
//开始尝试加入i
for(int i=1;
i<=n;
i++)
{
int ok=1;
//开始检查
if(vis[0][i]||vis[1][cur+i]||vis[2][cur-i+n])
ok=0;
//为了清晰 写的比较啰嗦点
if(ok)
{
//因为vis数组是全局变量，此处若想在递归中来当作局部变量一样入栈出栈，必须要手动恢复
vis[0][i]=vis[1][cur+i]=vis[2][cur-i+n] =1;
map[cur]=i;
search2(cur+1);
vis[0][i]=vis[1][cur+i]=vis[2][cur-i+n] =0;
}}
}
}这样效率就提高了不少 用wikioi的一张图进行对比
文章图片
恰好是一半的时间左右，，这个好像是可以根据分析算出的。。。暂时先留个疑问。
例子2素数环问题
也是有两个方法来进行比较。
第一个就是纯粹的动态判断+暴力枚举
因为这里需要不断得进行枚举排列。
那么就有stl进行下一个排列枚举的方法 还有动态生成的方法。
这里是要进行先枚举排列后进行判断，所以用do while循环来调用next_permutation
//生成第一个排列
for(int i=1;
i<=n;
i++)
A[i-1]=i;
//用这个排列来使用np .但是要保证一直以1开头
do
{
//开始判断
int ok=1;
for(int i=0;
i这种方法因为是无脑枚举...所以很慢 而用回溯法就可以解决这个问题，使得解答树的遍历过程显得很聪明。
void dfs(int cur)
{
//当cur==n时说明A[n-1] 已经有元素了
if(cur==n&&isp[A[0]+A[n-1]])
{
for(int i=0;
iA[0]=1;
dfs(1);
这样的话，即使n=18依然可以跑得比较快。 【算法学习笔记|【算法学习笔记】14.暴力求解法03 回溯法01 N皇后和素数环】
推荐阅读
- NOJ|NOJ 1227: 拆数
- leetcode做题笔记|leetcode:Subsets
- 算法学习|【算法学习】二维数组查找（Java）
- 算法学习笔记|【算法学习笔记】02.wikioi1205 单词翻转
- 【算法学习笔记】22.算法设计初步 二分查找 上下界判断
- 解题报告|【算法学习笔记】23.动态规划 解题报告 SJTU_OJ 1280 整装待发
- 算法学习笔记|【算法学习笔记】19.算法设计初步 最大子列和问题的三种方法
- 算法学习笔记|【算法学习笔记】20.算法设计初步 归并排序 求逆序数
- 【算法学习笔记】15.暴力求解法04 回溯法02 困难的串