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

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

На странице вики есть отдельный абзац о Жадный BFS но немного непонятно.

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

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.

21
задан Alex 30 October 2018 в 09:25
поделиться