Карта маршрутизации, а Карты Google ла?

голоса
19

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

Обновление: Я в первую очередь ищу указатели о том , как реализуется система отображения (структуры данных, алгоритмы и т.д.).

Задан 05/08/2008 в 21:24
источник пользователем
На других языках...                            


9 ответов

голоса
14

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

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

Ответил 05/08/2008 d 21:27
источник пользователем

голоса
4

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

Ответил 25/09/2008 d 00:19
источник пользователем

голоса
4

Барри Brumitt, один из инженеров Google Maps особенности маршрута ознакомительной, написал пост на тему, которая может представлять интерес:

Путь к хорошему пути, находя 11/06/2007 03:47:00 PM

Ответил 17/09/2008 d 09:44
источник пользователем

голоса
4

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

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

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

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

Ответил 15/08/2008 d 05:31
источник пользователем

голоса
2

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

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

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

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

EDIT @ Spikie

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

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

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

Этикетка узлов, начиная с левой нижней, идя слева направо и вверх, а А, В, С, D, E, F (F в верхней части).

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

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

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

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

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

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

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

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

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

Ответил 26/09/2008 d 15:05
источник пользователем

голоса
2

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

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

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

Ответил 17/09/2008 d 09:34
источник пользователем

голоса
2

Вместо обучения API , каждому провайдеру картографического сервиса (как Gmaps, Ymaps АНП) его хорошо учиться Mapstraction

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

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

Ответил 06/08/2008 d 14:35
источник пользователем

голоса
1

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

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

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

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

Ответил 15/07/2012 d 22:13
источник пользователем

голоса
1

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

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

Ответил 18/09/2011 d 22:34
источник пользователем

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more