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

Я всегда был заинтригован Map Routing, но я никогда не нашел хороших учебников начального (или даже продвинутого!) Уровня. У кого-нибудь есть указатели, подсказки и т. Д.?

Обновление: я в основном ищу указатели на то, как реализована система карт (структуры данных, алгоритмы и т. Д.).

5.08.2008 20:24:42
9 ОТВЕТОВ
РЕШЕНИЕ

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

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

15
5.08.2008 20:27:36

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

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

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

2
6.08.2008 13:35:08

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

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

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

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

5
20.11.2016 00:28:03
Карты, как правило, слишком велики, чтобы использовать стандартные алгоритмы кратчайшего пути, вам придется создать некоторую эвристику для выбора подграфа. Кроме того, вы можете использовать совершенно разные эвристические подходы (например, сначала автомагистрали, ...), чтобы найти маршрут.
Don Johe 18.08.2009 11:18:52

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

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

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

2
17.09.2008 09:10:22

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

Дорога к лучшему поиску пути 11.06.2007 15:47:00

4
17.09.2008 08:44:28

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

4
24.09.2008 23:19:48
На самом деле, модифицированный D * - это то, что обычно используется, насколько я знаю.
mmcdole 21.10.2008 04:55:40

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

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

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

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

РЕДАКТИРОВАТЬ @ Spikie

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

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

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

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

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

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

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

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

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

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

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

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

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

2
5.08.2010 14:21:09
@ jonathan, пожалуйста, не могли бы вы рассказать подробнее о камне в алгоритме пруда и о том, как я могу применить его на карте? скажем, я нахожусь в точке, и я хочу искать вокруг в ряби, прежде чем перейти к следующей внешней ряби. и чувак, которого я знаю, и на 2 года опоздал на разговор
Spikie 2.08.2010 00:32:27

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

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

1
5.04.2016 13:32:45

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

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

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

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

1
15.07.2012 21:13:02