《黑镜》中的回溯算法

,

前些日子看英剧《黑镜：潘达斯奈基》的时候，突然觉得其叙事结构与回溯算法（Backtracking）的思想颇为相似。《潘达斯奈基》讲述的是年轻程序员 Stephen 开发了一个名为《潘达斯奈基》的冒险类电脑游戏，该游戏文本是基于书籍《选择自己的冒险》。为了将自己的游戏推广于世，Stephen 将游戏交给了为电脑游戏公司塔克软件工作的 Mohan 分发宣传，而 Stephen 则独自在家中完成游戏开发。逐渐地，Stephen 开始觉得自己受到控制，并以与书籍作者 Jerome F. Davies 所做的同样方式陷入疯狂。《潘达斯奈基》是《黑镜》观众互动模式的首次尝试，将剧情发展的几个关键点交由观众自己来选择，观众可以从给定的两个走向中选择其一，以此，主人公 Stephen 的生死也交由观众手上。

回溯算法是暴力搜索法中的一种，通过在每个岔路口选择不同走向的路寻找目的地，一个岔路口、一个岔路口的去尝试。如果走错了路，则返回上一个岔路口，走另一条路，直到找到目的地。回溯算法的经典题包括八皇后问题（N-Queens）、求集合的所有子集、集合中元素的所有排列组合等等。利用回溯算法的解题思考过程和代码框架有一定的套路。在 labuladong 的算法小抄中，回溯算法被等价于多叉树的遍历问题。其文章中也给出了解决回溯问题需要考虑的三个关键基本问题和解题框架。下面是我的 Java 版本。

1、路径：历史选择。
2、选择列表：当前可选项。
3、结束条件：到达多叉树最后一层，无法再做选择时的条件。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public List<List<T>> solution(选择列表) {
    List<List<T>> 返回结果 = new ArrayList<>();
    List<T> 当前路径 = new ArrayList<>();
    backtrack(选择列表，当前路径, 返回结果, ...);
    return 返回结果;
}
private void backtrack(选择列表，当前路径, 返回结果，...) {
    if(满足结束条件) {
        返回结果.add(new ArrayList<>(当前路径));
        return;
    }
    for(选择 : 选择列表) {
        当前路径.add(选择);
        从选择列表里将该选择移除;
        backtrack(选择列表，当前路径, 返回结果，...);
        当前路径.remove(选择);
        将该选择再加入选择列表;
    }
}

那么，如何判断某道题能不能用回溯算法呢？当解题中设计取舍时，就可以考虑使用回溯算法。例如，leetcode 高频题 Combinations Sum：给定一数组和一目标总和 target，求用这个数组里的元素组成和为 target 的所有可能的组合。这里取舍发生于数组每个元素的选与不选。这道题三个基本问题的解答分别是，路径为已经选过的数组元素，选择列表为当前数组的剩余元素，结束条件是选择过的数组元素和等于 target。

最后，回到这部剧集。看《潘达斯奈基》的时候，觉得特别津津有味的是它涉及到了三层相同逻辑的嵌套。最内一层是 Stephen 设计的可自选故事走向的电子游戏，游戏角色的命运被玩家掌握。第二层是 Stephen 本人感觉自己的行为受到了他人的控制。虽然剧情没有点明控制 Stephen 的是谁，但是从某种角度上说，控制他人生的正是坐在电脑屏幕前的我们。而这也禁不住让我再向外延展一层思考，我们的人生轨迹是否也像 Stephen 一样，被观看这一故事背景更宏大、时间跨度更长久的剧集的”观众“所控制呢？谁又能确凿地说自己所处的这个世界不是一局精心设计的游戏、不是一场苦心编排的戏剧呢？

Black_Mirror_Bandersnatch.jpeg