Объясните BFS и DFS с точки зрения возврата - PullRequest
Новая
       39

Объясните BFS и DFS с точки зрения возврата

7 голосов
/ 25 апреля 2010

Википедия о глубине Первый поиск:

Поиск в глубину (DFS) алгоритм обхода или поиска дерево, древовидная структура или граф. Один начинается с корня (выбор некоторых узел как корень в графе) и исследует как можно дальше вдоль каждая ветвь перед возвратом.

Так что же такое поиск в ширину?

"алгоритм, который выбирает стартовый узел, проверяет все узлы возвраты , выбирает кратчайший путь, выбирает соседние узлы backtracks , выбрал кратчайший путь, наконец находит оптимальный путь из-за прохождение каждого пути из-за непрерывного возвраты.

Regex find Обрезка - возвращение?

Термин backtracking сбивает с толку из-за его разнообразия использования. UNIX find обрезка SO-пользователя объяснила с возвратом. Regex Buddy использует термин «катастрофическое возвращение», если вы не ограничиваете область действия своих регулярных выражений. Кажется, это слишком широко используемый общий термин. Итак:

  1. Как вы определяете «возвратный путь» специально для теории графов?
  2. Что такое "возврат" при поиске по ширине и поиску по глубине?

[Добавлено]

Хорошие определения об отслеживании и примеры

  1. Метод грубой силы
  2. Изобретенный Столлманом (?) Термин "обратный контроль в зависимости от зависимостей"
  3. Возврат и регулярное выражение пример
  4. Определение поиска в глубину.

1 Ответ

19 голосов
/ 01 июля 2010

Путаница возникает из-за того, что при поиске происходит обратное отслеживание, но оно также относится к конкретной методике решения проблем, при которой выполняется обратное отслеживание. Такие программы называются backtrackers.

Представьте себе, что вы проезжаете по соседству, всегда берете первый поворот, который видите (предположим, что петель нет), пока не попадаете в тупик, после чего вы возвращаетесь на перекресток следующей не посещенной улицы. Это «первый» вид возврата, и он примерно эквивалентен разговорному употреблению слова.

Более конкретное использование относится к стратегии решения проблем, которая похожа на поиск в глубину, но возвращает назад, когда осознает, что не стоит продолжать поиск по некоторому поддереву.

Другими словами, наивный DFS слепо посещает каждый узел, пока не достигнет цели. Да, это "возврат" на листовых узлах. Но backtracker также возвращает на бесполезные ветви. Одним из примеров является поиск слов на доске Boggle. Каждая плитка окружена 8 другими, поэтому дерево огромно, а наивная DFS может занять слишком много времени. Но когда мы видим комбинацию типа «ZZQ», мы можем безопасно прекратить поиск с этого момента, поскольку добавление большего количества букв не сделает это словом.

Мне нравятся эти лекции профессора Джулии Зеленски. Она решает 8 королев, загадку судоку и загадку подстановки чисел с помощью возврата, и все это прекрасно анимировано. Программирование абстракций, лекция 10 Программирование абстракций, лекция 11

Дерево - это граф, в котором любые две вершины имеют только один путь между ними. Это исключает возможность циклов. При поиске на графике у вас все равно будет какая-то логика для устранения циклов, поэтому поведение остается тем же. Кроме того, с ориентированным графом вы не можете следовать за ребрами в «неправильном» направлении.

Из того, что я могу сказать, в статье Столлмана они разработали логическую систему, которая не просто говорит "да" или "нет" в запросе, но фактически предлагает исправления для неправильных запросов путем внесения наименьшего числа изменений. Вы можете увидеть, где может появиться первое определение возврата.

...