Я не понимаю A* Pathfinding

Насколько я понимаю:

Добавить текущий узел в закрытый список.

Найдите узлы, соседние с текущим узлом, и, если они не являются непроходимыми узлами и не находятся в закрытом списке, добавьте этот узел в открытый список с родителем, являющимся текущим узлом, и вычислите значения F, G и H. Если узел уже существует в открытом списке, проверьте, приведет ли переход к этому узлу через текущий узел к более низкому значению G — если да, сделайте родительский узел этого узла текущим узлом.

Найдите узел в открытом списке с самым высоким значением F и сделайте текущий узел этим узлом.

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

Итак, это имеет смысл для моего мозга, но когда я на самом деле пробую это на диаграмме, я думаю, что я не понимаю это правильно.

(На рисунке ниже) Идите вниз от начальной зеленой плитки, той, что имеет значение F 60. Она находится в открытом списке и имеет более низкое значение F, чем правая нижняя 74. Почему выбрано 74 вместо 60?

A*


algorithm path-finding a-star
person apscience    schedule 18.06.2011    source источник

Ответы (2)


arrow_upward
4
arrow_downward

На мой взгляд, вам следует взглянуть на страницы А* Амита. Они действительно отлично объясняют, как работает алгоритм и как заставить его работать.

Что касается вашего случая, на диаграмме показана оценка G для первого узла в открытом списке. Когда вы смотрите на веб-сайт, вся диаграмма строится сначала для оценки первого узла, и автор показывает, что первым лучшим узлом является узел справа. Затем для продвижения вперед используется оценка G, основанная на оценке текущего узла и стоимости перемещения следующего узла, что не показано на диаграмме.

Хотя на сайте написано:

И последний квадрат, расположенный непосредственно слева от текущего квадрата, проверяется, чтобы увидеть, не станет ли показатель G ниже, если вы пройдете через текущий квадрат, чтобы добраться туда. Нет игральных костей.

Его показатель G на самом деле будет 24 (14 (текущая стоимость) + 10 (стоимость горизонтального перемещения)), точно так же, как квадрат под ним, если я правильно помню.

person Jesse Emond    schedule 18.06.2011
comment
Хм? Думаю теперь разобрался. Оценка 60 F является самой низкой, поэтому она становится текущим узлом. Затем он добавляется в закрытый список. Это просто продолжается до тех пор, пока все узлы ниже 74 не будут в закрытом списке, а затем делает узел с 74 текущим квадратом. Это так, потому что дальше по странице вы можете видеть, что G-счет одного второго зеленого узла изменился, так что это должно означать, что 60-й узел стал текущим квадратом. - person apscience; 18.06.2011
comment
@gladoscc: да ладно, мои знания A* заржавели. =/ Но все же, я бы посоветовал вам прочитать всю серию страниц Амита, они очень помогут. - person Jesse Emond; 18.06.2011

arrow_upward
0
arrow_downward

Причина, по которой вы не переходите на клетку со значением F 60, заключается в том, что она находится в «закрытом списке». Тогда как поля со значением F 88 и 74 находятся в «открытом списке» и могут быть изучены для следующего хода.

person badnmad    schedule 18.06.2011