Комментарии 28
Правильно я понимаю, что использовался алгоритм Дейкстры? Не пробовали ли вы использовать эвристические оптимизации вроде A*?
Думали об этом, но поскольку ищем маршрут с минимальным времени сходу не придумали какую эвристику использовать для A*. Интуитивно расстояние до цели казалось неподходящим. Но может быть мы были не правы и позже попробуем.
Планирую написать статью о правильном использовании A* для геоинформационных маршрутов, а так по топику:
1. При использовании правильной эвристики (например расстояния, вообще-то все меряется во времени) A* ищет оптимальный маршрут!
2. Двунаправленный A* ищет быстрее, но требует больше памяти.
1. При использовании правильной эвристики (например расстояния, вообще-то все меряется во времени) A* ищет оптимальный маршрут!
2. Двунаправленный A* ищет быстрее, но требует больше памяти.
Если времени на статью не найдете, напишите хотя бы заметку.
Мы хотели попробовать распределенную дейкстру из Parallel BGL, чтобы подсократить время поиска, но к сожалению не успели. С удовольствием послушал бы чей-то опыт про это. Стоит ли оно того.
Мы хотели попробовать распределенную дейкстру из Parallel BGL, чтобы подсократить время поиска, но к сожалению не успели. С удовольствием послушал бы чей-то опыт про это. Стоит ли оно того.
Я работаю над маршрутами для мобильных устройств и там другая специфика, что не имею 1) много RAM 2) не могу держать большое количество предрасчетов в самих картах (мало диска).
ИМХО, все opensource тренды сводятся к 2-м: A* и Contraction Hierarchies. Все остальные используют эвристики и могут строить неоптимальные маршруты.
Да и тем более, если у вас маршрут 60мс советую вам ничего не делать — это уже отлично :) Когда граф дорог дорастет до 100Гб RAM тогда может, что-то придется менять)
ИМХО, все opensource тренды сводятся к 2-м: A* и Contraction Hierarchies. Все остальные используют эвристики и могут строить неоптимальные маршруты.
Да и тем более, если у вас маршрут 60мс советую вам ничего не делать — это уже отлично :) Когда граф дорог дорастет до 100Гб RAM тогда может, что-то придется менять)
Почему не взяли/не дописали готовый «маршрутизатор» из Openstreetmap?
Если конкретно, то, например, project-osrm.org/
Спасибо, тут уже понятнее, что имеется в виду, поизучаем.
Вот сайт научной группы, которая разрабатывала алгоритмы. Там есть ссылки на статьи, где алгоритмы описаны.
Да-да, почему только Дейкстра и A*, когда из-за возросших в последние десятилетия потребностей (дорожные карты материкового масштаба, на которых надо быстро находить оптимальный маршрут между любыми парами точек; линейные по сложности алгоритмы становятся неприемлемыми) сейчас существуют хорошо проработаные алгоритмы, дающие сублинейную сложность поиска кратчайшего пути (если граф дорог удовлетворяет определённым критериям и есть возможность провести его пред-обработку). Это интересная тема, и я не видел пока на Хабре её обсуждений, хотя посты по поиску кратчайшего пути время от времени появляются! Но в них всегда те же Дейкстра и A*, плюс, может быть, эвристические улучшения… Поправьте меня, если здесь всё-таки описывали что-то более актуальное (ключевые словосочетания, например, contraction hierarchies, highway dimension — при удовлетворении пред-условий на дорожную сеть сублинейный результат по сложности гарантируется, никаких эвристических неопределённостей!)
Я не имею в виду, что в этой заметке неправилный подход (тут акцент на других аспектах), просто пока не вижу на Хабре добротной информации по современным алгоритмам поиска кратчайшего пути на дорожных сетях за сублинейное время.
Да, сейчас поискал ещё раз, есть только одно упоминание highway dimension — но не в заметке, а в объявлении о лекции: habrahabr.ru/company/yandex/blog/82992/
Я не имею в виду, что в этой заметке неправилный подход (тут акцент на других аспектах), просто пока не вижу на Хабре добротной информации по современным алгоритмам поиска кратчайшего пути на дорожных сетях за сублинейное время.
Да, сейчас поискал ещё раз, есть только одно упоминание highway dimension — но не в заметке, а в объявлении о лекции: habrahabr.ru/company/yandex/blog/82992/
Основной упор идет на предпоготовку данных. Основное достоинство, что они предрасчитывают минимальные маршруты, то есть известно через какую точку будет проходить минимальный маршрут. Здесь же возникают и основная сложность: для любого динамического параметра надо хранить абсолютно другой граф дорог.
Поэтому выскажу недостатки OSRM, Grasshopper, которые по-моему до сих пор не решены:
— нет возможности склеивать 2 графа дорог (2 страны), потому как shortcut — основная концеция Contraction Hierarchies придется пересчитывать. Поэтому проекты держат полный граф дорог на машине.
— нет возможности менять динамические атрибуты (повысить приоритет, избегать дороги с ограничение 3 тонны и т.п.)
Работы ведутся в этом направление, но боюсь так как это концептуальные недостатки, внедрение этих фич будет жертвовать оптимальностью маршрута.
Большинство навигаторов применяют эвристики, но это достаточно дорого обходится. Потому что всякая эвристика ведет к неоптимальности и эти баги надо закрывать. Некоторые эвристики основаны на данных, например, на классах дорог. Можно предположить (или поставить требования для картографов), что классы дорог должны повышаться в любом маршруте, а затем понижаться (одномодные маршруты). Естественно если где-то между 2 трассами идет разрыв и переход через улицу, то эта эвристика не сработает.
Каждая эвристика должна быть подкреплена отчетом по данным, если на данные накладывается ограничение, то эвристика, становится неэвристикой, а частью алгоритма.
Поэтому выскажу недостатки OSRM, Grasshopper, которые по-моему до сих пор не решены:
— нет возможности склеивать 2 графа дорог (2 страны), потому как shortcut — основная концеция Contraction Hierarchies придется пересчитывать. Поэтому проекты держат полный граф дорог на машине.
— нет возможности менять динамические атрибуты (повысить приоритет, избегать дороги с ограничение 3 тонны и т.п.)
Работы ведутся в этом направление, но боюсь так как это концептуальные недостатки, внедрение этих фич будет жертвовать оптимальностью маршрута.
Большинство навигаторов применяют эвристики, но это достаточно дорого обходится. Потому что всякая эвристика ведет к неоптимальности и эти баги надо закрывать. Некоторые эвристики основаны на данных, например, на классах дорог. Можно предположить (или поставить требования для картографов), что классы дорог должны повышаться в любом маршруте, а затем понижаться (одномодные маршруты). Естественно если где-то между 2 трассами идет разрыв и переход через улицу, то эта эвристика не сработает.
Каждая эвристика должна быть подкреплена отчетом по данным, если на данные накладывается ограничение, то эвристика, становится неэвристикой, а частью алгоритма.
Интересно. Вы профи в теме (глядя на ваши реплики выше), а я знаком с ней только из любопытства, прочитал несколько статей / презентаций на английском, так что я не чувствую себя достаточно квалифицированным для обсуждения в подробностях. Основной пункт для меня вот в чём: насколько я могу понять беглым поиском, сублинейные алгоритмы с предподготовкой (Contraction Hierarchies) на Хабре не описывались. Да, они имеют недостатки при добавлении специфических (жизненных, разумеется) усложнений вроде динамики весов, ограничений, и не дают выигрыша на произвольных графах. Однако, они весьма хорошо работают на статических материковых картах (так как естественно сложившиеся материковые карты имеют достаточно низкую хайвейную размерность). Да, при добавлении динамики / ограничений в алгоритмы доказанной оптимальностью маршрутов приходится жертвовать, но то, что они резко проиграют после этого A*, это вопрос для меня не очевидный. Про динамику я статьи не читал, но они существуют (я интересовался, чем занимались авторы прочитанных мной статей в последнее время, и видел публикации про динамически усложнения).
Вот, кстати, пример статьи на Хабре: habrahabr.ru/post/180269/ — оригинальное исследование, весьма вероятно на идеях близких к Contraction Hierarchies (вершины графа с большими степенями лежат на хайвейных шорткатах в другой терминологии), но без отсылок к смежным исследованиям (довольно многочисленным и разнообразным: область ведь довольно горячая); меня это несколько опечаливает. А сесть самому в выходные, написать код, погонять, написать обстоятельное изложение и т.п. при том, что это никак не относится к моей текущей работе, я не могу себе позволить, увы (ну и не особо осмысленно «соревноваться» с профессионалами в области или работать популяризатором их результатов на чистом энтузиазме). А вы не собираетесь написать свою заметку? Интересно было бы почитать-обсудить!
Вот, кстати, пример статьи на Хабре: habrahabr.ru/post/180269/ — оригинальное исследование, весьма вероятно на идеях близких к Contraction Hierarchies (вершины графа с большими степенями лежат на хайвейных шорткатах в другой терминологии), но без отсылок к смежным исследованиям (довольно многочисленным и разнообразным: область ведь довольно горячая); меня это несколько опечаливает. А сесть самому в выходные, написать код, погонять, написать обстоятельное изложение и т.п. при том, что это никак не относится к моей текущей работе, я не могу себе позволить, увы (ну и не особо осмысленно «соревноваться» с профессионалами в области или работать популяризатором их результатов на чистом энтузиазме). А вы не собираетесь написать свою заметку? Интересно было бы почитать-обсудить!
Не понял про склейку двух графов. В OSM это всегда один граф, там отдельных нет. Это не баг, это свойство данных.
Думаю, что мы могли бы его использовать, если бы нашли. Но вряд ли бы это сильно сэкономило нам время, так как для того, чтобы запустить это решение на наших данных, сами данные нужно было бы привести в нормальный вид, а потом преобразовать в формат OSM (это наверное совсем несложно), выполнив как трансформацию графа в соответствии с ограничениями, так и предобработку для «склеивания» вершин, а это вещи которые заняли у нас больше 90% времени.
Если мы будем в будущем развивать наше решение, то возможно переход на OSRM в качестве поискового движка будет иметь смысл. Еще раз спасибо за ссылку.
Если мы будем в будущем развивать наше решение, то возможно переход на OSRM в качестве поискового движка будет иметь смысл. Еще раз спасибо за ссылку.
Когда искали готовое решение — этот маршрутизатор не нашли. Но сейчас бегло посмотрев, не смог сходу найти хорошо документированное API или возможность разместить на своих серверах, и как его можно использовать на своих, а не OpenStreetMaps данных. По этим критериям мы бы его исключили, даже если бы нашли.
OSRM именно под Open Street Maps заточен, но вам стоит всё же посмотреть как там всё работает, может найдёте что интересное/полезное, например про edge-expanded graph.
Для первой задачи стандартный способ решения — с помощью R* tree.
Для второй задачи я бы попробовал ослабить требование оптимальности маршрута. Есть способы находить очень близкий к оптимальному маршрут заметно быстрее. Навигаторы обычно так и работают — по карте раскидана сеть опорных точек, между которыми заранее посчитаны (или могут быть быстро посчитаны) маршруты. Вроде протоптанных троп. Тогда достаточно посчитать маршрут от точки А до ближайшей опорной и от другой опорной до точки Б.
Для второй задачи я бы попробовал ослабить требование оптимальности маршрута. Есть способы находить очень близкий к оптимальному маршрут заметно быстрее. Навигаторы обычно так и работают — по карте раскидана сеть опорных точек, между которыми заранее посчитаны (или могут быть быстро посчитаны) маршруты. Вроде протоптанных троп. Тогда достаточно посчитать маршрут от точки А до ближайшей опорной и от другой опорной до точки Б.
Многие упоминают опорные точки, но я еще ни одной хорошой реализации не видел, потому что есть следующие проблемы.
— Предположим у нас есть сеть опорных точек, сколько их 1000? 100? Между всеми ними нужно построить расстояние следовательно X^2, уже 1 000 000 для 1000.
— Для поиска ближайшей опорной точки придется использовать алгоритм Дейкстры (поиск в глубину). Если даже вы поставите в Москве на каждой трассе выезде по точке (думаю не менее 30-40), то вам придется из центра Москвы просмотреть практически все дороги, что не слабо
— Алгоритм расстановки опорных точек, крайне важен и крайне неясен. Их должно быть мало и они должны быть равномерно распределены.
— Самое главное замечание, если маршрут ведет через 2 опорные точки, которые недалеко друг от друга, абсолютно не факт, что он оптимальный. А не оптимальные маршруты к сожалению неинтересны пользователям.
Между прочим Contraction Hierarchies реализует идею опорных точек, но под другим соусом, но там свои проблемы.
— Предположим у нас есть сеть опорных точек, сколько их 1000? 100? Между всеми ними нужно построить расстояние следовательно X^2, уже 1 000 000 для 1000.
— Для поиска ближайшей опорной точки придется использовать алгоритм Дейкстры (поиск в глубину). Если даже вы поставите в Москве на каждой трассе выезде по точке (думаю не менее 30-40), то вам придется из центра Москвы просмотреть практически все дороги, что не слабо
— Алгоритм расстановки опорных точек, крайне важен и крайне неясен. Их должно быть мало и они должны быть равномерно распределены.
— Самое главное замечание, если маршрут ведет через 2 опорные точки, которые недалеко друг от друга, абсолютно не факт, что он оптимальный. А не оптимальные маршруты к сожалению неинтересны пользователям.
Между прочим Contraction Hierarchies реализует идею опорных точек, но под другим соусом, но там свои проблемы.
Выбор количества опорных точек, их расположение, какие пути заранее считать и в каком порядке их перебирать — задача тоже интересная. Но это уже не чисто алгоритмическая задача, а оптимизационная. И сильно привязанная к конкретным картам и источникам информации, особенно к обратной связи о качестве выбранных маршрутов.
Опорные точки — действительно частный случай contraction hierarchies.
Неоптимальные маршруты пользователям интересны. Google Maps, Yahoo Maps, Nokia Maps на телефоне и Garmin на навигаторе зачастуют дают мне совершенно разные маршруты. Не может быть так, чтоб все эти маршруты были оптимальны. Но если мне ехать час, а разница во времени поездки между ними 10 секунд, то мне как пользователю всё равно. А вот если один строит маршрут две минуты, а другой две секунды, то это мне не всё равно.
Опорные точки — действительно частный случай contraction hierarchies.
Неоптимальные маршруты пользователям интересны. Google Maps, Yahoo Maps, Nokia Maps на телефоне и Garmin на навигаторе зачастуют дают мне совершенно разные маршруты. Не может быть так, чтоб все эти маршруты были оптимальны. Но если мне ехать час, а разница во времени поездки между ними 10 секунд, то мне как пользователю всё равно. А вот если один строит маршрут две минуты, а другой две секунды, то это мне не всё равно.
Вы путаете «неоптимальные» маршруты и разные способы оценки маршрутов. Например 1% погрешности может приводить к тому, что алгоритм предложить съехать и заехать на трассу, что является откровенным багом с точки зрения пользователя, но в пределах допустимой погрешности.
Необязательно. Например, если есть два маршрута: долгий с заездом на трассу и быстрый задворками. Если разница между ними по времени в пути 1%, то я как пользователь могу предпочесть неоптимальный первый вариант, потому что меньше рулём крутить и реже на педали нажимать.
Предпочтения среднего пользователя можно как-то отразить в относительных весах разных дорог, но мои личные предпочтения, особенно мои предпочтения в данный момент, не выйдет.
Предпочтения среднего пользователя можно как-то отразить в относительных весах разных дорог, но мои личные предпочтения, особенно мои предпочтения в данный момент, не выйдет.
Для первой задачи R-tree безусловно подошел бы. Но сложность склейки вершин полагаю была бы n log(n), а наше решение для нашего частного случая имеет линейную сложность. Вероятно в абсолютных величинах время обработки нашего набора данных отличалось бы не драматически, но наше решение довольно простое в реализации, так почему бы и нет.
По второй части возникает вопрос сложности предпросчета при меняющихся весах (например пробки).
По второй части возникает вопрос сложности предпросчета при меняющихся весах (например пробки).
Планируется ли добавить данные о пробках и, если да, то как оценивается усложнение поискового алгоритма?
На данный момент маршруты с учетом пробок не планируются (не хватает людей и времени), это большая задача.
Сложность доработки очень сильно зависит от вида, в котором можно получить данные о пробках. Если это будет просто таблица новых весов сегментов, то изменений практически не требуется. Но думаю в реальной жизни данные о пробках такими идеальными не бывают и большая часть работы будет сосредоточена в том, чтобы привести эти данные к виду «просто таблица новых весов сегментов».
Сложность доработки очень сильно зависит от вида, в котором можно получить данные о пробках. Если это будет просто таблица новых весов сегментов, то изменений практически не требуется. Но думаю в реальной жизни данные о пробках такими идеальными не бывают и большая часть работы будет сосредоточена в том, чтобы привести эти данные к виду «просто таблица новых весов сегментов».
Статья очень понравилась.
Один только вопрос:
«Правда точки, расстояние между которыми меньше 1 метра, могут иметь разные ключи»
Можете пояснить, почему это может иметь место? Вообще, хэш функция у Вас выбрана достаточно сложно (getKey). Почему было бы просто не взять номер точки в сетке, с учетом того, что у вас 8-байтовый ключ?
Один только вопрос:
«Правда точки, расстояние между которыми меньше 1 метра, могут иметь разные ключи»
Можете пояснить, почему это может иметь место? Вообще, хэш функция у Вас выбрана достаточно сложно (getKey). Почему было бы просто не взять номер точки в сетке, с учетом того, что у вас 8-байтовый ключ?
Для ответа на первый вопрос, давайте рассмотрим ситуацию в одномерном пространстве. Две точки с координатами 0.9 и 1.1, первая получит ключ 0, вторая 1, но расстояние между ними 0.2, то есть в нашем случае меньше метра.
По второму вопросу — ключ выбран таким для того, чтобы можно было легко рассчитать ключи соседних клеток и посмотреть что там. А с точки зрения вычисления — ключ очень простой: два отбрасывания дробной части, сдвиг и побитовое ИЛИ.
По второму вопросу — ключ выбран таким для того, чтобы можно было легко рассчитать ключи соседних клеток и посмотреть что там. А с точки зрения вычисления — ключ очень простой: два отбрасывания дробной части, сдвиг и побитовое ИЛИ.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Поиск маршрутов за 1 человеко-месяц