算法分析·回溯法

回溯法

方法概述
算法框架
问题实例
- TSP 问题
- n皇后问题
回溯法效率分析

方法概述

回溯法是一个既带有系统性又带有跳跃性的搜索算法；

**系统性：**它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。
跳跃性：算法搜索至解空间树的任一结点时，判断该结点为根的子树是否包含问题的解，如果肯定不包含，则跳过以该结点为根的子树的搜索，逐层向其祖先结点回溯。否则，进入该子树，继续深度优先的策略进行搜索。

这种以深度优先的方式系统地搜索问题的解得算法称为回溯法，它适用于解一些组合数较大的问题。

问题的解向量：回溯法希望一个问题的解能表示成一个𝑛元组 $𝑥_1, 𝑥_2, … , 𝑥_𝑛)$ 的形式；
显约束：对分量 $𝑥_𝑖$ 的取值限定；
隐约束：为满足问题的解而对不同分量之间施加的约束；
解空间：对于问题的一个实例，解向量满足显式约束条件的所有多元组，构成了该实
例的一个解空间。

请添加图片描述

搜索从开始结点（根结点）出发，以深度优先搜索整个解空间。

这个开始结点成为活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为新的活结点，并成为当前扩展结点。

如果在当前的扩展结点处不能再向纵深方向扩展，则当前扩展结点就成为死结点。

此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点；直到找到一个解或全部解。

请添加图片描述

基本步骤：

① 针对所给问题，定义问题的解空间；
② 确定易于搜索的解空间结构；
③ 以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

常用剪枝函数：

① 用约束函数在扩展结点处剪去不满足约束的子树；
② 用限界函数剪去得不到最优解的子树。

二类常见的解空间树

① 子集树：当所给的问题是从𝑛个元素的集合𝑆中找出满足某种性质的子集时，相应的解空间树称为子集树。子集树通常有 $2^𝑛$ 个叶子结点，其总结点个数为 $2^{𝑛+1} − 1$ ，遍历子集树时间为 $Ω(2^𝑛)$ 。如0-1背包问题，叶结点数为 $2^𝑛$ ，总结点数 $2^{𝑛+1}$ ；
② 排列树：当所给问题是确定𝑛个元素满足某种性质的排列时，相应的解空间树称为排列树。排列树通常有𝑛!个叶子结点，因此，遍历排列树需要 $Ω (n!)$ 的计算时间。如TSP问题，叶结点数为𝑛!，遍历时间为 $Ω (n!)$ 。

算法框架

回溯法对解空间作深度优先搜索，因此在一般情况下可用递归函数来实现回溯法：

子集树回溯算法的伪代码为：

Backtrack( int 𝑡 ) //搜索到树的第𝑡层
{ //由第𝑡层向第𝑡 + 1层扩展，确定𝑥[𝑡]的值if 𝑡 > 𝑛 then output( 𝑥 ); //叶子结点是可行解else while( all Xt) do //𝑋𝑡为当前扩展结点的所有可能取值集合{𝑿[𝑡] = 𝑋𝑡中的第𝑖个值；if( Constraint(𝑡) and Bound( 𝑡 ) )	Backtrack(𝑡 + 1);}
}

排列树回溯算法的伪代码为：

Backtrack( int 𝑡 ) //搜索到树的第𝑡层
{ //由第𝑡层向第𝑡 + 1层扩展，确定𝑥[𝑡]的值if 𝑡 > 𝑛 then output( 𝑥 ); //叶子结点是可行解else for i=t to n do{swap(X[t],X[i]);if( Constraint(𝑡) and Bound( 𝑡 ) )	Backtrack(𝑡 + 1);swap(X[t],X[i]);}
}

问题实例

TSP 问题

旅行商问题。

旅行商从起点出发，遍历图中全部节点后回到原点，求最小代价。

一般的深度优先搜索如下所示：
请添加图片描述

定义解空间：𝑋 = {12341, 12431, 13241, 13421, 14231, 14321}
构造解空间树；
从A出发按DFS搜索整棵树。

请添加图片描述

最优解：13241，14231
成本：25

回溯法基本思想：利用排列生成问题的回溯算法Backtrack(2)，对𝑥[] = {1, 2, … , 𝑛}的𝑥[2. . 𝑛]进行全排列，则 (𝑥[1] , 𝑥[2]),(𝑥[2], 𝑥[3]) , … , (𝑥[𝑛], 𝑥[1])构成一个回路。在全排列算法的基础上，进行路径计算保存以及进行限界剪枝。

伪代码如下：

main( int n )
{
𝑎[𝑛][𝑛]; 𝑥[𝑛] = {1,2, … , 𝑛}; 
𝑏𝑒𝑠𝑡𝑥[]; cc=0;
𝑏𝑒𝑠𝑡𝑣 = ∞;//bestx保存当前最佳路径，bestv保存当前最优值
input(𝑎); //输入邻接矩阵
TSPBacktrack(2);
output( 𝑏𝑒𝑠𝑡𝑣, 𝑏𝑒𝑠𝑡𝑥[]);
}TSPBacktrack(int i)
{// 𝑐𝑐记录(𝑥[1], 𝑥[2]), … , (𝑥[𝑖 − 1], 𝑥[𝑖])的距离和if(i>n){// 搜索到叶结点，输出可行解与当前解比较if(cc +a[x[n]][1] < bestv or bestv = ∞){bestv = cc+a[x[n]][1];for(j=1;j<= n; j++) bestx[j]= x[j];}
}
else{for(j=i;j<=n;j++)if(cc+a[x[i-1]][x[j]]<bestv or bestv = ∞)// 限界裁剪子树}swap(x[i],x[j]);cc += a[x[i-1]][x[i]];TSPBackstrack(i+1);cc -= a[x[i-1]][x[i]];swap(x[i],x[j]);
}