Является ли Greedy лучшим в первом поиске отличным от поиска Best-first?

Терминологический вопрос - это самый жалкий поисковик, отличный от поиска Best-first?

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

Я понимаю, что Greedy BFS - это просто BFS, где "лучший node от OPEN" в алгоритме википедии - это эвристическая функция, которую вычисляют для node. Итак, реализуем это:

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 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

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

ИЗМЕНИТЬ: Комментарий к анонимному ответу:

Таким образом, по существу жадный BFS не нуждается в "ОТКРЫТОМ списке" и должен основывать свои решения только на текущем node? Является ли этот алгоритм 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 successors
5. Set BEST successor as CURRENT and go to 2.

Ответы

Ответ 1

"В лучшем случае" можно было бы пересмотреть решение, тогда как в жадном алгоритме решения должны быть окончательными и не пересмотрены.

Например, A * -поиск - лучший поиск, однако он не жадный.

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

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

Ответ 2

BFS - это экземпляр алгоритмов поиска дерева и графа, в которых a node выбран для расширения на основе оценочной функции f(n).

Обычно для расширения выбирается node с самой низкой оценкой, потому что оценка измеряет расстояние до цели.

BFS использует приоритетную очередь.

Greedy BFS пытается расширить node, который ближе всего к цели, на том основании, что это приводит к быстрому решению. Таким образом, он оценивает узлы, просто используя эвристическую функцию f(n) = h(n).

Ответ 3

Насколько я понимаю, Best-first Search - это только коллективное имя конкретной поисковой техники, в которой вы используете эвристическую функцию оценки h (n). Таким образом, A * и Greedy Best-first Search также попадают в эту категорию.

Пожалуйста, поправьте меня, если я ошибаюсь!