Объясните BFS и DFS с точки зрения отслеживания в обратном порядке
Википедия о поиске в глубину:
Поиск в глубину (DFS) является алгоритмом для того, чтобы пересечь или искать дерево, древовидную структуру или график. Каждый запускает в корне (выбирающий некоторый узел как корень в случае графика) и исследует в максимально возможной степени вдоль каждого ответвления перед отслеживанием в обратном порядке.
Таким образом, что такое Поиск в ширину?
"алгоритм, которые выбирают стартовый узел, проверяет все отслеживание в обратном порядке узлов, выбирает кратчайший путь, выбрал соседнее отслеживание в обратном порядке узлов, выбрал кратчайший путь, наконец находит оптимальный путь из-за пересечения каждого пути из-за непрерывного отслеживания в обратном порядке.
Regex findсокращение - отслеживание в обратном порядке?
Термин отслеживание в обратном порядке путает из-за его разнообразия использования. UNIX find сокращение ТАКИМ-ОБРАЗОМ-ПОЛЬЗОВАТЕЛЯ объяснило с отслеживанием в обратном порядке. Regex Buddy использует термин "катастрофическое отслеживание в обратном порядке", если Вы не ограничиваете объем своего Regexes. Это, кажется, слишком широко используемое обобщающее понятие. Так:
- Как Вы определяете "отслеживание в обратном порядке" специально для Теории графов?
- Что "отслеживает в обратном порядке" в Поиске в ширину и Поиске в глубину?
[Добавленный]
Хорошие определения об отслеживании в обратном порядке и примерах
- Метод "В лоб"
- Изобретенный термин киоскера (?) "откат с учетом зависимостей"
- Отслеживание в обратном порядке и regex пример
- Определение Поиска в глубину.
1 ответ
Путаница возникает из-за того, что обратное отслеживание - это то, что происходит во время поиска, но оно также относится к особой технике решения проблем, при которой выполняется много обратного отслеживания. Такие программы называются бэктрекерами.
Представьте, что вы едете в район, всегда выбирая первый поворот, который видите (предположим, что нет петель), пока не попадаете в тупик, после чего вы едете обратно к перекрестку со следующей не посещаемой улицей. Это «первый» вид поиска с возвратом, и он примерно эквивалентен разговорной речи.
Более конкретное использование относится к стратегии решения проблем, которая похожа на поиск в глубину, но возвращает откат, когда понимает, что не стоит продолжать движение вниз по некоторому поддереву.
Другими словами, наивная DFS слепо посещает каждый узел, пока не достигнет цели. Да, он выполняет «возврат» на листовых узлах. Но средство отслеживания также выполняет возврат по бесполезным ветвям. Один из примеров - поиск слов на доске Boggle. Каждая плитка окружена 8 другими, поэтому дерево огромно, и наивная DFS может занять слишком много времени. Но когда мы видим такую комбинацию, как «ZZQ», мы можем спокойно прекратить поиск с этого места, поскольку добавление дополнительных букв не сделает это слово.
Мне нравятся эти лекции профессора Юлии Зеленски. Она решает 8 ферзей, головоломку судоку и головоломку с заменой чисел с помощью поиска с возвратом, и все это красиво анимировано. Абстракции программирования, лекция 10 Абстракции программирования, лекция 11
Дерево - это граф, в котором любые две вершины имеют только один путь между ними. Это исключает возможность циклов. Когда вы ищете график, у вас, как правило, есть логика для исключения циклов, поэтому поведение такое же. Кроме того, с ориентированным графом вы не можете следовать за ребрами в «неправильном» направлении.
Насколько я могу судить, в статье Столлмана они разработали логическую систему, которая не просто говорит «да» или «нет» на запрос, но фактически предлагает исправления для неправильных запросов, внося минимальное количество изменений. Вы можете увидеть, где может сыграть роль первое определение поиска с возвратом.