回溯算法的描述

回溯算法

Backtracking is a general algorithm for finding all (or some) solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons each partial candidate c (“backtracks”) as soon as it determines that c cannot possibly be completed to a valid solution.[1][2] 针对一般的计算问题，特别是满足一定约束条件的问题，回溯算法是一个比较常见的解决方式，即是逐步的构建针对解决方案的候选方案，一旦确定候选方案不满足约束条件，不是一个解决方案时候立即的放弃。

The classic textbook example of the use of backtracking is the eight queens puzzle, that asks for all arrangements of eight chess queens on a standard chessboard so that no queen attacks any other. In the common backtracking approach, the partial candidates are arrangements of k queens in the first k rows of the board, all in different rows and columns. Any partial solution that contains two mutually attacking queens can be abandoned. 经典的回溯算法的案例就是八皇后问题，八皇后问题是在一个棋盘上面放置八个不能够互相攻击其他皇后的皇后，在经典的回溯算法中，候选的方案是K个皇后，棋盘的K行，包括皇后的位置处于所有的行和所有的列，任何一个两个皇后能够互相攻击的方案直接的舍弃。

Backtracking can be applied only for problems which admit the concept of a “partial candidate solution” and a relatively quick test of whether it can possibly be completed to a valid solution. It is useless, for example, for locating a given value in an unordered table. When it is applicable, however, backtracking is often much faster than brute force enumeration of all complete candidates, since it can eliminate a large number of candidates with a single test. 回溯算法适合拥有部分候选方案的问题，并且问题能够在相对比较短的时间内验证候选方案。对于无需表中确定一个确定值的位置这样的，回溯算法是不适合的。然而，相比较暴力破解的算法，回溯算法因为能够在一次的测试中放弃大量的候选的方案，所以还是比较快的。

Backtracking is an important tool for solving constraint satisfaction problems, such as crosswords, verbal arithmetic, Sudoku, and many other puzzles. It is often the most convenient (if not the most efficient[citation needed]) technique for parsing, for the knapsack problem and other combinatorial optimization problems. It is also the basis of the so-called logic programming languages such as Icon, Planner and Prolog.

对于满足约束条件的问题，例如填字游戏，语言运算，数独等类似的猜谜的问题，回溯是一个比较重要的工具。另外对于背包问题，组合优化，语法分析也是一个比较方便的工具。另外还是一些逻辑编程语言Icon, Planner and Prolog的基础

Backtracking depends on user-given “black box procedures” that define the problem to be solved, the nature of the partial candidates, and how they are extended into complete candidates. It is therefore a metaheuristic rather than a specific algorithm – although, unlike many other meta-heuristics, it is guaranteed to find all solutions to a finite problem in a bounded amount of time. 回溯取决于用户给定的“黑箱程序”，其定义了要解决的问题，部分候选的性质以及如何将其扩展为完整候选。因此，它是元启发式而不是特定的算法 - 尽管与许多其他元启发式算法不同，它保证在有限时间内找到有限问题的所有解。

Description of the method[]

The backtracking algorithm enumerates a set of partial candidates that, in principle, could be completed in various ways to give all the possible solutions to the given problem. The completion is done incrementally, by a sequence of candidate extension steps. 回溯算法枚举一组部分候选，原则上可以以各种方式给出给定问题的所有可能的解决方案。然后通过选定的步骤逐步地解决。

Conceptually, the partial candidates are represented as the nodes of a tree structure, the potential search tree. Each partial candidate is the parent of the candidates that differ from it by a single extension step; the leaves of the tree are the partial candidates that cannot be extended any further. 在概念上，部分候选方案被表示为树结构的节点，即潜在搜索树。每个部分候选是通过单个扩展步骤与其不同的候选的父代;树的叶是不能进一步扩展的部分候选方案。

The backtracking algorithm traverses this search tree recursively, from the root down, in depth-first order. At each node c, the algorithm checks whether c can be completed to a valid solution. If it cannot, the whole sub-tree rooted at c is skipped (pruned). Otherwise, the algorithm (1) checks whether c itself is a valid solution, and if so reports it to the user; and (2) recursively enumerates all sub-trees of c. The two tests and the children of each node are defined by user-given procedures. 回溯算法从根向下以深度优先顺序递归地遍历该搜索树。在每个节点c，算法检查c是否可以达到有效解条件。如果不能，则跳过（修剪）以c为根的整个子树。否则，算法（1）检查c本身是否是有效解，并且如果是，则将其报告给用户;和（2）递归地枚举c的所有子树。节点和每个节点的子节点的测试都是由用户给定的程序来校验。

