Мне нужна помощь в понимании алгоритма треугольника A * (TA *), который описан Демьеном в его статье « Эффективное нахождение путей на основе триангуляции» на страницах 76–81.
Он описывает, как адаптировать обычный алгоритм A * для триангуляции, чтобы искать другие, возможно, более оптимальные пути, даже после того, как конечный узел достигнут / расширен. Обычный A * останавливается, когда последний узел раскрывается, но это не всегда лучший путь при использовании в триангулированном графе. Это именно та проблема, которая у меня возникла.
Проблема проиллюстрирована на странице 78, рисунок 5.4:
Я понимаю, как рассчитать значения g и h, представленные в статье (стр. 80).
И я думаю, что условие остановки поиска:
if (currentNode.fCost > shortestDistanceFound)
{
// stop
break;
}
где currentNode - это поисковый узел, извлеченный из открытого списка (приоритетная очередь), который имеет наименьшую f-оценку. shorttestDistanceFound - это фактическое расстояние до самого короткого пути, найденного до сих пор.
Но как исключить ранее найденные пути из будущих поисков? Потому что, если я сделаю поиск снова, он, очевидно, найдет тот же путь. Сбросить закрытый список? Мне нужно что-то изменить, но я не знаю, что мне нужно изменить. В документе отсутствует псевдокод, так что это было бы полезно.
источник