算法设计与分析Notes

声明：由于本人算法水平非常差，大可不必继续往下看。纯属写给自己看的

回溯法

• 问题的解向量：回溯法希望一个问题的解能够表示成一个n元式(x1,x2,…,xn)的形式。
• 显约束：对分量xi的取值限定。
• 隐约束：为满足问题的解而对不同分量之间施加的约束。
• 解空间：对于问题的一个实例，解向量满足显式约束条件的所有多元组，构成了该实例的一个解空间。
• 求解是不断扩充解向量的过程

这里树的每一层的节点维护的是已知$x_1,x_2,...,x_{n-1}$时当前的状态。根是第1层，则叶是第n+1层。

子集树的回溯

递归写法

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

此函数的作用可以描述为：给定x[start:t]输出所有可行解。

非递归写法

void iterativeBacktrack() {
    int t = 1;          // 当前深度
    int* i = new int[n+1]; // 每层独立的"当前子节点序号"
    
    while (t > 0) {
        if (i[t] < g(n, t)) {      // 本层还有未尝试的子节点
            i[t]++;                // 关键：先递增，从 f(n,t) 开始
            x[t] = h(i[t]);
            
            if (constraint(t) && bound(t)) {
                if (solution(t)) {
                    output(x);
                } else {
                    t++;             // 深入下一层
                    i[t] = f(n, t) - 1; // 关键：重置新层的 i[t]，准备从首节点开始
                }
            }
        } else {
            // 本层所有子节点已遍历完
            i[t] = f(n, t) - 1;     // 重置，为下次重新进入该层做准备
            t--;                    // 回溯到上一层
        }
    }
}

排序树的回溯

递归写法

//x初始化为从1~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[i],x[t]);
    }
  }
}

此函数的作用可以描述为：给定x[start:t]，输出所有可行解。

分支限界法

代码框架

def branch_and_bound(X, bound_function):
    """
    分支限界法通用框架
    X: 初始问题实例
    bound_function: 界函数，返回节点上/下界
    """
    # 初始化
    PQ = PriorityQueue()  # 优先队列存储活结点
    best_value = -∞  # 当前最优解值
    
    # 创建根节点
    root = Node(level=0, solution=∅, value=0, bound=bound_function(X, ∅))
    PQ.push(root)
    
    while not PQ.empty():
        # 取出优先级最高的活结点
        node = PQ.pop()
        
        # 剪枝策略
        if node.bound ≤ best_value:  # 界不大于当前最优值
            continue  # 剪枝
            
        # 扩展子节点（分支）
        for child in generate_children(node):
            if is_feasible(child):  # 满足约束
                if is_solution(child):  # 是完整解
                    best_value = max(best_value, child.value)
                else:
                    child.bound = bound_function(X, child)
                    if child.bound > best_value:  # 可能产生更优解
                        PQ.push(child)
    
    return best_value

注意到这里面有两次剪枝，第一次发生在将该节点加入优先队列之前，第二次剪枝发生在扩展该节点时，这两次剪枝并不重复，因为best value是动态变化的，两次剪枝时best value在变得越来越优。那么类似的，在深搜的时候（回溯）我们也可以在每次递归回到当前节点时进行一次剪枝，总而言之就是充分利用信息。

总而言之，搜索的要领就是，要维护的活结点必须是有可能产生可行解/最优解的。对于最优解，我们通过一个限界函数来剪枝。每次回到一个状态，我们就剪枝一次。

搜索按策略来讲有很多种，最常见的是DFS，BFS，或者每次扩展bound最小的节点（如果bound单调，这会导致第一次扩展的叶节点就是最优解）