Разница между лучшим первым поиском и жадным лучшим первым поиском?

Question

Есть ли разница вообще? Мне сказали, что жадный выбирает child с самым высоким значением функции heuristi c, т.е. локально лучший преемник . Моя путаница заключается в том, что происходит в первом жадном алгоритме , который не отслеживает посещенные им узлы , встречает один и тот же узел по другому пути? Я нарисую проблему, чтобы изобразить ее четко:

Какой узел C будет расширяться алгоритмом жадного лучшего первого, когда он достигнет C через B, C (x) или C (y), и каким будет выходной путь? ABCG или ACG?

Примечание это дерево является графическим представлением оценки кратчайшего пути сетки , дочерние узлы являются действительными соседними узлами родительского узла в сетке.

Answer 1

Таким образом, это означает, что AB- C -G - это путь, который жадный лучше всего даст первым? Поскольку он будет рассматривать только дочерние элементы узла B для следующего выбора?

Да: строгий «жадный» алгоритм считает only лучшим краткосрочным выбором на каждом этапе. На первом этапе B дешевле, чем C, поэтому он начинается по этому пути. Отсюда он обрабатывает B как начальный узел. Самый дешевый шаг оттуда - к C, затем к G.

В отличие от этого, алгоритм «лучший в первую очередь», такой как A* или Dijkstra's, сделает некоторые заметки о самом дешевом общем пути. Все начинается с состояния (A, 0) - ничего не стоит добраться до A. Затем он генерирует ходы (AB, 2), (A C, 3) и (AD, лоты); он берет самый дешевый ход (AB, 2), но сохраняет остальные в списке. Теперь он генерирует ходы из B с общей стоимостью : (ABE, 7) и (AB C, 5). На данный момент он падает (AB C, 5), потому что есть известный более дешевый путь к C.

Теперь самый дешевый путь в списке (A C , 3), и алгоритм будет генерировать ходы оттуда: (ACG, 3 + неизвестно).

Достаточно ли для вас прояснения?

Answer 2

В общем, алгоритм называется «жадным», если он просто делает лучший локальный шаг и никогда не пересматривает решения. «Лучше всего сначала» - это какой-то исчерпывающий поиск, где вы упорядочиваете альтернативные шаги по некоторому heuristi c («звучит разумно, без гарантии») и пробуете их по порядку. Это имеет смысл только в том случае, если вы комбинируете с некоторым критерием отсечения, т. Е. У вас есть какой-то способ отсеять альтернативы, которые вы можете доказать , не дадут желаемого результата.

Проверьте, например, $ A ^ * $ (A-star) поиск.