回溯算法也叫试探法,它是一种系统地搜索问题的解的方法。回溯算法的基本思想是:从一条路往前走,能进则进,不能进则退回来,换一条路再试。用回溯算法解决问题的一般步骤为:
1、定义一个解空间,它包含问题的解。
2、利用适于搜索的方法组织解空间。
3、利用深度优先法搜索解空间。
4、利用限界函数避免移动到不可能产生解的子空间。
问题的解空间通常是在搜索问题的解的过程中动态产生的,这是回溯算法的一个重要特性。
经典例子(N后问题):
要求在一个n*n格的棋盘上放置n个皇后,使得她们彼此不受攻击,即使得任何两个皇后不能被放在同一行或同一列或同一斜线上(国际象棋中一个皇后可以攻击与之处在同一行或同一列或同一斜线上的其他任何棋子)。注意通常会多种可行的放置方案。
n皇后问题是NP完全的,用回溯法求解:
(1)定义问题的解空间:用n元组x[1:n]表示它的解,即一个可行的放置方案。其中x[i]表示皇后i放在棋盘的第i行第x[i]列。由于不允许将任何两个皇后放在同一列,所以解向量中诸x[i]互不相同。而任何两个皇后不能放在同一斜线上是问题的隐约束。在搜索时,可通过这个斜线约束来剪去无效的子树。将棋盘看作是二维方阵,从左上角到右下角的主对角线及其平行线上(即斜率为-1的各斜线),
元素的两个下标值的差值相等。同理,斜率为+1的每一条斜线上,元素的两个下标值的和相等。因此,若两个皇后放置位置为(i,j)和(k,l),且i-j=k-l或i+j=k+l,则这两个皇后处于同一斜线上。这里两个等式可统一表示为|i-k|=|j-l|。
(2)确定解空间树的结构:可以用一棵完全n叉树来表示n皇后问题的解空间。树枝上用放置的列号来标记,从树根到任一叶子结点的路径都是一种放置方案。这个完全n叉树共有n**n(即n的n次方)个叶子结点,因此遍历解空间树的算法需要O(n**n)的时间复杂度。
(3)以深度优先方式搜索整个解空间,找出所要的解:约束函数为Plack(k),它用来测试将皇后k放在x[k]列是否与前面已放置的k-1个皇后都不在同一列,且都不在同一斜线上。在回溯函数中,若搜索到达叶子结点(i>n),则得到一个新的n皇后互不攻击的可行方案,可行方案数加1。若还未到达叶子结点(i<=n),由于是n叉树,当前扩展结点有n个放置列号x[i]=1,2,...,n所表示的n个儿子结点,对皇后i的每一种列号放置情况,用结束函数Place检查其可行性,若可行则进入这个子树进行递归搜索,否则剪去这个子树。算法实现如下:
//问题及其解空间描述
class Queen{
private:
friend int nQueen(int); //算法实现函数
bool Place(int k); //约束函数
void Backtrack(int i); //回溯搜索函数
int n; //皇后个数
int* x; //当前解
long sum; //当前已找到的可行方案数
};
//约束函数
bool Queen::Place(int k){
for(int j=1;j<k;j++) //判断若将皇后k放在(k,x[k])处,与前面的每一个皇后(j,x[j])是否都不在同一列,且都不在同一斜线上
if( (x[j]==x[k]) || (abs(k-j)==abs(x[j]-x[k])) )
return false;
return true;
}
void Queen::Backtrack(int i){
if(i>n) //搜索到达叶子结点,得到一个新的可行的放置方案
sum++;
else //否则没达到叶子结点,当前扩展结点有n个列号x[i]=1,2,...,n表示的n个儿子结点
for(int j=1;j<=n;j++){
x[i]=j; //将皇后i放置在第j列
if(Place(i)) //若这个放置可行,则进入这个子树进行递归搜索
Backtrack(i+1);
}
}
//算法实现函数:返回可行的放置方案个数,这里数组x的长度应该为n+1,
//x[1]~x[n]存放了其中的一个可行放置方案
int nQueen(int* x,int n){
Queen alg;
alg.n=n;
alg.sum=0;
for(int i=1;i<=n;i++) //初始化各皇后的放置情况
alg.x[i]=0;
alg.Backtrack(1); //搜索整个解空间树
delete[] alg.x;
return alg.sum;
}
由于解空间树有n**n(即n的n次方)个叶子结点,因此算法的时间复杂度为O(n**n),非常耗时。回溯法有通用解题法之称。因为它采用的是搜索整个解空间的策略,对一些无从下手的、组合数较大的问题(特别是很多NP完全问题),回溯法是一个有力的工具。回溯法对解空间进行了有效的组织(组织成树或图的结构),还可以用剪枝函数来提高平均搜索效率,因此它的效率大大高于纯粹的穷举法。
小结:
考试虽然已经过去,偶尔回首看看,还是有很多收获的 。 回忆着写这些博客,可能有错误,也可能有一些理解不到的地方,如有问题,欢迎指正!
分享到:
相关推荐
这是算法分析中回溯算法的一个经典实验——N后问题。 里面包涵源程序和实验报告!!!!!
五大常用算法——回溯算法详解及经典例题,算法数据结构 五大常用算法
最优装载问题——回溯法 最优装载问题——回溯法 最优装载问题——回溯法
回溯法采用的搜索策略-五大常用算法——回溯算法详解及经典例题,算法数据结构 五大常用算法
算法分析论文——回溯算法的应用 包括算法的即便额概念,思想,回溯法应用及其在某些方面的改进
算法分析论文——回溯算法的应用 包括算法的即便额概念,思想,回溯法应用及其在某些方面的改进
回溯算法——n皇后问题
课程的随堂作业,C语言的,用dev就能运行,萌新代码,勿喷,仅仅帮助不想写作业的朋友方便一下,反正老师也不会仔细检查的
课程的随堂作业,C语言的,用dev就能运行,萌新代码,勿喷,仅仅帮助不想写作业的朋友方便一下,反正老师也不会仔细检查的
八皇后问题是一个古老而著名的问题,是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出:在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线...
5.5 对多个键进行排序——不稳定排序的修正方法 5.6 网络排序 5.7 小结:选择一种排序算法 5.8 资源和参考资料 第6章 树 6.1 二叉树 6.1.1 树查找 6.1.2 节点插入 6.1.3 节点删除 6.1.4...
五大常见算法策略之——回溯策略,算法数据结构 五大常用算法
n皇后问题的三种算法,n^n穷举,n!穷举,回溯法,比较它们的效率
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
剑指offer计划28(搜索与回溯算法困难)---java(csdn)————程序
剑指offer计划19( 搜索与回溯算法中等)---java(csdn)————程序
剑指offer计划15( 搜索与回溯算法中等)---java(csdn)————程序
剑指offer计划20( 搜索与回溯算法中等)---java(csdn)————程序
用回溯法实现子集和问题的完整代码
剑指offer计划7(搜索与回溯算法简单版)---java(csdn)————程序