Отличается ли жадный алгоритм поиска «лучший первый» от алгоритма поиска «лучший первый»?

Question

Отличается ли жадный алгоритм поиска с лучшим первым от алгоритма поиска с лучшим первым?

На вики-странице есть отдельный параграф о Greedy BFS, но оннемного неясно.

Насколько я понимаю, Greedy BFS - это просто BFS, где «лучший узел из OPEN» в алгоритме Википедии - это эвристическая функция, которую каждый вычисляет для узла.Таким образом, реализация этого:

OPEN = [initial state]
CLOSED = []
while OPEN is not empty
do
 1. Remove the best node from OPEN, call it n, add it to CLOSED.
 2. If n is the goal state, backtrace path to n (through recorded parents) and return path.
 3. Create n's successors.
 4. For each successor do:
   a. If it is not in CLOSED: evaluate it, add it to OPEN, and record its parent.
   b. Otherwise: change recorded parent if this new path is better than previous one.
done

с "лучшим узлом из ОТКРЫТОГО", являющимся эвристической функцией, оценивающей, насколько близко узел к цели, на самом деле является Greedy BFS.Я прав?

РЕДАКТИРОВАТЬ: Прокомментировать ответ Anonymouse:

Таким образом, по сути, жадная BFS не нуждается в «открытом списке» и должна основывать свои решения только натекущий узел?Является ли этот алгоритм GBFS:

1. Set START as CURRENT node
2. Add CURRENT to Path [and optinally, to CLOSED?]
3. If CURRENT is GOAL, exit
4. Evaluate CURRENT's successors
5. Set BEST successor as CURRENT and go to 2.

Answer 1

«Лучший первым» может позволить пересмотреть решение, тогда как в жадном алгоритме решения должны быть окончательными, а не пересматриваться.

Например, A * -поиск - это поиск в первую очередь, но он не жадный.

Однако обратите внимание, что эти термины не всегда используются с одинаковыми определениями. «Жадность» обычно означает, что решение никогда не пересматривается, и в конечном итоге он принимает неоптимальные решения в пользу улучшений во время выполнения. Тем не менее, держу пари, что вы найдете ситуации, в которых «жадность» используется для комбинации «лучший сначала + первая глубина», как в «попытаться расширить лучший следующий шаг, пока мы не попадем в тупик, а затем вернуться к предыдущему шагу и продолжить со следующим лучшим там "(который я назвал бы" приоритетной глубиной сначала ").

Кроме того, это зависит от того, о каком уровне абстракции вы говорите. А * не жаден в «построении пути». Это хорошо, если держать большой набор открытых путей вокруг. Однако он жаден в «расширении пространства поиска» в направлении истинно кратчайшего пути.

Answer 2

BFS является экземпляром дерева поиска и графика поиска алгоритмов , в котором узел выбран для расширения на основе функции оценки f(n) = g(n) + h(n), гдеg(n) - это длина пути от корня до n, а h(n) - это оценка длины пути от n до целевого узла.В алгоритме BFS для расширения выбирается узел с наименьшей оценкой (т. Е. С наименьшим f(n)).

Жадная BFS использует следующую функцию оценки f(n) = h(n), которая является просто эвристической функцией h(n),который оценивает близость n к цели.Следовательно, жадная BFS пытается расширить узел, который считается наиболее близким к цели, без учета ранее собранных знаний (т. Е. g(n)).

Подводя итог, основное различие между ними (аналогично)методы поиска - это функция оценки.

В качестве примечания, алгоритм A * - это алгоритм поиска наилучшего первого, в котором эвристическая функция h является допустимой эвристикой (т. е. h всегда является недооценкойсовершенной эвристической функции h*, для всех n).A * не является ужасным алгоритмом BFS, потому что его оценочная функция равна f(n) = g(n) + h(n).

Answer 3

Насколько я понимаю, «поиск в первую очередь» - это всего лишь собирательное название определенного метода поиска, в котором вы используете эвристическую функцию оценки h (n).Итак, A * и жадный поиск по принципу «лучший первый» - это алгоритмы, попадающие в эту категорию.