c++ - 使用回溯(而不是 DFS)背后的直觉

Question

我正在解决 Word Search LeetCode.com 上的问题:

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.

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

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

Q: My question is simple - why are we using a backtracking approach and not just a conventional DFS?

因为回溯在解决这类问题上比普通的 DFS 效率高得多。

DFS 和回溯之间的区别很微妙，但我们可以这样总结:DFS 是一种搜索图的技术，而回溯是一种问题解决技术 (由DFS + pruning组成，这样的程序被称为backtrackers)。因此，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;