Алгоритм Дейкстры для iPhone

Question

С iPhone SDK 3.0 можно легко использовать функцию GPS в iPhone, но категорически запрещено использовать Карты Google. Я думаю, это имеет два значения:

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

Я знаю, что вычисление кратчайшего маршрута озадачивало математиков целую вечность, но и Том Том, и Google отлично справляются со своей задачей, поэтому эта проблема, похоже, решена. Ища в сети, не будучи математиком, я наткнулся на алгоритм Дейкстры . Есть ли кто-нибудь из вас, кто успешно использовал этот алгоритм в приложении, похожем на Карты в iPhone? Хотели бы вы поделиться этим со мной / сообществом? Будет ли это правильный подход или другие варианты? Большое спасибо за внимание.

Answer 1

Я не верю, что алгоритм Дейкстры был бы полезен для картирования реального мира, потому что, как сказал Том Лейс (я бы прокомментировал его пост, но у меня не было бы представителя для этого), он требует единственной отправной точки. Если начальная точка изменяется, все должно быть пересчитано, и я полагаю, что это будет довольно медленно на устройстве, таком как iPhone, для значительно большого набора данных.

Answer 2

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

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

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

Обновление После долгих поисков я нашел статью на A *, которую вы можете прочитать

Answer 3

Алгоритм Дейкстры равен O (m log n) для n узлов и m ребер (для одного пути) и достаточно эффективен для использования при сетевой маршрутизации. Это означает, что он достаточно эффективен для одноразового вычисления.

Вкратце, алгоритм Дейкстры работает так:

Take the start node
Assign it a depth of zero
Insert it into a priority queue at its depth key

Repeat:
    Pop the node with the lowest depth from the priority queue
    Record the node that you came from so you can track the path back
    Mark the node as having been visited
    If this node is the destination:
        Break
    For each neighbour:
        If the node has not previously been visited:
            Calculate depth as depth of current node + distance to neighbour
            Insert neighbour into the priority queue at the calculated depth.

Return the destination node and list of the nodes through which it was reached.

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

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

Answer 4

Расчет маршрута с использованием алгоритма A * достаточно быстрый на iPhone с данными офлайн-карты. У меня есть опыт ведения коммерческой деятельности. Я использую алгоритм A *, описанный в Википедии, и храню дорожную сеть в памяти и использую ее повторно; после загрузки маршрут даже по большой территории, такой как Испания или западная половина Канады, практически мгновенный.

Я беру данные из OpenStreetMap или elswhere и преобразую их в ориентированный граф, предполагая (что является правильным способом для тех, кто знает), что любые две дороги, разделяющие точку с одинаковым идентификатором, объединяются. Я назначаю веса различным типам дорог на основе ожидаемых скоростей, и если часть дороги односторонняя, я создаю только одну дугу; дороги с двусторонним движением получают две дуги, по одной в каждом направлении. Это почти все, кроме специального кода для предотвращения опасных поворотов и реализации ограничений маршрутизации.

Answer 5

Если вы посмотрите на технологические вызовы tomtom «IQ-маршруты», они измеряют фактическую скорость и время в пути на рейд в любое время суток. Это делает время прибытия более точным. Таким образом, ожидаемое время прибытия более основано на фактах http://www.tomtom.com/page/iq-routes

Answer 6

Взгляните на CloudMade . Они предлагают бесплатный сервис для iPhone и iPad, который позволяет навигацию в зависимости от вашего текущего местоположения. Он построен на открытых картах улиц и имеет некоторые изящные функции, такие как создание собственного стиля карты. Время от времени он немного медленный, но совершенно бесплатный.

Answer 7

Это обсуждалось ранее здесь: Какие алгоритмы вычисляют направления от точки a к точке b на карте?