Я всегда был заинтригован Map Routing, но я никогда не находил никаких хороших вводных (или даже продвинутых) уровней обучения на нем. У кого-нибудь есть указатели, подсказки и т.д.
Обновление: Я в первую очередь ищут указатели относительно того, как реализована система карты (структуры данных, алгоритмы и т.д.).
Взгляните на проект открытой карты улиц, чтобы увидеть, как это происходит в действительно свободном программном проекте, используя только пользователя предоставленные и лицензированные данные и имеющие вики, содержащие материалы, которые могут оказаться интересными.
Несколько лет назад ребята участвовали там, где довольно легко переходили и отвечали на множество вопросов, которые у меня были, поэтому я не вижу причин, по которым они все еще не являются приятной связкой.
По Маршрутизации по карте вы подразумеваете поиск кратчайшего пути вдоль уличной сети?
Самый короткий путь алгоритма Дейкстры - самый известный. В Wikipedia нет плохого вступления: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
Здесь есть апплет Java, в котором вы можете увидеть его в действии: http://www.dgp.toronto.edu/people/JamesStewart/270/9798s/Laffra/DijkstraApplet.html, и Google приводит вас к исходному коду любой язык.
Любая реальная реализация для генерации маршрутов движения будет включать в себя довольно много данных об уличной сети, которые описывают затраты, связанные с пересечением ссылок и узлов - иерархия дорожной сети, средняя скорость, приоритет пересечения, привязка сигнала трафика, запрещенные повороты и т.д.
Барри Брумит, один из разработчиков функции поиска карт Google, написал сообщение на тему, которая может представлять интерес:
Дорога к лучшему поиску пути 11/06/2007 03:47:00 PM
A * на самом деле гораздо ближе к алгоритмам производственного сопоставления. Это требует совсем немного меньше исследований по сравнению с оригинальным алгоритмом Dijikstra.
Вместо того, чтобы изучать API для каждого поставщика услуг карты (например, Gmaps, Ymaps api), полезно изучить Mapstraction
"Mapstraction - это библиотека, которая предоставляет общий API для различных API отображения javascript"
Я предлагаю вам перейти к URL-адресу и узнать общий API. Существует также хорошее количество How-Tos.
Мне еще предстоит найти хороший учебник по маршрутизации, но есть много кода для чтения:
Существуют приложения маршрутизации GPL, которые используют данные Openstreetmap, например. Gosmore, который работает на Windows (+ mobile) и Linux. Существует ряд интересных [приложений, использующих одни и те же данные, но у gosmore есть несколько интересных приложений например. интерфейс с веб-сайтами.
Самая большая проблема с маршрутизацией - это плохие данные, и вы никогда не получите достаточно хороших данных. Поэтому, если вы хотите попробовать, держите ваш тест очень местным, чтобы вы могли лучше контролировать данные.
С концептуальной точки зрения, представьте, что вы бросаете камень в пруд и смотрите на рябь. Маршруты представляли бы пруд и камень в вашем исходном положении.
Конечно, алгоритм должен будет искать некоторую долю n ^ 2 путей при увеличении расстояния n. Вы берете начальную позицию и проверяете все доступные пути с этой точки. Затем рекурсивно вызываем точки в конце этих путей и т.д.
Вы можете увеличить производительность, не используя двойную поддержку на пути, не пересматривая маршруты в точке, если она уже была покрыта, и отказавшись от слишком длинных путей.
Альтернативный способ заключается в использовании подхода ant феромонов, где муравьи сканируют случайным образом из начальной точки и оставляют след запаха, который создает больше муравьев, пересекающих данный путь. Если вы отправляете (достаточно) муравьев из начальной точки и конечных точек, то в конечном итоге путь с самым сильным запахом будет самым коротким. Это связано с тем, что кратчайший путь будет посещаться больше раз за определенный период времени, учитывая, что муравьи ходят в одинаковом темпе.
EDIT @Spikie
В качестве дополнительного объяснения того, как реализовать алгоритм пруда, необходимо выделить потенциальные структуры данных:
Вам нужно сохранить карту как сеть. Это просто набор nodes и edges между ними. Набор nodes составляет a route. Кромка соединяет два узла (возможно, оба одинаковые node) и имеет связанный с ним cost, такой как distance или time, чтобы пересечь ребро. Край может быть либо двунаправленным, либо однонаправленным. Вероятнее всего, просто просто иметь однонаправленные и удвоить для двухстороннего перемещения между узлами (т.е. Одно ребро от А до В и другое для Б до А).
В качестве примера представим три железнодорожные станции, расположенные в равностороннем треугольнике, направленном вверх. Есть также еще три станции на полпути между ними. Кромки соединяются со всеми соседними станциями вместе, последняя диаграмма будет иметь перевернутый треугольник, расположенный внутри большего треугольника.
Узлы метки, начинающиеся слева внизу, идут влево и вправо, как A, B, C, D, E, F (F вверху).
Предположим, что ребра можно перемещать в любом направлении. Каждый край имеет стоимость 1 км.
Итак, мы хотим маршрутизировать из левого нижнего положения A в верхнюю станцию F. Существует множество возможных маршрутов, включая те, которые удваиваются обратно на себя, например. ABCEBDEF.
У нас есть подпрограмма, NextNode, которая принимает node и a cost и вызывает себя для каждого node, к которому она может перейти.
Ясно, что если мы допустим, что эта подпрограмма запускается, в конечном итоге будут обнаружены все маршруты, в том числе потенциально бесконечные по длине (например, ABABABAB и т.д.). Мы останавливаемся на этом, проверяя на cost. Всякий раз, когда мы посещаем node, который ранее не был посещен, мы поместили как стоимость, так и node из этого node. Если node был посещен, прежде чем мы проверим стоимость, и если мы дешевле, мы обновим node и продолжаем (рекурсивно). Если мы дороже, мы пропустим node. Если все узлы пропущены, мы выходим из подпрограммы.
Если мы нажмем на цель node, мы также выйдем из этой программы.
Таким образом проверяются все жизнеспособные маршруты, но решаются только те, у которых самая низкая стоимость. К концу процесса каждый node будет иметь самую низкую стоимость для получения этого node, включая нашу цель node.
Чтобы получить маршрут, мы работаем назад от нашей цели node. Поскольку мы сохранили node, мы пришли вместе со стоимостью, мы просто прыгаем назад, наращивая маршрут. В нашем примере мы получим что-то вроде:
Node A - (Всего) Стоимость 0 - От node Нет
Node B - Стоимость 1 - От node A
Node C - Стоимость 2 - От node B
Node D - Стоимость 1 - От node A
Node E - Стоимость 2 - От node D/Стоимость 2 - От node B (это исключение, так как существует равная стоимость)
Node F - Стоимость 2 - От node D
Итак, самый короткий маршрут - это ADF.
Другая мысль приходит мне в отношении стоимости каждого обхода, но увеличит время и вычислительную мощность, необходимые для вычисления.
Пример: Есть три способа, которыми я могу (где я живу) перейти от точки А к Б, в соответствии с GoogleMaps. Единицы Garmin предлагают каждый из этих 3 путей в расчете маршрута Quickest. После многократного прохождения каждого из этих маршрутов и усреднения (очевидно, будут ошибки в зависимости от времени суток, количества кофеина и т.д.), Я считаю, что алгоритмы могут учитывать количество изгибов в дороге для высокого уровня точности, напр. прямой путь 1 мили будет быстрее, чем 1-мильная дорога с острыми изгибами в ней.
Не практическое предложение, но, конечно, одно, которое я использую для улучшения набора результатов моей ежедневной поездки.
Из моего опыта работы в этой области A * делает работу очень хорошо. Он (как упоминалось выше) быстрее, чем алгоритм Дейкстры, но все еще достаточно прост для обычного компетентного программиста для реализации и понимания.
Построение маршрутной сети - самая сложная часть, но ее можно разбить на несколько простых шагов: получить все дороги; сортировать точки в порядке; сделать группы одинаковых точек на разных дорогах пересечениями (узлами); добавьте дуги в обоих направлениях, где узлы соединяются (или в одном направлении только для односторонней дороги).
Сам алгоритм A * хорошо документирован в Википедии. Ключевым местом для оптимизации является выбор лучшего node из открытого списка, для которого вам нужна высокопроизводительная очередь приоритетов. Если вы используете С++, вы можете использовать адаптер STL priority_queue.
Настройка алгоритма маршрутизации по различным частям сети (например, пешехода, автомобиля, общественного транспорта и т.д.) в пользу скорости, расстояния или других критериев довольно проста. Вы делаете это, записывая фильтры, чтобы контролировать, какие сегменты маршрута доступны, при построении сети и какой вес назначается каждому из них.