Я внедрил и использовал A * несколько раз и думал, что знаю все, что нужно знать об A *…. Пока я не столкнулся с этим примером:
График состоит из 4 узлов и 6 направленных взвешенных ребер. Эвристика обозначена для каждого узла H=…. Эвристика явно допустима, поэтому я не вижу никаких проблем с этим.
Задача состоит в том, чтобы найти маршрут от старт до цель с минимальной общей стоимостью. Правильное решение - маршрут с краями 36 и 18.
Моя реализация A * выполняет следующие шаги (без каких-либо операций, связанных с закрытым списком):
- Начальный узел: {G = 0, H = 200, -> F = 200} и выбран как «текущий узел»
- Все его соседи добавлены в открытый список
= {{G=5, H=100, F=105}, {G=36, H=100, F=136}}.
- Выбран новый «текущий узел», который является узлом в открытом списке с наименьшим F, который является узлом с
F = 105, верхним узлом в изображении.
- Соседи этого узла добавляются в открытый список, который затем содержит элементы {{G = 36, H = 100, F = 136}, {G = 58, H = 0, F = 58}}.
- Снова выбран новый текущий узел, который является целевым узлом, поэтому алгоритм завершается и выбирается маршрут с затратами 5 и 53.
Таким образом, реализация дает неправильный результат. Что на этих шагах не должно было произойти?