实际场景中,解决问题的出发点有多种,为了确认这些出发点是否真的可以解决问题,我们需要逐一测试,找出 1 个甚至所有可行的解决方案,必要时还需要从众多可行方案中找出一个最优的方案。这种情况下,就可以优先考虑回溯算法。
回溯是一种可查找部分甚至全部解决方案的算法,它能够对所有的可行性方案进行测试,一旦判定某个方案无效,则以回溯的方式继续测试其它的方案,直至测试完所有的方案。
回溯可以简单地理解为“回退”或者“原路返回”,我们以一个实例来理解回溯的含义。如下图所示,找出从 A 到 K 的路径:
图 1 回溯的含义
显然,从 A 到 K 的路径为 A-E-J-K,但如果要编程实现查找可行的路径,需要一一测试从 A 出发的所有路径,整个查找的过程为:
从 A 出发,有 2 条路径可以选择,先选择 A-B;从 B 出发,又有 2 条路径,先选择 B-C;
到达 C 后,发现无法达到 K,所以放弃此路线,回退至 B,继续测试其他路径(第一次回溯);
继续探查 B-D,发现也无法到达 K,回退到 B,继续探测其他路径(第二次回溯);
除 B-C 和 B-D 外,没有其他路径可供选择,回退至 A,探测其他路径(第三次回溯);
除了 A-B 外,还可以选择 A-E,测试过程同测试 A-B 部分的方式完全相同。
下图给您描绘了测试所有路径所经历的过程:
图 2 回溯的过程
通过不断的回溯,找到解决问题的所有可行方案,这样的算法就称为回溯算法。
回溯算法经常以递归的方式实现,该算法常用于解决以下 3 类问题:
决策问题:从众多选择中找到一个可行的解决方案;
优化问题:从众多选择中找到一个最佳的解决方案;
枚举问题:找出能解决问题的所有方案。
经典的适合用回溯算法解决的问题有 N皇后问题、迷宫问题等,我们会在后续章节给大家做详细的讲解。