回溯法

2023-11-12 20:16:25

好文分享：https://blog.csdn.net/qq_53549930/article/details/124136986

1. 子集树

有时问题是要从一个集合的所有子集中搜索一个集合，作为问题的解。

当问题是要计算n个元素的子集，以便达到某种优化目标时，可以把这个解空间组织成一棵子集树。

复杂度Ω(2ⁿ)

 1 //形参t为树的深度，根为1
 2 void backtrack (int t)
 3 {
 4 　　if (t>n) update(x);
 5 　　else
 6 　　　　for (int i=0; i<=1; i++)　　//每个结点只有两个子树
 7 　　　　{
 8 　　　　　　x[t]=i;　　　　　　　  //即0/1
 9 　　　　　　if (constraint(t) && bound(t)) backtrack(t+1);
10 　　　　}
11 }
12  
13 约束函数constraint(t)和限界函数bound(t)，称为剪枝函数。
14 函数update(x)是更新解向量x的。
15 约束函数constraint(t)，一般可以从问题描述中找到。

2. 排列树

当所给的问题是确定n个元素满足某种性质的排列时，可以把这个解空间组织成一棵排列树。

排列树通常有n!个叶子结点。因此遍历排列树时，其计算时间复杂度是Ω(n!) 。

例如，旅行商问题就是一棵排列树。

 1 //形参t为树的深度，根为1
 2 void backtrack (int t)
 3 {
 4 　　if (t>n) update(x);
 5 　　else
 6 　　　　for (int i=t; i<=n; i++)
 7 　　　　{
 8 　　　　　　//为了保证排列中每个元素不同，通过交换 来实现
 9 　　　　　　swap(x[t], x[i]);
10 　　　　　　if (constraint(t) && bound(t)) backtrack(t+1);
11 　　　　　　swap(x[t], x[i]);　　　　//恢复状态
12 　　　　}