Представление карты и работа A * на ней

Question

Мой вопрос в основном о представлении карты, и мне бы хотелось ваше мнение.

Имея карту, представленную связкой дорог и связью между ними, скажем, дорога A соединена с B, C, D на одном краю, но возможны только повороты от A до C и D. Предположим, Я представляю это по графику, где каждая дорога является краем, и каждая встреча/конец дороги - это вершина.

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

Я могу сохранить, откуда я родом, но я также хочу, чтобы это было как можно более общим, а простое графическое решение не дает мне знания, откуда я родом.

Не могли бы вы посоветовать мне, как бы вы приблизились к этому?

Спасибо!

Answer 1

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

Итак, у нас есть следующий график.

И пусть используют следующие правила:

• Если Приехал из А чем мы можем только обратиться к D
• Если пришел к В от С чем мы можем идти только E
• Если пришел к с от а, чем мы можем пойти как B и D
• Если Приехал с из Е, чем мы можем идти только Б

Чем мы имеем следующий эквивалентный граф, теперь каждый узел, отмеченный оригинальным имя и входящую дорога:

Это универсальный способ, который позволяет, как использовать любой стандартный алгоритм для ориентированного графа в такой ситуации , Для некоторых алгоритмов вам может понадобиться создать поддельные исходные или начальные и стоковые или узловые узлы для обработки, которые на таком графике могут быть представлены как несколько узлов каждый, в данном случае нам может понадобиться дополнительный узел для описания поведения, если мы начнем с этого носа , вместо того, чтобы исходить из какого-то другого, но в целом это просто оригинальная структура, представленная как классический граф.

Также нам не нужно разделять A, D или E, если они всегда имеют одинаковое поведение.