Внедрение ярлыков (досягаемости) обрезки при использовании A *

Я работаю над проектом по поиску кратчайшего пути. Я просмотрел много ресурсов в Интернете, чтобы придумать хороший алгоритм.

Я работаю с данными openstreetmap, и мне ясно, что я должен использовать алгоритм A*.

При поиске различных решений я обнаружил, что, поскольку путь состоит из разных узлов, можно отсечь промежуточные узлы, которые не являются соединениями. Как я могу сделать это на языке программирования? Если у кого-то есть идея или дополнительная статья, которая может мне помочь, это было бы очень признательно.

Точная информация, которую я нашел об этой обрезке, относящейся к osm, такова:

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


mapping algorithm openstreetmap a-star graph-theory
person echoalpha    schedule 24.02.2015    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Загляните в проект GraphHopper (где я являюсь автором) или другие маршрутизация проектов для OSM уже делает это. Идея состоит в том, чтобы подсчитать количество способов, которыми один узел является членом, и пометить узлы как соединения, если их количество равно трем или более (или только одно, если конечное «соединение»).

Тем не менее, промежуточные узлы должны быть доступны, так как вам нужно проложить маршрут для конечных результатов после расчета маршрута. В GraphHopper мы называем их опорными узлами (узлами между соединениями) и башнями (узлами). Здесь более подробная информация.

Другая проблема заключается в том, что вам нужно рассчитывать точные маршруты GPS, а не только маршруты от перекрестка к перекрестку. Посмотрите это изменение, как мы исправили это с помощью виртуальных узлов и ребер.

person Karussell    schedule 24.02.2015
comment
доступен ли исходный код того, как вы выполняли анализ данных и создавали график, чтобы при его обходе в график включались только узлы башни? РЕДАКТИРОВАТЬ: или как избежать этих узлов столба при обходе - person echoalpha; 24.02.2015
comment
Да, конечно, это все с открытым исходным кодом. См. OSMReader. Но эта часть самая простая по сравнению с другими проблемами, которые у вас возникнут;) - person Karussell; 25.02.2015