回溯法

回溯法（英语：backtracking）是暴力搜索法中的一种。

*回溯*是一种通用算法，用于查找所有(或部分)解决某些计算问题的解决方案，特别是约束满足问题，这些解决方案逐步构建候选方案，并在确定候选方案不可能在有效的完成时，放弃候选方案(“回溯”)

对于某些计算问题而言，回溯法是一种可以找出所有（或一部分）解的一般性算法，尤其适用于约束满足问题（在解决约束满足问题时，我们逐步构造更多的候选解，并且在确定某一部分候选解不可能补全成正确解之后放弃继续搜索这个部分候选解本身及其可以拓展出的子候选解，转而测试其他的部分候选解）。

在经典的教科书中，八皇后问题展示了回溯法的用例。（八皇后问题是在标准国际象棋棋盘中寻找八个皇后的所有分布，使得没有一个皇后能攻击到另外一个。）

回溯法采用试错的思想，它尝试分步的去解决一个问题。在分步解决问题的过程中，当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候，它将取消上一步甚至是上几步的计算，再通过其它的可能的分步解答再次尝试寻找问题的答案。回溯法通常用最简单的递归方法来实现，在反复重复上述的步骤后可能出现两种情况：

• 找到一个可能存在的正确的答案
• 在尝试了所有可能的分步方法后宣告该问题没有答案

在最坏的情况下，回溯法会导致一次复杂度为指数时间的计算。

为了对特定类型的问题应用回溯，必须为要解决的问题的特定实例提供数据P，以及六个过程参数root、reject、accept、first、next和output。这些程序应以实例数据P为参数，并应做以下工作:

1. root(P): 返回搜索树根处的候选项。
2. reject(P,c):只有当部分候选c不值得完成时才返回true。
3. accept(P,c):如果c是P的解，返回true，否则返回false。
4. first(P,c): 生成候选c的第一个扩展。
5. next(P,s): 在扩展s之后生成候选项的下一个可选扩展。
6. output(P,c): 将P的解决方案c作为输出。

回溯算法将问题简化为bt(root(P))，其中bt是以下递归过程的伪代码:

procedure bt(c)
  if reject(P,c) then return
  if accept(P,c) then output(P,c)
  s ← first(P,c)
  while s ≠ Λ do
    bt(s)
    s ← next(P,s)

回溯可以用来解决难题或问题的例子包括:

• 谜语，如八皇后eight queens puzzle, 纵横字谜，语言算术，数独，和Peg纸牌。
• 组合优化问题，如解析和背包问题。
• 逻辑编程Logic programming ，如Icon, Planner 和Prolog，使用内部回溯来生成答案。

下面是例子，通过回溯来解决的数独游戏。

【来源：web； URL：https://en.wikipedia.org/wiki/Backtracking  】

发展历史

“回溯”（"backtrack"）一词是美国数学家 D. H. Lehmer（ University of California at Berkeley）在20世纪50年代首创的。

“回溯”被大量学者发现并应用。R. J. Walker在1960年，《An enumerative technique for a class of combinatorial problems》给出了一个关于回溯的相当普遍的阐述。这是第一次尝试全面阐述回溯编程的范围和方法。

先驱字符串处理语言SNOBOL(1962)可能是第一个提供内置通用回溯功能的语言。

之后，1965年， S. Golamb 和 L. Baumert.的方案进行修改提出.Backtrack programming，回溯规划已成功地应用于各种组合问题的分块求解，本文的例子仅具有代表性。其他有趣的组合应用包括优化路由问题

【来源：paper ;  URL: Backtrack programming  】

1976年，Stallman, R. M., & Sussman, G. J.提出相关性回溯法。

1993年，动态回溯法被提出，它是一种可以在搜索空间中更深入地移动回溯点的方法。所开发的技术是依赖导向回溯的一种变体。它使用多项式空间，同时仍然提供有用的控制信息，并保留早期方法的完整性。

主要事件

发展分析

瓶颈

在最坏的情况下，回溯法会导致一次复杂度为指数时间的计算。

未来发展方向

对回溯法计算复杂度进行进一步的优化，将是未来研究的重要方向。

Contributor: Ruiying Cai