Алгоритм Star наиболее эффективный путь

Question

Я пробовал писать Звездный алгоритм с диагоналями и эвристикой прямого расстояния между двумя точками. Однако путь не самый короткий в таком случае, как этот

Переход (2,2) -> (3,2) -> (4,2) -> (5,2) будет быстрее , но он решил разрезать.

Я не могу понять, что случилось с моим пониманием, потому что так оно и будет работать, когда я тоже это думаю.

Мое понимание:

1. Запускает из (1,1) находит (2,2), чтобы быть лучшими
2. находки (3,3), чтобы быть лучше, находит (4,3) будет лучше, так как вы не можете вырезать углы
3. Находит (5,3) лучше, но вычисляет значение f (5,2) как X
4. Невозможно перейти к (6,2) и вычислить f (5,2) при Y> X, поэтому путь возвращается к (4,3)
5. Поскольку (5,3) больше не находится в открытом наборе, выбирает следующий лучший (5,2)
6. Остальная часть пути в порядке, ничего не происходит, поскольку «мертвых концов» не было встречено.

То, что должно было осознать, состоит в том, что f (5,2) ниже (4,2), которое ниже (3,2), которое никогда не рассчитывается из-за того, что оно выбрало (3,3)

Что именно не так с этим?

Редактировать: Шаг стоимость 1 для горизонтального/вертикального и SQRT (2) для диагоналей

Answer 1

Благодаря Генри в комментариях, рассуждение выключено, потому что (4,3) -> (5,2) будет имеют более высокое значение f, чем (2,2) -> (3,2), поэтому он должен вместо этого опускаться (3,2)

IE следующий узел для оценки выбирается из списка отсортированных открытых узлов, а не списка узлов с группами значений, отсортированных при вводе (а не в стек с отсортированным, добавленным к нему)