Отличается ли жадный алгоритм поиска по первому наилучшему от алгоритма поиска по первому наилучшему?
На странице вики есть отдельный абзац о Жадный 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.