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

Question

我正在解决leetcode.com上的单词搜索问题：

给定一个二维板和一个单词，找出这个单词是否存在于网格中。

我用在线帮助编写的解决方案如下：

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”开头的单词。Backtracker会立即用“jacq”、“jacd”和“jacf”修剪分支，例如，通过查阅从字典中构建的辅助trie数据结构。在某个时候，甚至DFS也会回溯，但只有在它没有地方去的时候--也就是说，周围的所有信件都已经被访问过了。

总之，在您的示例中，传统的DFS会对每个节点盲目地检查所有邻居节点，直到它找到目标字或直到它的所有邻居都被访问为止，它只会回溯。另一方面，Backtracker不断检查我们是否在“正确的轨道上”，执行此操作的代码中的关键行是：

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