Тема: Интуиция в использовании backtracking (а не только рекурсивной DFS). - PullRequest
Новая
       29

Тема: Интуиция в использовании backtracking (а не только рекурсивной DFS).

0 голосов
/ 04 апреля 2019

Для начала я не пытаюсь спросить разницу между автомобилем и делорианом .Итак, я решаю этот вопрос LeetCode:

Для данной двумерной доски и слова найдите, существует ли слово в сетке.Слово может быть составлено из букв последовательно смежных ячеек, где «соседние» ячейки - это те, которые соседствуют по горизонтали или вертикали.Одну и ту же буквенную ячейку нельзя использовать более одного раза.

board =
[
['A', 'B', 'C', 'E'],
['S ',' F ',' C ',' S '],
[' A ',' D ',' E ',' E ']
]

Даноword = "ABCCED", верните true.

A Высоко проголосованное решение выглядит следующим образом: 

public class Solution {
public boolean exist(char[][] board, String word) {
    for(int i = 0; i < board.length; i++)
        for(int j = 0; j < board[0].length; j++){
            if(exist(board, i, j, word, 0))
                return true;
        }
    return false;
}
private boolean exist(char[][] board, int i, int j, String word, int ind){
    if(ind == word.length()) return true;
    if(i > board.length-1 || i <0 || j<0 || j >board[0].length-1 || board[i][j]!=word.charAt(ind))
        return false;
    board[i][j]='*';
    boolean result =    exist(board, i-1, j, word, ind+1) ||
                        exist(board, i, j-1, word, ind+1) ||
                        exist(board, i, j+1, word, ind+1) ||
                        exist(board, i+1, j, word, ind+1);
    board[i][j] = word.charAt(ind);     //--> why?
    return result;
}

Мой вопрос - в чем заключалась интуицияиспользуя алгоритм обратного отслеживания для этого вопроса, в отличие от использования обычной рекурсивной DFS?При использовании рекурсивной DFS я бы просто пометил узлы как посещенные, а затем перешел к соседям (таким образом выяснив, ABCCED - правильный путь).Почему я должен backtrack (закомментированная строка в коде выше), чтобы понять, существует ли этот путь?

Спасибо!

Редактировать : Другой способзадавать мой вопрос следующим образом: почему бы нам не начать с самой верхней левой ячейки A и начать посещать всех ее соседей, используя visited, установленный по пути, чтобы отметить посещенные узлы?В следующей итерации мы могли бы начать с ячейки, смежной с самым верхним левым A - B, посетить всех ее соседей, используя новый набор visited для отметки посещенных узлов, и так далее?Зачем использовать возврат?

Ответы [ 2 ]

0 голосов
/ 05 апреля 2019

Допустим, вы ищете слово ABCBDE на этой доске: 

ABD
BCE

Предполагая тот же порядок исследования соседей, что и в предоставленном вами исходном коде, ваша DFS сначала попробует правильно> down-> left path, поэтому ваш набор visited будет содержать крайний левый квадрат 2x2, и вы не сможете найти решение.

0 голосов
/ 04 апреля 2019

Поиск в глубину - это алгоритм возврата.Природа рекурсивности - сам механизм возврата.Если путь не очень хороший, он возвращает ложь, прежде чем углубиться в дерево.Вот ваш ответ: 

if(i > board.length-1 || i <0 || j<0 || j >board[0].length-1 || board[i][j]!=word.charAt(ind))
    return false;

Строка 

board[i][j] = word.charAt(ind);

просто используется для сброса узла к его первоначальному значению и позволяет использовать его в другом смежном пути, как прокомментировал Бэкон Джарсерна вопросный пост.

Вы можете проверить очень быстро первый абзац и этот пост .

Надеюсь, что эта помощь.

...