пишу роутинг для дорожной сети.
использую алгоритм A*

встала задача о запрете поворотов.

уже весь мозг сломал....

может кто решал подобную задачу?
поделитесь опытом.

Здравствуйте, kkv79, Вы писали:

K>пишу роутинг для дорожной сети.
K>использую алгоритм A*

K>встала задача о запрете поворотов.

Так можно вместо одного узла «перекрёсток» сделать несколько узлов типа «въезд с улицы А» или «съезд на улицу Б». Ну и меняя вес рёбер между такими точками можно либо делать соответствующие манёвры менее выгодными (вроде избегания левых поворотов), либо даже полностью запрещать их. Ну и сделать, разумеется, эти рёбра графа направленными.
Или проблема в чём-то другом?

вопрос не совсем понятен.

Вершинами графа берутся отрезки дорог , а ребрами графа переходы между отрезками дорог , есть ребро — есть поворот , нет ребра ..

Здравствуйте, minorlogic, Вы писали:

M>вопрос не совсем понятен.

M>Вершинами графа берутся отрезки дорог , а ребрами графа переходы между отрезками дорог , есть ребро — есть поворот , нет ребра ..

хм..., интересный подход... действительно, проблема поворотов будет решена. Но...
я делал так: перекрёсток=узел графа, дорога=ребро графа, расстояние от перекрёстка до перекрёстка=вес ребра графа

т.к. моей основной задачей является вычислить расстояние в метрах от точки А до точки В, а не сам путь, (сам маршрут движения меня не интересует)
то не совсем понятно, каким образом, в предложенном Вами варианте, хранить расстояния между узлами. и каким образом в итоге найти длину пути...
проясните плиз....

Здравствуйте, kkv79, Вы писали:

K>Здравствуйте, minorlogic, Вы писали:

M>>вопрос не совсем понятен.

M>>Вершинами графа берутся отрезки дорог , а ребрами графа переходы между отрезками дорог , есть ребро — есть поворот , нет ребра ..

K>хм..., интересный подход... действительно, проблема поворотов будет решена. Но...

Это общепринятый подход в ГИС.

K>то не совсем понятно, каким образом, в предложенном Вами варианте, хранить расстояния между узлами. и каким образом в итоге найти длину пути...
K>проясните плиз....

Это думаю сами сможете нагуглить или додумать, это уже малоинтересные детали реализации, (простейший случай растояния это длина предыдущего сегмента). Обратите внимание что ребра графа направленны.

Здравствуйте, kkv79, Вы писали:

K>Здравствуйте, minorlogic, Вы писали:

M>>вопрос не совсем понятен.

M>>Вершинами графа берутся отрезки дорог , а ребрами графа переходы между отрезками дорог , есть ребро — есть поворот , нет ребра ..

K>хм..., интересный подход... действительно, проблема поворотов будет решена. Но...
K>я делал так: перекрёсток=узел графа, дорога=ребро графа, расстояние от перекрёстка до перекрёстка=вес ребра графа

K>т.к. моей основной задачей является вычислить расстояние в метрах от точки А до точки В, а не сам путь, (сам маршрут движения меня не интересует)
K>то не совсем понятно, каким образом, в предложенном Вами варианте, хранить расстояния между узлами. и каким образом в итоге найти длину пути...
K>проясните плиз....


А ты замени обычный перекрёсток на развязку типа "клеверный лист".
Тогда вместо одного узла будет четыре узла и шесть (с учетом двунаправленности-12) дополнительных рёбер.
На каждое такое ребро вешаешь дополнительное условие(возможность проехать) и даже можно добавить цену поворота в каждом направлении

Здравствуйте, minorlogic, Вы писали:
M>вопрос не совсем понятен.
M>Вершинами графа берутся отрезки дорог , а ребрами графа переходы между отрезками дорог , есть ребро — есть поворот , нет ребра ..
Есть нюанс, например, поворот может быть разрешён, а два поворота (разворот) нет. Потому не всё так однозначно.
Как вариант решения — либо "костыль", либо "как правильно", но сложнее алгоритмизируется и далеко не всеми поддерживается (пример неверного маршрута).

У ТС вроде проблемы другого уровня.

Здравствуйте, kkv79, Вы писали:

K>может кто решал подобную задачу?
K>поделитесь опытом.

K>встала задача о запрете поворотов.

Если ты под запретом поворотов понимаешь ограничения дорожного движения (а не посторение маршрута с минимумом или вообще без поворотов) то общепринятый подход такой: граф дорог преобразуется к ориентированному графу с учетом ограничений. Т.о. двусторонная дорога AB превратится в две дуги A -> B и B' -> A' Если в точке А разрешен разворот, то добавляется фейковая дуга A' -> A. В реальности этой дуге присваивают достаточно большой фейковый вес чтобы избежать необоснованных разворотов. За подробностями см. тысячи открытых движков роутинга.