使用回溯（而不是 DFS）背后的直觉

我正在解决单词搜索 https://leetcode.com/problems/word-search/description/LeetCode.com 上的问题：

给定一个 2D 板和一个单词，查找该单词是否存在于网格中。

该单词可以由顺序相邻单元格的字母构成，其中“相邻”单元格是水平或垂直相邻的单元格。同一字母单元不得使用多次。

我根据网上帮助写的解决方案如下：

class Solution {
public:
    
    //compare this with Max Area of Island:
    //they 'look' similar, but this one uses a backtracking approach since we retract when we don't find a solution
    //In case of Max Area Of Island, we are not 'coming back' - technically we do come back due to recursion, but we don't track     
    //that since we don't acutally intend to do anything - we are just counting the 1s.
    
    bool exist(vector<vector<char>>& board, string& word) {
        if(board.empty()) return false;
        
        for(int i=0; i<board.size(); i++) {
            for(int j=0; j<board[0].size(); j++) {
                //if(word[0] == board[i][j])
                    if(existUtil(board, word, i, j, 0))    //matching the word[i][j] with 0th character of word
                        return true;
            }
        }
        
        return false;
    }
    
    bool existUtil(vector<vector<char>>& board, string& word, int i, int j, int match) {
        if(match==word.size()) return true;
        if(i<0 || i>=board.size() || j<0 || j>=board[0].size()) return false;
        if(board[i][j]!=word[match]) return false;
        
        board[i][j] = '*';
        bool ans = existUtil(board, word, i+1, j, match+1) || //[i+1,j]
               existUtil(board, word, i-1, j, match+1) || // [i,j+1]
               existUtil(board, word, i, j+1, match+1) || // [i-1,j]
               existUtil(board, word, i, j-1, match+1);   // [i,j-1]
        board[i][j] = word[match];
        
        return ans;
    }
};

我的问题很简单 - 为什么我们使用回溯方法而不仅仅是传统的 DFS？与我们所做的非常相似，我们可以从每个字符开始并执行 DFS 以确定我们是否可以找到目标单词。但我们并没有这样做，为什么呢？

我想了很多，并得出了以下推理，但我不确定 - 我们使用回溯方法是因为同一字母单元不得使用多次。因此，当我们进行回溯时，我们用“*”替换原始字符，然后当我们回来时重新替换它。但这感觉不太对，因为我们本可以使用visited矩阵代替。

Q:我的问题很简单 - 为什么我们使用回溯方法而不仅仅是传统的 DFS？

因为回溯对于解决此类问题比普通的 DFS 更有效。

DFS 和回溯之间的区别很微妙，但我们可以这样总结：DFS 是搜索图的技术，而回溯是问题解决技术（其中包括DFS+剪枝，这样的程序称为回溯器）。因此，DFS 会访问每个节点，直到找到所需的值（在您的情况下为目标单词），而回溯则更智能 - 当确定在那里找不到目标单词时，它甚至不会访问特定分支。

想象一下，您有一本包含所有可能单词的字典，并在棋盘上搜索以查找棋盘上存在的所有单词（Boggle 游戏）。您开始遍历棋盘并按顺序偶然发现字母“J”、“A”、“C”，因此当前前缀是“JAC”。伟大的。让我们看看字母“C”的邻居，例如它们是“A”、“Q”、“D”、“F”。普通的 DFS 会做什么？它会跳过“A”，因为它来自该节点到“C”，但它会盲目地访问其余每个节点，希望找到一些单词，即使我们知道没有以“JACQ”、“JACD”开头的单词”和“JACF”。 Backtracker 将立即修剪带有“JACQ”、“JACD”和“JACF”的分支，例如查阅从字典构建的辅助特里数据结构。在某些时候，即使 DFS 也会回溯，但只有当它无处可去时——即所有周围的字母都已被访问过。

总而言之，在您的示例中，传统的 DFS 将对每个节点盲目检查所有邻居节点，直到找到目标单词或访问其所有邻居，然后才会回溯。另一方面，回溯器不断检查我们是否处于“正确的轨道”上，而执行此操作的代码中的关键行是：

if (board[i][j] != word[match]) return false;