Сравните разные алгоритмы поиска

Question

Чем похожи DFS и Best-first search? Чем похожи BFS и Best-first?

Для меня, чтобы лучше описать, как схожи DFS и BestFS, было бы легче указать разницу, заключающуюся в том, что в BestFS мы выбрали следующим, чтобы расширить тот, который кажется наиболее близким к цели, используя функцию heuristi. Почти во всех других отношениях оба из лучших и DFS похожи.

Однако мне трудно найти сходство между BFS и BestFS

Answer 1

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

С Depth First search , если вы натолкнулись на ветку, вы бы взяли эту ветку, а затем возьмите другую ветку, другую и другую, пока не дойдете до листа.

С Ширина первый поиск (обратите внимание, я не сказал «лучший сначала» здесь), когда вы встречаете новую ветку, вы добавляете ее в очередь, к которой можно вернуться позже, пока вы не найдете все ветви на текущем уровне. Обычно, когда люди говорят «BFS», они имеют в виду Ширина Первый поиск , а не Лучший Первый.

Так что насчет Best первый поиск , как вы и просили? Хорошо, предположим, что вы выполняете поиск в глубину, и вы наткнулись на две ветви. С DFS, вы просто выбираете первый каждый раз, позже вы вернетесь и выберете другой.

С помощью Лучший первый поиск вы выбираете ветвь с наибольшим эвристическим значением, основываясь на некоторой эвристике, которую вы используете, чтобы помочь угадать лучший путь. Таким образом, поиск Best First - это type of Depth first search.

Википедия очень полезна для подобных вопросов, кстати.

Answer 2

Best First Search - это тип информированного поиска, который хорошо подходит для сценариев, в которых известна некоторая информация о пространстве состояний, которое вы ищете. Это знакомство с пространством состояний или системой, в которой вы работаете, помогает в разработке эвристики, которая выбирает лучший узел на каждом этапе поиска. Короче говоря, Best First Search использует парадигму Жадности для достижения цели, то есть цели поиска.

Поиск в глубину и поиск в ширину - это неинформированные методы поиска, которые удобны, когда вы ничего не знаете о системе, с которой имеете дело. Они имеют свои собственные компромиссы (между собой) с точки зрения памяти и гарантируют, что найдут решение (если оно существует). Вы можете проверить детали в Wiki .

Я не вижу большого сходства между неинформированным поиском и информированными методами поиска, за исключением того, что они помогают решить проблему поиска. Другим аспектом, на котором можно утверждать сходство, является то, завершен ли поиск (метод поиска вызывается завершенным, когда он возвращает решение, когда оно существует) и оптимальный (метод поиска является оптимальным, когда он возвращает решение с минимальными затратами при наличии решения) .

Поиск в ширину - полный и оптимальный (если все ребра имеют удельную стоимость)

Поиск в глубину - полный (для конечного дерева поиска) и неоптимальный

Лучший первый поиск - полный и оптимальный

Ключ в том, чтобы знать, какой использовать в какой ситуации.

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

ура