Java 为什么这称为回溯？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/24372387/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Why is this called backtracking?
提问by Elad Benda2
I have read in Wikipedia and have also Googled it,
我在维基百科上读过，也用谷歌搜索过，
but I cannot figure out what "Backtracking Algorithm" means.
但我无法弄清楚“回溯算法”是什么意思。
I saw this solution from "Cracking the Code Interviews"
我从“破解代码面试”中看到了这个解决方案
and wonder why is this a backtracking algorithm?
想知道为什么这是一个回溯算法？
采纳答案by Willem Van Onsem
"Backtracking" is a term that occurs in enumerating algorithms.
“回溯”是一个出现在枚举算法中的术语。
You built a "solution" (that is a structure where every variable is assigned a value).
您构建了一个“解决方案”（即每个变量都分配了一个值的结构）。
It is however possible that during construction, you realize that the solution is not successful (does not satisfy certain constraints), then you backtrack: you undo certain assignments of values to variables in order to reassign them.
然而，有可能在构建过程中，您意识到解决方案不成功（不满足某些约束），然后您回溯：您撤消对变量的某些值分配以重新分配它们。
Example:
示例：
Based on your example you want to construct a path in a 2D grid. So you start generating paths from (0,0). For instance:
根据您的示例，您要在 2D 网格中构建路径。所以你开始从 (0,0) 生成路径。例如：
(0,0)
(0,0) (1,0) go right
(0,0) (1,0) (1,1) go up
(0,0) (1,0) (1,1) (0,1) go left
(0,0) (1,0) (1,1) (0,1) (0,0) go down
Oops, visiting a cell a second time, this is not a path anymore
Backtrack: remove the last cell from the path
(0,0) (1,0) (1,1) (0,1)
(0,0) (1,0) (1,1) (0,1) (1,1) go right
Oops, visiting a cell a second time, this is not a path anymore
Backtrack: remove the last cell from the path
....
回答by Giovanni Botta
From Wikipedia:
来自维基百科：
Backtracking is a general algorithm for finding all (or some) solutions to some computational problem, 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.
回溯是一种通用算法，用于寻找某些计算问题的所有（或部分）解决方案，它逐步构建解决方案的候选者，并在确定 c 不可能完成到 a 时立即放弃每个部分候选者 c（“回溯”）有效的解决方案。
Backtracking is easily implemented as a recursive algorithm. You look for the solution of a problem of size nby looking for solutions of size n- 1 and so on. If the smaller solution doesn't work you discard it.
回溯很容易实现为递归算法。您通过寻找大小为n- 1 等的解来寻找大小为n的问题的解。如果较小的解决方案不起作用，则将其丢弃。
That's basically what the code above is doing: it returns true in the base case, otherwise it 'tries' the right path or the left path discarding the solution that doesn't work.
这基本上就是上面的代码所做的：它在基本情况下返回 true，否则它“尝试”正确的路径或左路径，丢弃不起作用的解决方案。
Since the code above it's recursive, it might not be clear where the "backtracking" comes into play, but what the algorithm actually does is building a solution from a partial one, where the smallest possible solution is handled at line 5 in your example. A non recursive version of the algorithm would have to start from the smallest solution and build from there.
由于上面的代码是递归的，因此可能不清楚“回溯”在哪里发挥作用，但算法实际所做的是从部分解决方案构建解决方案，其中最小的可能解决方案在您的示例中的第 5 行处理。该算法的非递归版本必须从最小的解决方案开始并从那里构建。
回答by Mike Samuel
I cannot figure out what "backtracking algorithm" means.
我无法弄清楚“回溯算法”是什么意思。
An algorithm is "back-tracking" when it tries a solution, and on failure, returns to a simpler solution as the basis for new attempts.
算法在尝试解决方案时会“回溯”，并且在失败时返回到更简单的解决方案作为新尝试的基础。
In this implementation,
在这个实现中，
current_path.remove(p)
goes back along the path when the current path does not succeed so that a caller can try a different variant of the path that led to current_path.
当当前路径不成功时沿着路径返回，以便调用者可以尝试导致 的路径的不同变体current_path。
回答by Josef E.
Backtrackingis a form of recursion, at times.
回溯有时是一种递归形式。
This boolean based algorithm is being faced with a choice, then making that choice and then being presented with a new set of choices after that initial choice.
这个基于布尔值的算法面临一个选择，然后做出这个选择，然后在最初的选择之后呈现一组新的选择。
Conceptually, you start at the root of a tree; the tree probably has some good leaves and some bad leaves, though it may be that the leaves are all good or all bad. You want to get to a good leaf. At each node, beginning with the root, you choose one of its children to move to, and you keep this up until you get to a leaf.(See image below)
从概念上讲，您从树的根部开始；这棵树可能有一些好的叶子和一些坏的叶子，尽管可能叶子都是好的或全是坏的。你想得到一片好叶子。在每个节点，从根开始，你选择它的一个子节点移动，并保持它直到你到达一个叶子节点。（见下图）
Explanation of Example:
示例说明：
- Starting at Root, your options are A and B. You choose A.
- At A, your options are C and D. You choose C.
- C is bad. Go back to A.
- At A, you have already tried C, and it failed. Try D.
- D is bad. Go back to A.
- At A, you have no options left to try. Go back to Root.
- At Root, you have already tried A. Try B.
- At B, your options are E and F. Try E.
- E is good. Congratulations!
- 从 Root 开始，您的选项是 A 和 B。您选择 A。
- 在 A，您的选项是 C 和 D。您选择 C。
- C是坏的。回到A。
- 在 A 处，您已经尝试过 C，但它失败了。试试 D。
- D 不好。回到A。
- 在 A 处，您没有其他选择可以尝试。回到根。
- 在 Root，您已经尝试过 A。尝试 B。
- 在 B 处，您的选项是 E 和 F。试试 E。
- E 不错。恭喜！
Source: upenn.edu
资料来源：upenn.edu
回答by Jenian
Backtracking basically means trying all possible options. It's usually the naive, inefficient solutions to problems.
回溯基本上意味着尝试所有可能的选项。它通常是对问题的幼稚、低效的解决方案。
In your example solution, that's exactly what's going on - you simply try out all possible paths, recursively: You try each possible direction; if you found a successful path - good. if not - backtrackand try another direction.
在您的示例解决方案中，这正是正在发生的事情 - 您只需递归地尝试所有可能的路径：您尝试每个可能的方向；如果你找到了一条成功的道路 - 很好。如果没有 -回溯并尝试另一个方向。
