回溯法 (Backtracking)

回溯法是一个通用的算法,能够找到一些计算问题的所有解, 通常是一些满足约束问题。 通过遍历的方法寻找解,不断深入搜索,如果确定这部分不可能有解,则放弃这部份的搜索, 继续下一部分的搜索

回溯法的算法本质是:n 叉树的遍历

递归版本

类似对 n 叉树进行遍历,且遍历起始编号为 0. 在遍历中加入约束与限界,以此确定一些子树不需要遍历

大致代码如下,以及一些解释:

  • data 需要用到的数据
  • data->depth 需要遍历的深度
  • depth 遍历的当前深度
  • solution(data) 处理得到的解
  • path[depth] 记录了根到当前节点的路径,可替换为其它需要在各个遍历节点处理的代码
  • constraint(data, depth) 约束函数,满足约束返回 TRUE, 否则返回 FALSE
  • bound(data, depth) 限界函数,满足减枝条件返回 TRUE, 否则返回 FALSE
void backtracking_iter(struct data *data, int depth)
{
    if (data->depth == depth) {
        solution(data);
        return;
    }

    for (int i = 0; i < data->depth; i++) {
        data->path[depth] = i;
        if (constraint(data, depth) == TRUE && bound(data, depth) == FALSE) {
            backtracking(data, depth + 1);
        }
    }
}

void backtracking(struct data *data)
{
    backtracking_iter(data, 0);
}