Алгоритм поиска пути триангуляции A * (TA *)

11

Мне нужна помощь в понимании алгоритма треугольника A * (TA *), который описан Демьеном в его статье « Эффективное нахождение путей на основе триангуляции» на страницах 76–81.

Он описывает, как адаптировать обычный алгоритм A * для триангуляции, чтобы искать другие, возможно, более оптимальные пути, даже после того, как конечный узел достигнут / расширен. Обычный A * останавливается, когда последний узел раскрывается, но это не всегда лучший путь при использовании в триангулированном графе. Это именно та проблема, которая у меня возникла.

Проблема проиллюстрирована на странице 78, рисунок 5.4: введите описание изображения здесь

Я понимаю, как рассчитать значения g и h, представленные в статье (стр. 80).

И я думаю, что условие остановки поиска:

if (currentNode.fCost > shortestDistanceFound)
{
    // stop
    break;
}

где currentNode - это поисковый узел, извлеченный из открытого списка (приоритетная очередь), который имеет наименьшую f-оценку. shorttestDistanceFound - это фактическое расстояние до самого короткого пути, найденного до сих пор.

Но как исключить ранее найденные пути из будущих поисков? Потому что, если я сделаю поиск снова, он, очевидно, найдет тот же путь. Сбросить закрытый список? Мне нужно что-то изменить, но я не знаю, что мне нужно изменить. В документе отсутствует псевдокод, так что это было бы полезно.

Morrowless
источник

Ответы:

3

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

shortestDistance = infinity
do A* with modified g cost
    if node.fCost > shortestDistance (section 5.5)
        don't open node
    if node.isGoal()
        run funnel algorithm (string pulling)
        update shortestDistance

Разница заключается в том, что даже если вы найдете на пути к цели, это не обязательно самый короткий путь. Но вы будете продолжать улучшать верхние границы на кратчайшем пути, а это значит, что вам не придется открывать все узлы. В конце концов ваш открытый набор должен быть пустым, и лучший из найденных вами путей должен быть самым коротким.

Модифицированная стоимость g, которую он описывает, кажется большой недооценкой, поэтому я скептически отношусь к тому, насколько хорошо она работает на практике.

celion
источник
Хм, я могу ошибаться, но я интерпретирую это как условие остановки, а не как условие добавления в открытый список. Следующее звучит как условие для добавления в открытый список: «Как примечание стороны, дочерний элемент состояния поиска не будет создан для конкретного соседнего треугольника, если состояние, соответствующее этому треугольнику, уже является предком этого состояния. исключение может быть сделано, потому что оно никогда не устранит оптимальный путь, только тот, который может стать короче, удалив его часть, как указано в теореме 4.3.4. "
Без Моря,