首页 > Python算法 > 回溯算法 阅读数:26

回溯算法的基本思想

回溯算法可以算作搜索/遍历算法的一个分支。回溯算法和暴力的线性搜索法的相似点在于两者在最坏的情况下都会尝试所有的可能,导致时间复杂度为指数的搜索。但是,比起暴力搜索法,回溯算法是一种有条理的、最优化的搜索技术。

回溯算法会通过提前放弃一些已知不可能的选择,从而加快速度。回溯算法适用于解决信息量较大的约束满足问题。因为一旦约束不再被满足,回溯算法就会丢弃当前选择,转而尝试其他解。

回溯算法可以用一句话概括:不撞南墙不回头,一撞南墙就回头。它采用了试错的思想,与枚举的思路基本是一样的。举个例子,想象一个充满岔口的迷宫,这个迷宫的出口是此问题的解,如图 1 所示。
迷宫
图 1:迷宫

在利用回溯算法寻找解的过程中,我们从起点出发,选择某一条道路向前搜索,如果在某一检查阶段发现路不通,就马上返回到上一个路口,尝试另外一条路。如果该条路也不通,就返回到更早的岔口,再次尝试。回溯算法就是一个走不通就回溯的过程。到最后,我们可能找到正确路线,也有可能宣告迷宫没有出口或解。

以数独为例。已知一个未填满的盘面,我们怎样才能正确地填满它呢?最简单的方法是暴力法。我们依次尝试所有的可能解。如果盘面上有 76 个空位,我们一共需要尝试 976 种可能,因为每一个空位上都有 9 种可能。

当然,我们还可以用回溯算法像暴力法一样将所有的排列组合都先列出来然后再一一尝试。我们将一个数字一个数字地尝试,动态地构建和修改当前的组合。如图 2 所示,第一行、第二列的数字 1 是我们填的数字,其他都是已知的数字。每一个位置都有 9 个选择。首先尝试在第一行、第二列填 1。
数独盘面(1)
图 2:数独盘面(1)

在继续填其他空位前,我们先检查当前盘面是否成立。如果当前盘面不成立,就没有继续填其他空位的必要。我们看到当前盘面不成立。因此,我们需要取消第一个空格里的数字,换成下一个数字。但是 2 仍然不成立,所以我们继续尝试,发现 3 成立。这时会发现,回溯算法已经在帮我们节省时间了。通过放弃 1 和 2,我们节约了尝试 2 × 975 个错误选择的时间。

接下来,到第二个空格,继续尝试。如图 3 所示,还是从第一个数字开始,排除 1、2 和 3,填 4。我们又节约了 3× 974 个错误选择的时间。
数独盘面(2)
图 3:数独盘面(2)

加快进度,按照从左到右、从上到下的顺序,当到第 15 个空格时,我们发现 9 个数字无一可行,如图 4 所示。
数独盘面(3)
图 4:数独盘面(3)

这时,我们需要返回到第 14 个空格,就像在迷宫中退回到上一个岔口一样。如图 5 所示,取消 2,尝试下一个数字。
数独盘面(4)
图 5:数独盘面(4)

然而,如图 6 所示,第 14 个空格除了 2 没有其他选项,3 到 9 都不可行。
数独盘面(5)
图 6:数独盘面(5)

如图 7 所示,我们需要再次返回一个空格,到第 13 个空格,放弃 3,尝试下一个数字,直到数字成立。如果没有数字成立,则继续返回。一直到盘面能够成立为止。
数独盘面(6)
图 7:数独盘面(6)

解题过程中,我们会一直重复“尝试—回溯—尝试—回溯-……”这个过程,一旦一条路走不通,就不再这条路上花费更多的时间,而是后退并尝试另一条路。在这个过程中,我们很有可能会一直会后退到起点,比如在数独的例子中,我们很可能会倒退到第一个空格。

我们甚至会倒退到起点好几次。但是不论怎样,算法在尝试过程中都在有效地“剪枝”,也就是在剪去错误的答案,保证自己永远在尝试目前为止最有效的答案。这就是回溯算法比穷举法更有效率的原因。