主题：使用回溯（而不仅仅是递归DFS）后面的直觉

Question

首先，我不是要问the difference between a car and a DeLorean。所以，我正在解决this LeetCode问题：

给定一个2D板和一个单词，找出该单词是否存在于网格中。该单词可以由顺序相邻的单元的字母构成，其中“相邻”单元是水平或垂直相邻的单元。相同的字母单元格不得多次使用。

董事会= [ [ 'A'， 'B'， 'C'， 'E']， [ 'S'， 'F'， 'C'， 'S']， [ 'A'， 'd'， 'E'， 'E'] ]

给定word =“ABCCED”，返回true。

highly upvoted solution如下：

public class Solution {
public boolean exist(char[][] board, String word) {
    for(int i = 0; i < board.length; i++)
        for(int j = 0; j < board[0].length; j++){
            if(exist(board, i, j, word, 0))
                return true;
        }
    return false;
}
private boolean exist(char[][] board, int i, int j, String word, int ind){
    if(ind == word.length()) return true;
    if(i > board.length-1 || i <0 || j<0 || j >board[0].length-1 || board[i][j]!=word.charAt(ind))
        return false;
    board[i][j]='*';
    boolean result =    exist(board, i-1, j, word, ind+1) ||
                        exist(board, i, j-1, word, ind+1) ||
                        exist(board, i, j+1, word, ind+1) ||
                        exist(board, i+1, j, word, ind+1);
    board[i][j] = word.charAt(ind);     //--> why?
    return result;
}

我的问题是 - 对于使用正常的递归DFS而言，使用回溯算法背后的直觉是什么？在使用递归DFS时，我只是将节点标记为已访问，然后转移到其邻居（从而计算出ABCCED是一个有效路径）。为什么我必须回溯（上面的代码中的注释行）才能意识到这条路径是否存在？

谢谢！

编辑：问我问题的其他方式就是这样：为什么我们不从最左边的单元格A开始，并开始使用沿途设置的visited访问所有邻居来标记访问过的节点？在下一次迭代中，我们可以从靠近最左边的A - B的单元格开始，使用新的visited集来访问所有邻居以标记访问节点，依此类推？为什么要使用回溯？

Answer 1

深度优先搜索是一种回溯算法。递归的本质是回溯机制本身。如果路径不是好路径，则在深入树之前返回false。这是你的回溯：

if(i > board.length-1 || i <0 || j<0 || j >board[0].length-1 || board[i][j]!=word.charAt(ind))
    return false;

这条线

board[i][j] = word.charAt(ind);

仅用于将节点重置为其原始值，并允许它在其他相邻路径中使用，如Bakon Jarser在问题帖子上发表评论。

你可以检查真正的快速first paragraph和this post。

希望这有帮助。

Answer 2

假设你在这块板上寻找ABCBDE这个词：

ABD
BCE

假设与您提供的源代码中的邻居探索顺序相同，您的DFS将首先尝试右 - >向下 - >左路径，因此您的visited集将包含最左边的2x2方块，您将无法找到解决方案。