java - 主题 : Intuition behind using backtracking (and not just recursive DFS)

Question

首先，我不是想问 the difference between a car and a DeLorean .所以，我正在解决 this LeetCode 题目:

Given a 2D board and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

board =
[
    ['A','B','C','E'],
    ['S','F','C','S'],
    ['A','D','E','E']
]

Given word = "ABCCED", return true.

A 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 开始，然后使用 开始访问它的所有邻居code>visited设置沿途标记访问过的节点？在下一次迭代中，我们可以从与最左端 A - B 相邻的单元格开始，使用新的 visited 设置访问其所有邻居标记访问过的节点等等？为什么要使用回溯？

Answer 1

深度优先搜索是一种回溯算法。 递归的本质是回溯机制本身。如果路径不是好路径，它会在进入树的更深处之前返回错误。 这是你的回溯:

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 .

希望这对您有所帮助。