为什么这被称为回溯算法？

Question

我在维基百科和谷歌上查找过，但我无法理解“回溯算法”的含义。我从《破解面试》中看到了这个解决方案，并想知道为什么它是一种回溯算法？

- Elad Benda2

---

这段代码会因违反Java编程风格而降低面试表现。 - Display Name

因为一开始你在第一个房间里检查抽屉，但是没有找到，所以你原路返回到下一个房间检查抽屉。这也被称为试错法。 - Khaled.K

Answer 1

回溯法（Backtracking）是一种递归形式的算法。

该基于布尔值的算法面临选择，然后进行选择，并在初始选择后呈现一组新的选择。

---

从概念上讲，您从树的根部开始；树可能有一些好的叶子和一些坏的叶子，尽管叶子可能全部是好的或全部是坏的。您想到达一个好的叶子。从根节点开始，每个节点选择其要移动到的一个子节点，一直保持下去，直到到达叶子节点。（见下图）

示例说明：

1. 从根节点开始，你的选择是A和B。你选择A。
2. 在A处，你的选择是C和D。你选择C。
3. C是不好的。返回A。
4. 在A处，你已经尝试过C了，它失败了。尝试D。
5. D是不好的。返回A。
6. 在A处，你没有可尝试的选项了。返回根节点。
7. 在根节点，你已经尝试过A。尝试B。
8. 在B处，你的选择是E和F。尝试E。
9. E是好的。恭喜你！

来源：upenn.edu

- Josef E.

---

这是一个很棒的图解！ - Giovanni Botta

你甚至不尝试 F？这只适用于寻找一个好结果的算法吗？ - Elad Benda2

在这个例子中，本质上是递归/枚举；可以修改以查找所有好的叶子。但在这种情况下，我们只寻找一个（第一个被访问的）。@user1065869 - Josef E.

这应该是被接受的答案，因为它涉及（并使用）单词“back”。 - WebViewer

Answer 2

“回溯”是在枚举算法中出现的术语。

您构建了一个“解决方案”（即，每个变量都被分配了一个值的结构）。

然而，在构建过程中，可能会意识到该解决方案不成功（不满足某些约束条件），然后您需要回溯：撤消对变量赋值的某些操作以重新分配它们的值。

---

例子：

根据您的示例，您希望在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
....

- Willem Van Onsem

---

这只适用于寻找一个好结果的算法吗？ - Elad Benda2

有时候你可能对所有的解决方案感兴趣，或者只对“最好”的五个解决方案感兴趣（如果你可以比较两个解决方案的话）。但是从那一刻起，当你需要“摧毁”之前构建的一部分以重新分配变量时，这就被称为回溯算法。 - Willem Van Onsem

Answer 3

事实上，“回溯”一词在“回溯法”中有时会让人感到困惑，因为在解决经典的N皇后问题时，回溯解决方案“继续向前走”：

/**
 * Given *starting* row, try all columns.
 * Recurse into subsequent rows if can put.
 * When reached last row (stopper), increment count if put successfully.
 * 
 * By recursing into all rows (of a given single column), an entire placement is tried.
 * Backtracking is the avoidance of recursion as soon as "cannot put"...  
 *    (eliminating current col's placement and proceeding to the next col).
 */
int countQueenPlacements(int row) {     // queen# is also queen's row (y axis)
    int count = 0;
    for (int col=1; col<=N; col++) {    // try all columns for each row
        if (canPutQueen(col, row)) {
            putQueen(col, row);
            count += (row == N) ? print(board, ++solutionNum) : countQueenPlacements(row+1);
        }
    }
    return count;   
}

请注意，我的评论将回溯定义为尽快避免递归，即“无法放置”--但这并不完全正确。在此解决方案中，回溯也可能意味着一旦找到适当的放置位置，递归栈就会展开（或回溯）。

- WebViewer

Answer 4

来自维基百科：

回溯法是一种用于找到某些计算问题的所有（或某些）解的通用算法，它逐步构建解的候选并放弃每个部分候选c（“回溯”），只要它确定c不可能完成为有效的解。

回溯法很容易作为递归算法实现。您通过寻找大小为n-1的解决方案来寻找大小n问题的解决方案等等。如果小尺寸的解决方案不起作用，则将其丢弃。

基本上，上面的代码是在做什么：在基本情况下返回true，否则它会'尝试'右路径或左路径，丢弃不起作用的解决方案。

由于上面的代码是递归的，可能不清楚“回溯”何时发挥作用，但算法实际上是从部分解构建解决方案，其中最小可能的解决方案在您的示例中在第5行处理。非递归版本的算法必须从最小解开始构建。

- Giovanni Botta

Answer 5

我不明白"回溯算法"是什么意思。

当一个算法尝试一种解决方案，失败后返回到更简单的解决方案作为新尝试的基础时，它被称为"回溯"算法。

在这个实现中，

current_path.remove(p)

当当前路径不成功时，可以返回沿着路径，以便调用者可以尝试导致 current_path 的路径的不同变体。

- Mike Samuel

Answer 6

回溯法基本上意味着尝试所有可能的选项。这通常是解决问题的天真、低效的方法。

在您的示例解决方案中，正是这样做的 - 您只需递归地尝试所有可能的路径： 您尝试每个可能的方向；如果找到成功的路径 - 很好。如果没有 - 回溯并尝试另一个方向。

- Jenian

---

不，它不会。如果你让通常使用回溯的Prolog来解决x=2，y=x的问题，它不会尝试所有x或y的值并只返回值为2的结果。 - Pete Kirkham

@Jenian是正确的：“回溯是一种算法技术，其目标是使用暴力方法获取问题的所有解决方案。它包括逐步构建所有解决方案的集合。由于问题会有约束条件，因此未能满足这些条件的解决方案将被删除。” - WebViewer