Карта маршрутизации, а-ля Google Maps?

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

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

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

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

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

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

Барри Брумитт, один из инженеров Google maps route finding feature, написал пост на эту тему, который может представлять интерес:

Дорога к лучшему пути-поиск 11/06/2007 03:47:00 PM

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

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

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

Я бы посоветовал вам пойти в URL и выучить общий API. Есть также хорошее количество инструкций.

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

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

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

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

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

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

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

EDIT @ Spikie

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

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

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

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

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

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

У нас есть подпрограмма, скажем , NextNode, которая принимает a node и A cost и вызывает СЕБЯ Для каждого узла, к которому она может перейти.

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

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

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

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

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

Так что самый короткий маршрут-это ADF.

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

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

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

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

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

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