Маршрутизация карты, а-ля Google Maps?

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

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

Вместо того, чтобы изучать API для каждого поставщика картографических сервисов (например, Gmaps, Ymaps api), полезно изучить Mapstraction

«Mapstraction - это библиотека, которая предоставляет общий API для различных API-интерфейсов сопоставления javascript»

Я предлагаю вам перейти по URL-адресу и изучить общий API. Также есть много How-Tos.

Под маршрутизацией по карте вы имеете в виду поиск кратчайшего пути по уличной сети?

Алгоритм кратчайшего пути Дейкстры является наиболее известным. В Википедии есть неплохое вступление: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Здесь есть Java-апплет, где вы можете увидеть его в действии: http://www.dgp.toronto.edu/people/JamesStewart/270/9798s/Laffra/DijkstraApplet.html и Google вы найдете исходный код практически на любом языке.

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

Мне еще не удалось найти хороший учебник по маршрутизации, но есть много кода, который нужно прочитать:

Существуют приложения маршрутизации GPL, использующие данные Openstreetmap, например Госмор, который работает в Windows (+ mobile) и Linux. Есть ряд интересных [приложений, использующих те же данные, но у gosmore есть несколько интересных применений например интерфейс с веб-сайтами.

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

Барри Брумитт, один из разработчиков функции поиска маршрута на картах Google, написал сообщение по теме, которая может представлять интерес:

Путь к лучшему поиску пути 06.11.2007 15:47:00

A * на самом деле намного ближе к алгоритмам отображения продукции. Он требует немного меньше исследований по сравнению с исходным алгоритмом Диджикстры.

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

Конечно, алгоритм должен будет искать некоторую долю путей из n ^ 2 по мере увеличения расстояния n. Вы бы заняли свою исходную позицию и проверили все доступные пути с этой точки. Затем рекурсивно вызовите точки в конце этих путей и так далее.

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

Альтернативный способ - использовать подход с феромонами муравьев, при котором муравьи беспорядочно ползают от начальной точки и оставляют след запаха, который накапливается по мере того, как больше муравьев пересекает заданный путь. Если вы отправите (достаточное количество) муравьев как из начальной, так и из конечной точек, в конечном итоге путь с самым сильным запахом будет самым коротким. Это связано с тем, что кратчайший путь будет посещаться больше раз за заданный период времени, учитывая, что муравьи идут с одинаковой скоростью.

ИЗМЕНИТЬ @ Spikie

В качестве дополнительного объяснения того, как реализовать алгоритм пруда, выделены потенциальные необходимые структуры данных:

Вам нужно будет сохранить карту как сеть. Это просто набор nodes и edges между ними. Набор nodes составляет route. Ребро соединяет два узла (возможно, оба являются одним и тем же узлом) и имеет связанный cost, такой как distance или time, для пересечения границы. Ребро может быть двунаправленным или однонаправленным. Вероятно, проще всего иметь однонаправленные и удвоить для двустороннего перемещения между узлами (то есть одно ребро от A до B и другое для B к A).

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

Обозначьте узлы, начиная снизу слева, слева направо и вверх, как A, B, C, D, E, F (F вверху).

Предположим, что края можно перемещать в любом направлении. Каждое ребро имеет стоимость 1 км.

Хорошо, поэтому мы хотим пройти от левого нижнего угла A до верхней станции F. Есть много возможных маршрутов, в том числе те, которые возвращаются сами по себе, например ABCEBDEF.

У нас есть процедура, скажем, NextNode, которая принимает node и cost и вызывает себя для каждого узла, к которому она может перемещаться.

Очевидно, что если мы позволим этой подпрограмме работать, она в конечном итоге обнаружит все маршруты, включая потенциально бесконечные по длине (например, ABABABAB и т. д.). Мы предотвращаем это, проверяя cost. Каждый раз, когда мы посещаем узел, который ранее не посещался, мы помещаем стоимость и узел, из которого мы пришли, против этого узла. Если узел был посещен до того, как мы сверим с существующей стоимостью, и если мы дешевле, мы обновляем узел и продолжаем (рекурсивно). Если мы дороже, то пропускаем узел. Если все узлы пропущены, мы выходим из процедуры.

Если мы попадаем в наш целевой узел, мы также выходим из процедуры.

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

Чтобы получить маршрут, мы работаем в обратном направлении от нашего целевого узла. Поскольку мы сохранили узел, из которого пришли, вместе со стоимостью, мы просто перескакиваем назад, строя маршрут. В нашем примере мы получим что-то вроде:

Узел A - (Общая) Стоимость 0 - От узла Нет
Узел B - Стоимость 1 - От узла A
Узел C - Стоимость 2 - От узла B
Узел D - Стоимость 1 - От узла A
Узел E - Стоимость 2 - От узла D / Стоимость 2 - От узла B (это исключение, поскольку существует равная стоимость)
Узел F - Стоимость 2 - От узла D

Итак, самый короткий маршрут - ADF.

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

Пример: Согласно картам GoogleMaps, я могу (там, где я живу) добраться из точки А в точку Б тремя способами. Устройства Garmin предлагают каждый из этих трех путей в расчете маршрута Quickest. После многократного прохождения каждого из этих маршрутов и усреднения (очевидно, что будут ошибки в зависимости от времени суток, количества кофеина и т. д.), Я чувствую, что алгоритмы могут учитывать количество поворотов дороги для высокого уровня точности. , напримерпрямая дорога в 1 милю будет быстрее, чем дорога в 1 милю с крутыми поворотами. Не практическое предложение, но, безусловно, я использую его, чтобы улучшить результат моей ежедневной поездки на работу.

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

Создание сети маршрутов - самая сложная часть, но ее можно разбить на ряд простых шагов: проложить все дороги; отсортируйте точки по порядку; объединять группы одинаковых точек на разных дорогах в перекрестки (узлы); добавьте дуги в обоих направлениях, где соединяются узлы (или в одном направлении только для дороги с односторонним движением).

Сам алгоритм A * - хорошо задокументировано в Википедии. Ключевым моментом для оптимизации является выбор лучшего узла из открытого списка, для которого вам нужна высокопроизводительная приоритетная очередь. Если вы используете C++, вы можете использовать адаптер STL priority_queue.

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