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

Question

我正在 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矩阵来代替。

Answer 1

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

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

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

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

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

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