回溯法 - 简书

简介
有许多问题，当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时，往往要使用回溯法。
回溯法的基本做法是搜索，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。
回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。

问题的解向量：回溯法希望一个问题的解能够表示成一个n元式(x1,x2,…,xn)的形式。
显约束：对分量xi的取值限定。
隐约束：为满足问题的解而对不同分量之间施加的约束。（即剪枝时可利用的约束条件）
解空间：对于问题的一个实例，解向量满足显式约束条件的所有多元组，构成了该实例的一个解空间。

n=3时的0-1背包问题用完全二叉树表示的解空间

扩展结点：一个正在产生儿子的结点称为扩展结点
活结点：一个自身已生成但其儿子还没有全部生成的节点称做活结点
死结点：一个所有儿子已经产生的结点称做死结点
深度优先的问题状态生成法：如果对一个扩展结点R，一旦产生了它的一个儿子C，就把C当做新的扩展结点。在完成对子树C（以C为根的子树）的穷尽搜索之后，将R重新变成扩展结点，继续生成R的下一个儿子（如果存在）
宽度优先的问题状态生成法：在一个扩展结点变成死结点之前，它一直是扩展结点
回溯法：为了避免生成那些不可能产生最佳解的问题状态，要不断地利用限界函数(bounding function)来处死那些实际上不可能产生所需解的活结点，以减少问题的计算量。 $\color{red}{具有限界函数的深度优先生成法称为回溯法}$

用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为 $h(n)$ ，则回溯法所需的计算空间通常为 $O(h(n))$ 。

递归回溯

void backtrack(int t) {
    if (t > n)
        output(x);
    else
        for (int i = f(n, t); i <= g(n, t); i++) {
            x[t] = h(i);
            if (constraint(t) && bound(t))
                backtrack(t + 1);
        }
}

迭代回溯

void iterativeBacktrack() {
    int t = 1;
    while (t > 0) {
        if (f(n, t) <= g(n, t))
            for (int i = f(n, t); i <= g(n, t); i++) {
                x[t] = h(i);
                if (constraint(t) && bound(t)) {
                    if (solution(t))
                        output(x);
                    else
                        t++;
                }
            }
        else
            t--;
    }
}

子集树与排序树

遍历子集树需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]);
        }
}

典型的回溯问题

排序树
1.全排列问题

#include <iostream>
using namespace std;
//交换
void swap(int &a, int &b) {
    int temp = a;
    a = b;
    b = temp;
}
//全排列递归算法
void Perm(int list[], int k, int m) {
    // list 数组存放排列的数，K表示层 代表第几个数，m表示数组的长度
    if (k == m) {
        // K==m 表示到达最后一个数，不能再交换，最终的排列的数需要输出；
        for (int i = 0; i <= m; i++)
            cout << list[i];
        cout << endl;
    } else {
        for (int i = k; i <= m; i++) {
            swap(list[i], list[k]);
            Perm(list, k + 1, m);
            swap(list[i], list[k]);
        }
    }
}
int main() {
    int a[] = {1, 2, 3};
    int m = 2;
    Perm(a, 0, 2);
    return 0;
}

2.批处理作业调度问题

void Flowshop::Backtrack(int i) {
    if (i > n) {
        for (int j = 1; j <= n; j++)
            bestx[j] = x[j];
        bestf = f;
    } else
        for (int j = i; j <= n; j++) {
            f1 += M[x[j]][1];
            f2[i] = ((f2[i - 1] > f1) ? f2[i - 1] : f1) + M[x[j]][2];
            f += f2[i];
            if (f < bestf) {
                Swap(x[i], x[j]);
                Backtrack(i + 1);
                Swap(x[i], x[j]);
            }
            f1 - = M[x[j]][1];
            f - = f2[i];
        }
}

子集树

利用性价比进一步剪枝

另一种剪枝将物品按重量升序，价值降序排列