4.6 最小生成树

掌握Prim算法和Kruskal算法思想，复杂度分析。

第5章回溯法

5.1 回溯法的算法框架

回溯法的基本步骤：

▪(1)针对所给问题，定义问题的解空间；

▪(2)确定易于搜索的解空间结构；

▪(3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

常用剪枝函数：

▪用约束函数在扩展结点处剪去不满足约束的子树；

▪用限界函数剪去得不到最优解的子树。

关于复杂性：

▪用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。

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

子集树的回溯算法O(2n)

void backtrack (int t)

{

if (t>n) output(x);

else

for (int i=0;i<=1;i++) {

x[t]=i;

if (legal(t)) backtrack(t+1);

}

}

排列树的回溯算法O(n!)

void backtrack (int t)

{

if (t>n) output(x);

else

for (int i=t;i<=n;i++) {

swap(x[t],x[i]);

if (legal(t)) backtrack(t+1);

swap(x[t],x[i])

}

}

6/8