Избегайте разворотов в алгоритме A *

Question

Я определил узлы и ребра для графа, которые я хочу использовать для определения пути, используя алгоритм A *. У меня есть алгоритм A *, который, кажется, работает, но теперь мне нужно предотвращать развороты. Это не дороги с двумя или более полосами движения, это только одно направление, хотя два узла образуют два ребра (по одному в любом направлении).

Так, например, если я хочу вычислить маршрут из 1114-1105, алгоритм выдаст мне 1114-1112-1105. Это недопустимо, поскольку включает разворот с 1112 на 1105. Результат, который я хочу достичь, был бы больше похож на 1114-1110-1111-1113-1112-1105.

Я наивно думал, что смогу вычислить угол между предыдущим, текущим и следующим узлами, который в этом случае будет равен 0, а затем добавить большое число к значению 'f'. Но, похоже, это ничего не делает.

Есть предложения, как это реализовать? Спасибо

Answer 1

Ваше «состояние» на графике зависит от двух вещей:

• Узел, в котором вы находитесь
• Узел, с которого вы пришли

Чтобы смоделировать это, мы можем создать новый (направленный) граф, где каждое «состояние» является своим собственным узлом.Другими словами, вы создаете новый граф, разделяя каждый узел в вашем старом графе на N узлов в новом графе (где N - число входящих ребер в этот старый узел) .Тогда у нового узла будет меньше исходящих ребер.

Это может разделить ваши начальные / конечные узлы на несколько узлов.Чтобы исправить это, вы можете создать новые одиночные начальные / конечные узлы и подключить их к старым начальным / конечным узлам с ребрами с нулевой стоимостью.