回溯法
回溯法的算法框架
1. 综述
- 从问题的 解空间树 中，按照 深度优先 的策略，从根节点出发搜索解空间树。
- 回溯法求所有解时，最终需要回溯到根，并且所有节点的字数都已被搜索遍才结束。求一个解时，遇到一个解便可以结束。
- 回溯法适用于组合数较大的问题。
2. 解空间
- 解空间应该至少包含问题的一个解
- 解空间应该很好地组织起来，通常组织成树或者图
3. 基本思想
- 活结点、扩展结点、死结点
- 约束函数剪去不满足约束条件的子树
- 限界函数剪去得不到最优解的子树
- 基本步骤
- 针对所给的问题，定义问题的解空间；
- 确定易于搜索的解空间；
- 以深度优先方式搜索解空间，并在搜索的过程中用剪枝函数避免无效搜索。
4. 递归回溯
/*
t:递归深度
n:最大深度
f(n,t):当前扩展结点处未搜索过的子树的起始编码
g(n,t):当前扩展结点处未搜索过的子树的终止编码
Constraint(t):约束函数
Bound(t):限界函数
自顶向下，
对每个结点的分支进行递归调用 for(int i=f(n,t);i<=g(n,t);i++)
*/
void Backtrack(int t)
{
if(t > n) Output(x); //是否递归结束
else
{
for(int i=f(n,t);i<=g(n,t);i++) //保证所有子树要不被遍历，要么被剪枝
{
t=i;
if(Constraint(t)&&Bound(t)) Backtrack(i+1);
}
}
}
5. 迭代回溯
/*
自顶向下，
对每个结点的分支进行迭代 for(int i=f(n,t);i<=g(n,t);i++)
*/
void IterativeBacktrack(void)
{
int t=1;
while(t > 0)
{
if(f(n,t) <= g(n,t))
{
for(int i=f(n,t);i<=g(n,t);i++)
{
t=i;
if(Constraint(t)&&Bound(t))
{
if（Solution(t)) Output(x); //Solution(t)用于判断问题是都得以解决
else t++;
}
else t--;
}
}
}
}
6. 子集树
从结合S中寻找满足某种性质的子集时，相应的解空间树称为子集树，如0-1背包问题。
子集树一般为完全二叉树，也就是由“要、不要、要、不要等”形成。
void Backtrack(int t)
{
if(t > n) Output(x); //是否递归结束
else
{
for(int i=0;i<=1;i++) //保证所有子树要不被遍历，要么被剪枝
{
t=i;
if(Constraint(t)&&Bound(t)) Backtrack(i+1);
}
}
}
7. 排列树
确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。排列树通常有n!个叶结点。例如旅行售货员问题。
void Backtrack(int t)
{
if(t > n) Output(x);
else
{
for(int i=t;i<=n;i++)
{
Swap(x[t],x[i]);
if(Constraint(t)&&Bound(t)) Backtrack(i+1);
Swap(x[i],x[t]);
}
}
}
货箱装载
1. 问题描述
两艘船，n个货箱。第一艘载重量c1，第二艘载重量c2。wi是货箱i的重量，∑wi<=c1+c2。确定一种方法把n个货箱全部装上船。
∑wi<=c1=c2，原问题等价于子集之和问题；c1=c2，原问题等价于分割问题。这两个问题都是NP-复杂问题。
解决办法 ：尽可能将第一艘船转载到它的转载极限，在将剩余的装载到第二艘。
为了将第一艘船尽可能装满，需要一个货箱的子集，使得他们的总重量接近于c1。这个问题可以通过0/1背包问题来解决。
2. 递归回溯算法
属于上述的子集树解决办法。
/*
货箱重量weight[1:numberOfContainers]
rLoad(1):返回<=capacity的最大子集之和
*/
void rLoad(int currentLevel)
{
//从currentLevel处的节点开始搜索
if(currentLevel > numberOfContainers)
{
//到达一个叶节点处
if(weightOfCurrentLoading > maxWeightSoFar)
maxWeightSoFar = weightOfCurrentLoading;
return;
}
//还未到达叶节点，检查子树
if(weightOfCurrentLoading + weight[currentLevel] <= capacity)
{
//搜索左子树，即x[currentLevel]=1
weightOfCurrentLoading += weight[currentLevel];
rLoad(currentLevel + 1);
weightOfCurrentLoading -= weight[currentLevel];
}
//搜索左子树，即x[currentLevel]=0，既然为0那么可以无需检查而得以继续
rLoad(currentLevel + 1);
}
3. 寻找最优子集
增加代码来寻找到当前的最优子集，为此使用一组数组bestLoadingSoFar,当且仅当bestLoadingSoFar[i]=1时，货箱i属于最优子集。
/*
报告最有装载的预处理程序
*/
int maxLoading(int *theWeight, int theNumberOfContainers, int theCapacity, int *bestLoading)
{
/*
数组theWeight[1:theNumberOfContainers]是货箱重量
theCapacity是船的载货量
数组bestLoading[1:theNumberOfContainers]是解
返回最大载重量
*/
//初始化全局变量
numberOfContainers = theNumberOfContainers;
weight =theWeight;
capacity = theCapacity;
weightOfCurrentLoading = 0;
maxWeightSoFar = 0;
currentLoading = new int [numberOfContainers+1];
bestLoadingSoFar = bestLoading;
//remainingWeight的初始值是所有货箱重量之和
for(int i=1;i<=numberOfContainers;i++)
{
remainingWeight += weight[i];
}
//计算最优装载的重量
rLoad(1);
return maxWeightSoFar;
}
/*
报告最优装载的回溯算法
*/
void rLoad(int currentLevel)
{
//从currentLevel处开始搜索
if(currentLevel > numberOfContainers)
{
//到达了一个叶节点，存储一个更优解
for(int j=1; j <= numberOfContainers; j++)
bestLoadingSoFar[j] = currentLoading[j];
maxWeightSoFar = weightOfCurrentLoading;
return;
}
//没有到达一个叶节点，检查子树
remainingWeight -= weight[currentLevel];
if(weightOfCurrentLoading + weight[currentLevel] <= capacity)
{
//搜索左子树
currentLoading[currentLevel] = 1;
weightOfCurrentLoading += weight[currentLevel];
rLoad(currentLevel + 1);
weightOfCurrentLoading -= weight[currentLevel];
}
if(weightOfCurrentLoading + remainingWeight > maxWeightSoFar)
{
//搜索右子树
rLoad(currentLevel + 1);
}
remainingWeight += weight[currentLevel];
}
