使用回溯（而非DFS）背后的直觉 [英] Intuition behind using backtracking (and not DFS)
问题描述
我正在解决LeetCode.com上的单词搜索问题：
给出一个2D板和一个单词，找出单词是否存在于网格中。
该单词可以由顺序相邻的单元格的字母构成，其中相邻单元格是水平或垂直相邻的单元格。相同的字母单元不得重复使用。
我在在线帮助下编写的解决方案如下：
class解决方案{
public：
//将其与最大岛屿面积进行比较：
//它们的外观相似，但是此方法使用了回溯方法，因为当我们找不到解决方案时我们会缩回
//如果是岛屿最大面积，我们不会回归-从技术上讲，我们确实是由于递归而返回的，但是我们不会跟踪
//因为我们不打算做任何事情-我们只计算1。
布尔存在（vector& board，string& word）{
if（board.empty（））return false;
for（int i = 0; i
// if（word [0] == board [i] [j]）
if（existUtil（board，word，i，j，0））//匹配单词[i] [j]单词
的第0个字符返回true；
}
}
返回false；
}
bool existUtil（vector&char;& board，string& word，int i，int j，int match）{
if（match = = word.size（））返回true；
if（i< 0 || i&== board.size（）|| j< 0 || j&= board [0] .size（））返回false；
if（board [i] [j]！= word [match]）返回false；
董事会[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，以确定是否可以找到目标单词。但是我们为什么不这样做呢？
我对此进行了很多思考，并提出了以下理由，但我不确定-我们使用回溯方法是因为同一个字母单元不得重复使用。因此，当我们进行回溯时，我们用'*'替换原始字符，然后在返回时重新替换它。但这有点不对劲，因为我们可以使用访问的矩阵。
问：我的问题很简单-为什么我们要使用回溯方法，而不仅仅是常规的DFS？
因为回溯比普通的DFS更有效地解决此类问题。
DFS之间的区别回溯是微妙的，但我们可以这样总结：DFS是一种用于搜索图形的技术，而回溯是一种解决问题的技术（由 DFS组成+修剪，此类程序称为回溯程序）。因此，DFS会访问每个节点，直到找到所需的值（在您的情况下为目标单词）为止，而回溯更为智能-当确定在此处找不到目标单词时，它甚至不会访问特定的分支。 p>
假设您有一个词典，其中包含所有可能的单词，并在棋盘上搜索以找到棋盘上存在的所有单词（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]）返回false；
I am solving Word Search question on 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.
The solution which I wrote with online help is as follows:
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;
}
};
My question is simple - why are we using a backtracking approach and not just a conventional DFS? Pretty similar to what we have done, we could start at each character and do a DFS to determine if we could find the target word. But we are not doing so, why?
I thought a lot about it and came with the following reasoning, but I am not sure - we use a backtracking approach because of the same letter cell may not be used more than once. So, when we are do backtracking, we replace the original character with a '*' and then later re-substitute it when we come back. But this somehow does not feel right, because we could have used a visited matrix instead.
Q: My question is simple - why are we using a backtracking approach and not just a conventional DFS?
Because backtracking is far more efficient for solving this class of problems than the plain DFS.
The difference between DFS and backtracking is subtle, but we can summarize like this: DFS is a technique for searching a graph, while backtracking is a problem solving technique (which consists of DFS + pruning, such programs are called backtrackers). So, DFS visits each node until it finds the required value (in your case the target word), while backtracking is smarter - it doesn't even visit particular branches when it is certain that the target word would not be found there.
Imagine that you have a dictionary of all possible words and searching through the board to find all words that exist on the board (Boggle game). You start to traverse the board and stumble upon the letters 'J','A','C' in that order, so the current prefix is "JAC". Great. Let's look at the neighbors of the letter 'C', e.g. they are 'A', 'Q', 'D', 'F'. What would plain DFS do? It would skip 'A' because it came from that node to 'C', but it would then blindly visit each of the remaining nodes hoping to find some word, even though we know there are no words starting with "JACQ", "JACD" and "JACF". Backtracker would immediately prune branches with "JACQ", "JACD" and "JACF" by e.g. consulting an auxiliary trie data structure built from the dictionary. At some point even DFS would backtrack, but only when it does not have where to go - i.e. all surrounding letters have already been visited.
To conclude - in your example, the conventional DFS would for each node blindly check all neighbor nodes until it finds the target word or until all its neighbors are visited - it would only then backtrack. Backtracker on the other hand constantly checks whether we are on the "right track", and the key line in your code that performs this is:
if (board[i][j] != word[match]) return false;
这篇关于使用回溯（而非DFS）背后的直觉的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
