回溯算法中的优化
回溯算法
如果你经常刷算法题，相信对回溯算法（Backtracking）不会陌生。回溯算法可以看成是深度优先搜索算法的特殊形式，它的目的是在所有可能性中找出最优解。通常来说会使用递归来实现，
1
2
3
4
5
6
7
8
void backtracking(int params) {
// pre-processing...
backtracking(/* ... */);
// post-processing...
// return
}
但是回溯算法的时间复杂度是指数级别的，通常来说仅仅适用于小数据集。我们还是来通过一个例子来讲解。
井字棋（Tic-Tac-Toe） 是一个简单的双人游戏。我们假设人和电脑对战，并且双方都采取最优策略。双方所要做的就是在剩下的格子中选择一个，我们假设选出一个格子，电脑获胜的话记为 +1，人获胜的话为 -1，平的话为 0。从电脑方来看，目的是找的格子在所有的格子中提供最大值，而人则相反，需要找到一个当前提供最小值的格子。
我们可以很容易得出下面的代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public class MoveInfo {
public int move;
public int value;
public MoveInfo( int m, int v ){
move = m; value = v;
}
}
public MoveInfo ticTacToe(boolean isHumanMove) {
int i, responseValue;
int value, bestMove = 1;
MoveInfo quickWinInfo;
if ((quickWinInfo = immediateWin(!isHumanMove) ) != null) { // 如果之前对手走的可以分出胜负，直接返回
return quickWinInfo;
} else if(fullBoard()) { // 如果格子被占满，平局
value = 0;
} else {
value = isHumanMove ? 1 : -1;
for(i = 1; i <= 9; i++) {
if( isEmpty( i ) ) {
place( i, isHumanMove ? HUMAN : COMP );
responseValue = ticTacToe(!isHumanMove).value;
unplace( i );
if (isHumanMove && responseValue < value) {
value = responseValue;
bestMove = i;
} else if (!isHumanMove && responseValue > value) {
value = responseValue;
bestMove = i;
}
}
}
}
return new MoveInfo( bestMove, value );
}
这种算法被称为极小化极大算法（Minimax Strategy），双方都在基于当前的情况，最小化对手的最大收益，也就是最大化自己的收益。这个算法常用于双人对战游戏，比如说象棋、围棋、跳棋等等。当然 Tic-Tac-Toe 相比于其他棋类要简单的多，因为情况比较少，所以用这种暴力求解的方式也行得通。
那么基于这么样的一个算法，我们该如何优化来减少其枚举次数呢？
α ~ ß 剪枝
对于一个回溯算法，我们可以画出类似如下的遍历树（和前面的例子无关）：
当然了并不是说真的存在这颗树，它只是辅助我们理解，树上的每个节点表示的是对应的（递归）函数调用最后计算出来的值。我们前面也提到过回溯算法其实是深度优先搜索的一种特殊性质，这里你可以回想一下二叉树上的遍历，其实是类似的。上图的例子中，回溯到最后，44 就是最终的答案。
树的深度越深，树的宽度越大，那么树的节点数就越多，搜索所需要的时间就会越长。但是不论是深度还是宽度，这都是由问题本身决定的，我们无法对其进行改变。现在的问题是，我们是否真的需要遍历整颗树，如果说在遍历的过程中我们就已经知道了答案，那么是不是就可以终止余下的遍历呢？
这个怎么理解呢？还是上图的例子，我们采用极小化极大算法（Minimax Strategy），假设我们是从左到右进行深度遍历的，我们把其中的几个节点标注了出来：
我们先来看 A 和 C 两个节点。对于节点 A，这里我们需要去求极小值，相对应的节点 A 的父节点就是求极大值，在遍历完其父节点以及左子树后，父节点的值被更新为 73，那么这里还需要继续遍历节点 A 吗？不管节点 A 的值是多少，其父节点的值只可能比 73 要大（父节点求的是极大值），而 A 的祖父节点已经通过左子树将值设定为 68（祖父节点求的是极小值），所以不管遍不遍历 A，祖父节点的值都不变，也就不会影响最终的答案。C 也同理，基于当前已经遍历到的结果，其祖父节点的值不会改变，于是我们可以不去遍历 C 节点对应的整颗子树。
B 和 D 也是一样的道理，只不过 A 和 C 节点处都是求的极小值，而 B 和 D 处求的是极大值。把极小值处的省略（优化）称为 α 剪枝，把极大值处的省略（优化）称为 ß 剪枝，这也就是 α ~ ß 剪枝名字的由来。
再回到我们之前 TicTacToe 的游戏例子，要想做这个优化，我们只需要对原有的代码做略微修改：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public class MoveInfo {
public int move;
public int value;
public MoveInfo( int m, int v ){
move = m; value = v;
}
}
public MoveInfo ticTacToe(boolean isHumanMove, int alpha, int beta) {
int i, responseValue;
int value, bestMove = 1;
MoveInfo quickWinInfo;
if ((quickWinInfo = immediateWin(!isHumanMove) ) != null) { // 如果之前对手走的可以分出胜负，直接返回
return quickWinInfo;
} else if(fullBoard()) { // 如果格子被占满，平局
value = 0;
} else {
value = isHumanMove ? beta : alpha;
for(i = 1; i <= 9 && ((isHumanMove && value > alpha) || (!isHumanMove && value < beta)); i++) {
if( isEmpty( i ) ) {
place( i, isHumanMove ? HUMAN : COMP );
responseValue = isHumanMove ? ticTacToe(!isHumanMove, alpha, value).value
: ticTacToe(!isHumanMove, value, beta).value;
unplace( i );
if (isHumanMove && responseValue < value) {
value = responseValue;
bestMove = i;
} else if (!isHumanMove && responseValue > value) {
value = responseValue;
bestMove = i;
}
}
}
}
return new MoveInfo( bestMove, value );
}
在实际应用中，α ~ ß 剪枝可以把搜索节点数从 N 个降到 $ \sqrt{N} $ 个，具体还需要结合实际情况来考虑。应用了这个优化，相同时间内，算法能够处理的数据集也就变多了，当然了，除了 α ~ ß 剪枝还有其他的剪枝优化，都是通过减少递归函数调用的次数来达到优化算法的目的。