回溯法

回溯法的算法框架

1. 综述

• 从问题的 解空间树 中，按照 深度优先 的策略，从根节点出发搜索解空间树。
• 回溯法求所有解时，最终需要回溯到根，并且所有节点的字数都已被搜索遍才结束。求一个解时，遇到一个解便可以结束。
• 回溯法适用于组合数较大的问题。

2. 解空间

• 解空间应该至少包含问题的一个解
• 解空间应该很好地组织起来，通常组织成树或者图

3. 基本思想

• 活结点、扩展结点、死结点
• 约束函数剪去不满足约束条件的子树
• 限界函数剪去得不到最优解的子树
• 基本步骤

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];
}