Therefore, the actual search tree that is traversed by the algorithm is only a part of the potential tree. The total cost of the algorithm is the number of nodes of the actual tree times the cost of obtaining and processing each node. This fact should be considered when choosing the potential search tree and implementing the pruning test.

因此，回溯遍历的是潜在搜索树的一部分，但是总体的算法的花费是树的全部的节点乘以每一个节点的检查时间。这一点应该在实现算法的时候加以考虑。

Pseudocode

In order to apply backtracking to a specific class of problems, one must provide the data P for the particular instance of the problem that is to be solved, and six procedural parameters, root, reject, accept, first, next, and output. These procedures should take the instance data P as a parameter and should do the following:

• [ ] root(P): return the partial candidate at the root of the search tree.
• [ ] reject(P,c): return true only if the partial candidate c is not worth completing.
• [ ] accept(P,c): return true if c is a solution of P, and false otherwise.
• [ ] first(P,c): generate the first extension of candidate c.
• [ ] next(P,s): generate the next alternative extension of a candidate, after the extension s.
• [ ] output(P,c): use the solution c of P, as appropriate to the application.

The backtracking algorithm reduces the problem to the call bt(root(P)), where bt is the following recursive procedure:

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)

Usage considerations

The reject procedure should be a boolean-valued function that returns true only if it is certain that no possible extension of c is a valid solution for P. If the procedure cannot reach a definite conclusion, it should return false. An incorrect true result may cause the bt procedure to miss some valid solutions. The procedure may assume that reject(P,t) returned false for every ancestor t of c in the search tree. reject是一个返回boolean值的方法，只有当c不可能是p的一个解的时候，才会返回true。如果这个方法不能够确定结论，就返回false。如果方法在不正确的情况，返回了true，就可能会错过某些正确的解。这个方法reject（p,t）搜索树t的根节点时候，可以假设返回false。

On the other hand, the efficiency of the backtracking algorithm depends on reject returning true for candidates that are as close to the root as possible. If reject always returns false, the algorithm will still find all solutions, but it will be equivalent to a brute-force search. 另外一方面，回溯算法的效率和reject返回true的时候，节点离根点的远近成比例。如果reject总是返回false，那么此时的回溯就相当于暴力算法。 The accept procedure should return true if c is a complete and valid solution for the problem instance P, and false otherwise. It may assume that the partial candidate c and all its ancestors in the tree have passed the reject test. 如果c是问题实例P的完整有效解，则accept过程应返回true，否则返回false。它可以假设树中的部分候选c及其所有祖先通过了拒绝测试 Note that the general pseudo-code above does not assume that the valid solutions are always leaves of the potential search tree. In other words, it admits the possibility that a valid solution for P can be further extended to yield other valid solutions. 注意，上面的一般伪代码不假设有效解决方案总是潜在搜索树的叶。换句话说，它承认P的有效解可以进一步扩展以产生其他有效解的可能性。

The first and next procedures are used by the backtracking algorithm to enumerate the children of a node c of the tree, that is, the candidates that differ from c by a single extension step. The call first(P,c) should yield the first child of c, in some order; and the call next(P,s) should return the next sibling of node s, in that order. Both functions should return a distinctive “null” candidate, denoted here by ‘Λ’, if the requested child does not exist.

回溯算法使用first 和 next方法 来遍历树的节点c的所有的子节点，即使候选方案通过c进一步的扩展。first(P,c) 应该是c的第一个孩子，按照某种的顺序，next(P,s)应该是s的兄弟节点，两个函数都有返回 null 的情况，这个使用’Λ’ 代表子节点不存在的情况。

Together, the root, first, and next functions define the set of partial candidates and the potential search tree. They should be chosen so that every solution of P occurs somewhere in the tree, and no partial candidate occurs more than once. Moreover, they should admit an efficient and effective reject predicate.

root first next 这些方法合起来标识潜在搜索树的候选方案的集合，这个集合中包含了树种全部的候选方案，并且候选方案没有重复。另外这些候选方案可以被 reject 方法处理。

Early stopping variants

The pseudo-code above will call output for all candidates that are a solution to the given instance P. The algorithm is easily modified to stop after finding the first solution, or a specified number of solutions; or after testing a specified number of partial candidates, or after spending a given amount of CPU time.

伪代码中是输出全部的解决的方案，如果修改为找到一个解决方案就返回，或者找个几个解决方案就返回，亦或是校验了特定数量的备选方案或者过了特定的时间 就返回，也不是什么难事。