目录

回溯算法

概念

类似穷举的方法,不断搜索可能解的路径,当发现不满足的条件时,就回溯返回,返回后再继续尝试别的路径。

(如下图示, 为了找到迷宫的出口,不断尝试不同的路径,当发现路径不通时,回溯到岔路口,并继续走其他路径)

走迷宫

基本思想

将上面的走迷宫进一步抽象,可以将这个问题转化成树结构,称之为解空间树

解空间树和迷宫有如下对应关系:

根节点→初始状态

中间节点→分叉路口

不满足问题解的叶子节点→迷宫死路

满足问题解的叶子节点→迷宫出口

解空间树

回溯法解题步骤

​ (1)针对所给问题,确定问题的解空间:

​ 首先应明确定义问题的解空间,问题的解空间应至少包含问题的一个(最优)解。

​ (2)确定结点的扩展搜索规则

​ (3)以深度优先方式搜索解空间,并在搜索过程中用剪枝函数(在搜索算法中优化中,剪枝,就是通过某种判断,避免一些不必要的遍历过程)避免无效搜索。

通用解题方法

实现时的代码细节

递归实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
void backtrack(state s) {
    if(s is end){           // 当前结点为可行解
        sols.append(path);  // 保存该解
    }
    else if(s has no ways){ // 当前结点为不可达叶子结点
        return; 
    }
    else{                   // 当前结点为中间结点
        for(i in possible ways){
            next_s = do i in s; // 选择一条边
            backtrack(next_s);  // 在选择的边上往下走
            s = redo i in s;    // 回溯到父结点
        }
    }
}

例题

39. Combination Sum

参考资料