Да. Это правда интересно. Такую статистику я не помню, да и помнил бы, написать не смог. Но по опыту могу сказать, что ядер очень часто больше двух. Например, один из девайсов, на котором я делал тесты выше iPhone SE (2016 год), на момент выпуска был не особенно мощным. Но в нем уже два ядра. Насколько я помню, даже на low-end девайсах последние годы обычно 2-4 ядра, если не больше.
Да. Я не думал, о таком варианте. И это вариант, вполне можно протестировать. Отказаться от мьютекса это серьезный плюс. Так же хочу отметить, что используя третий поток, мы слегка изменим момент остановки алгоритма. Он может наступить, чуть позже, чем пересекутся волны. Но это, кажется, не должно повлиять на корректность алгоритма, насколько я помню доказательство.
С другой стороны, добавив 3й поток мы получим следующие минусы:
Нам нужно будет копировать приличный объем данных между потоками. Раскрытые вершин много на больших графах.
Нам нужно будет как-то наладить передачу данных о раскрытых вершинах в третий поток из двух рабочих потоков. Как вариант - очередь. Это тоже накладные расходы.
Хорошо бы, чтоб под 3й поток, было отдельное ядро. (Его может не быть на мобильных устройствах.)
Усложнится система.
Но тут, нужно реализовывать и мерить. Может и лучше окажется.
Мой добрый приятель и бывший коллега (@kshalnev) уже после публикации статьи, придумал очень интересную штуку, как уменьшить проверки под мьютексом. Идея применима к любому графу, но опишу ее в терминах графа дорог. Идея в следующем.
Перед запуском алгоритма считаем расстояние между стартом и финишем.
У нас есть консистентная эвристика для A*. А это значит, мы можем понять, сколько времени минимально может потребоваться, чтоб добраться из старта в финиш. По сути, в терминах карты, это время, чтоб доехать из старта до финиша по прямой дороге, на максимально скорости.
Пока в раскрытых вершинах от старта и от финиша у нас меньше половины этого времени - не проверяем, что волны пересеклись. И следовательно не выполняем долгой проверки под мьютексом. Действительно, чтоб волны пересеклись, в одной из волны мы должны рассматривать вершины, в которых будет сохранено время большее, чем половина самого быстрого.
Кажется это может ускорить работу алгоритма. Более того, кажется, что не проверять, что волны пересеклись можно и дольше. И это тоже не должно повлиять на корректность алгоритма.
На этой картинке одна волна от старта к финишу. Классический A*. В нем используется стандартная эвристика: берется расстояние по прямой (на поверхности земли, без учета рельефа) и делится на максимальную скорость.
На примере видно, что есть преимущество перед алгоритмом Дейкстры. Так же видно, что волна ушла к финишу в двое дальше, чем в противоположенном направлении.
Так же на распространение волны очень влияет, есть ли быстрые дороги в регионе прокладки. Если присмотреться, то можно заметить, что именно по магистралям были раскрыты вершины в низу и в направлении от старта.
Спасибо на добром слове, Сергей! Это правда очень хорошая идея. И она подходит для многих случаев. Но ввиду описанных причин, нам пришлось сделать иначе.
На первом скриншоте количество точек примерно равномерно распределено вокруг точки назначения
Уточните п-та на каком скриншоте. Картинка с раскрытыми 90К вершинами есть на 1-й и на 3-й иллюстрациях. Вершины вокруг точки назначения - это вторая картинка на 3-й иллюстрации. И на ней не 90К, а 30К вершин раскрыто.
Комментарий про DFS и переоценку A* уже написал @wataru Спасибо!
Действительно граф дорог имеет ряд интересных особенностей. Он почти планарный (мостов и туннелей не так много.) И еще длинные маршруты почти всегда строятся через очень ограниченное число быстрых дуг (через магистрали). Наличие таких быстрых дуг эксплуатируется в алгоритмах, указанных вами, а так же в Contraction hierarchies, Reach и ATL. Это очень быстрые алгоритмы прокладки маршрута с очень асимптотической сложностью.
Reach - тут сложность зависит от обучающей выборки, но на практике, говорят что результаты хорошие. Я сам Reach не реализовывал и не работал с ним.
К сожалению все эти алгоритмы требуют подготовки индекса перед началом работы. Например, подготовка индекса для Contraction hierarchies требует O(n^2 * log (n) + n*m, где n это кол-во вершин, а m - это кол-во ребер. Индекс имеет существенный размер и считается не быстро. Для карты мира, на хорошем сервере порядка суток занимало.
Сергей, мне кажется, что ваша задумка близка к одному из указанных алгоритмов. Вероятно, к Reach, если я правильно понял. Это очень хорошая и перспективная идея. Если посмотреть, на Reach, то к сожалению, чтоб понять, насколько сильно нужно стремиться к быстрым дорогам, нужно знать, насколько близко вершина лежит от быстрых дорог. А это предрасчет и индекс.
Сложность в среднем O(ln(m)*ln(n)) - выглядит очень круто. Хотя, как я отмечал ранее, в случае поиска кратчайшего пути на графе, желательно оговаривать, о каких дугах и вершинах мы говорим. Поскольку старт и финиш могут быть близко на огромном графе. И для расчета требуется затронуть маленькое число дуг относительно всего графа.
Вы пишите про вершины, лежащие на плоскости ребра. П-та уточните, что имеется ввиду. Существенная доля вершин лежит в плоскости ребра? Верно?
Вы пишите, скорости сопоставимы. Если говорить про дорожную сеть, то формально есть дороги без ограничений. Правда их не много. Но в реальности скорости на дугах часто отличаются раз 20.
Состояние дел с прокладкой маршрутов по графам дорог не плохо было описано в этой обзорной статье: https://arxiv.org/pdf/1504.05140.pdf . Вероятно, там есть что-то похожее и вашу задумку. Если да, то скажите п-та какой это алгоритм. Если нет, но напишите п-та поконкретнее в чем идея.
Коллеги, обзорная статья 2015 года. Если у кто-то знает более новую подобную статью - пришлите ссылку п-та.
Добавление второй волны как улучшает оценку сложности в среднем случае?
Кажется, что просто на константу. Но на большую. Приведу довольно грубые рассуждения для Дейкстра, которые наводят на такую оценку.
Допустим у нас есть граф, вершины которого распределены равномерно на плоскости. Допустим от старта до финиша R метров.
Рассмотрим односторонний Дейкстра на этом графе. Чтоб получить кратчайший путь от старта до финиша нужно раскрыть вершины на круге с центром в старте. Площадь круга будет Pi*R^2.
Представим двусторонний Дейкстра на этом же графе. Чтоб получить кратчайший путь от старта до финиша нужно раскрыть вершины в кругах вокруг старта и финиша. Площадь каждого R/2. Суммарная площадь, на которой раскрыты вершины будет: 2*Pi*(R/2)^2 = (Pi*R^2)/2.
Т.е. в этом частном случае, кол-во раскрытых вершин уменьшиться в двое.
Это не ответ на вопрос. Кол-во раскрытых вершин удобно использовать для оценки сложности алгоритма роутинга, но это не сложность в среднем. И эти рассуждения актуальны для Дейкстра, но не для A*. Я подумаю, над более точным ответом.
Можно ли придумать какой-то частичный индекс?
Уточните п-та вопрос. Индекс, который мог бы обновляться при обновлении весов дуг графа?
1. Для двунаправленного поиска есть довольно тонкий момент, что неизвестно время прихода на финиш, что важно для оценки пробок...
Это правда очень тонкий момент и интересное наблюдение. Кажется этот момент важен при условии, что у нас есть какая-то эвристика позволяющая оценить пробки в будущем. Тогда односторонний A* (только прямая волна) позволит нам их учесть. А для двухстороннего придется придумывать предсказание для финиша. Да еще такое предсказание, чтоб эвристика A* не дала переоценки. У нас были пробки только в текущий момент времени, так что я не столкнулся с указанной проблемой.
2. В OSRM есть второй алгоритм - multi-level dijkstra (MLD). Он позволяет обновлять индекс на лету, но тут тоже сильно будет зависеть от скорости устройства и объема данных
Да. Это правда. Но MLD в OSRM появился в 2017, а мы реализовывали поддержку пробок в Maps.me в 2016.
Да. Это основная идея! Но все же формальное доказательство существенно длиннее. Но и к нему, желательно описание алгоритма, чтоб договориться, что мы доказываем. Мне нравится вариант доказательства корректности - через потенциалы вершин. Думаю, это было бы не плохим дополнением к статье.
Кажется без описания алгоритма не обойтись, если писать статью и доказательство. Я наверно, так сделаю. Завтра или после завтра напишу не большой набросок, в какую сторону смотреть, прямо в этой ветке. А статью уже позже и отдельно. Спасибо, за замечание!
Просто интересно, а сколько там всего суммарно вершин и дуг в графе всех дорог мира?
Примерно сотни миллионов дорожных фичей в OpenStreetMap (https://taginfo.openstreetmap.org/keys/highway#overview). Далее, в среднем 5-7 сегментов на фичу. Т.е. грубо получается 1-2 миллиарда вершин графа дорог. Можно, уменьшить кратно их кол-во рассматривая в качестве вершин только перекрестки. Такой подход не позволит по-простому реализовать разворот в произвольном месте, где он возможен, но он вполне оправдан. Развороты при таком подходе будут возможны только на перекрестках.
И есть вопрос про двусторонний A*. А можно поподробнее остановиться на доказательстве корректности критерия остановки?
Отличный вопрос! Я изначально думал это написать в статье, но она оказалась и без того достаточно объемной. Предлагаю так. Я или напишу ответ на Ваш комментарий, где покажу, корректность алгоритма. Или напишу отдельную статью на эту тему. Как продолжение к этой статье.
Спасибо за статью! В начале прошлого века начали появляться машины, и был бум на автомехаников. Бум прошел. Машины остались. Хороший автомеханик востребован по сей день :) Компьютеры как и машины вошли в нашу жизнь. Думаю, профессии, которые их создают, обслуживают и поддерживают так же будут востребованы.
Все так, но ведь в примере в выводах я предложил написать `int32_t signed_offset = -signed_width;`, где и signed_offset и signed_width знаковые типы. Как раз это нам и позволит уйти от unspecified behaviour, насколько я понимаю. Тогда 8.5.2.1.8 применен не будет. А 7.8.3 будет задействован в строчке выше: `int32_t signed_width = width;` в части value is unchanged.
@code_panik верно ли я понял вашу идею? Если нет, уточните п-та.
Уверен, при написании кода, имеет смысл полагаться на стандарт и на то, что он разрешает, запрещает как-то регламентирует.
Я не мало писал на C++ под мобильные девайсы. Мне иногда доводилось сталкиваться с ошибками, к которым приводил unspecified behaviour. Как раз та самая ситуация, когда обычно поведение одно и тоже (хотя и unspecified), но на каком-нибудь девайсе, в редком случае и только в релизной сборке оно другое. Притом, как правило, этот класс ошибок очень не просто выявить и исправить, т.к. они редко воспроизводятся.
Спасибо большое! Поправил.
Да. Это правда интересно. Такую статистику я не помню, да и помнил бы, написать не смог. Но по опыту могу сказать, что ядер очень часто больше двух. Например, один из девайсов, на котором я делал тесты выше iPhone SE (2016 год), на момент выпуска был не особенно мощным. Но в нем уже два ядра. Насколько я помню, даже на low-end девайсах последние годы обычно 2-4 ядра, если не больше.
Спасибо @v0stok86!
Да. Я не думал, о таком варианте. И это вариант, вполне можно протестировать. Отказаться от мьютекса это серьезный плюс. Так же хочу отметить, что используя третий поток, мы слегка изменим момент остановки алгоритма. Он может наступить, чуть позже, чем пересекутся волны. Но это, кажется, не должно повлиять на корректность алгоритма, насколько я помню доказательство.
С другой стороны, добавив 3й поток мы получим следующие минусы:
Нам нужно будет копировать приличный объем данных между потоками. Раскрытые вершин много на больших графах.
Нам нужно будет как-то наладить передачу данных о раскрытых вершинах в третий поток из двух рабочих потоков. Как вариант - очередь. Это тоже накладные расходы.
Хорошо бы, чтоб под 3й поток, было отдельное ядро. (Его может не быть на мобильных устройствах.)
Усложнится система.
Но тут, нужно реализовывать и мерить. Может и лучше окажется.
Мой добрый приятель и бывший коллега (@kshalnev) уже после публикации статьи, придумал очень интересную штуку, как уменьшить проверки под мьютексом. Идея применима к любому графу, но опишу ее в терминах графа дорог. Идея в следующем.
Перед запуском алгоритма считаем расстояние между стартом и финишем.
У нас есть консистентная эвристика для A*. А это значит, мы можем понять, сколько времени минимально может потребоваться, чтоб добраться из старта в финиш. По сути, в терминах карты, это время, чтоб доехать из старта до финиша по прямой дороге, на максимально скорости.
Пока в раскрытых вершинах от старта и от финиша у нас меньше половины этого времени - не проверяем, что волны пересеклись. И следовательно не выполняем долгой проверки под мьютексом. Действительно, чтоб волны пересеклись, в одной из волны мы должны рассматривать вершины, в которых будет сохранено время большее, чем половина самого быстрого.
Кажется это может ускорить работу алгоритма. Более того, кажется, что не проверять, что волны пересеклись можно и дольше. И это тоже не должно повлиять на корректность алгоритма.
На этой картинке одна волна от старта к финишу. Классический A*. В нем используется стандартная эвристика: берется расстояние по прямой (на поверхности земли, без учета рельефа) и делится на максимальную скорость.
На примере видно, что есть преимущество перед алгоритмом Дейкстры. Так же видно, что волна ушла к финишу в двое дальше, чем в противоположенном направлении.
Так же на распространение волны очень влияет, есть ли быстрые дороги в регионе прокладки. Если присмотреться, то можно заметить, что именно по магистралям были раскрыты вершины в низу и в направлении от старта.
Спасибо на добром слове, Сергей! Это правда очень хорошая идея. И она подходит для многих случаев. Но ввиду описанных причин, нам пришлось сделать иначе.
Желаю вам удачи в ваших начинаниях!
Уточните п-та на каком скриншоте. Картинка с раскрытыми 90К вершинами есть на 1-й и на 3-й иллюстрациях. Вершины вокруг точки назначения - это вторая картинка на 3-й иллюстрации. И на ней не 90К, а 30К вершин раскрыто.
Комментарий про DFS и переоценку A* уже написал @wataru Спасибо!
Присоединяюсь к вопросу о ссылках почитать про алгоритм.
Сергей.
Действительно граф дорог имеет ряд интересных особенностей. Он почти планарный (мостов и туннелей не так много.) И еще длинные маршруты почти всегда строятся через очень ограниченное число быстрых дуг (через магистрали). Наличие таких быстрых дуг эксплуатируется в алгоритмах, указанных вами, а так же в Contraction hierarchies, Reach и ATL. Это очень быстрые алгоритмы прокладки маршрута с очень асимптотической сложностью.
Например, Contraction hierarchies - O(sqrt(n) * log(n)), где n кол-во вершин (https://en.wikipedia.org/wiki/Contraction_hierarchies)
Reach - тут сложность зависит от обучающей выборки, но на практике, говорят что результаты хорошие. Я сам Reach не реализовывал и не работал с ним.
К сожалению все эти алгоритмы требуют подготовки индекса перед началом работы. Например, подготовка индекса для Contraction hierarchies требует O(n^2 * log (n) + n*m, где n это кол-во вершин, а m - это кол-во ребер. Индекс имеет существенный размер и считается не быстро. Для карты мира, на хорошем сервере порядка суток занимало.
Сергей, мне кажется, что ваша задумка близка к одному из указанных алгоритмов. Вероятно, к Reach, если я правильно понял. Это очень хорошая и перспективная идея. Если посмотреть, на Reach, то к сожалению, чтоб понять, насколько сильно нужно стремиться к быстрым дорогам, нужно знать, насколько близко вершина лежит от быстрых дорог. А это предрасчет и индекс.
Сложность в среднем O(ln(m)*ln(n)) - выглядит очень круто. Хотя, как я отмечал ранее, в случае поиска кратчайшего пути на графе, желательно оговаривать, о каких дугах и вершинах мы говорим. Поскольку старт и финиш могут быть близко на огромном графе. И для расчета требуется затронуть маленькое число дуг относительно всего графа.
На всякий случай, вот статья с кратким описание сути Reach и ряда других алгоритмов: https://habr.com/ru/companies/2gis/articles/326638/
Посмотреть в код стоит вот сюда:
https://github.com/mapsme/omim/blob/1892903b63f2c85b16ed4966d21fe76aba06b9ba/routing/edge_estimator.cpp#LL136C14-L136C14
А так же можно и вот сюда:
https://github.com/mapsme/omim/blob/1892903b63f2c85b16ed4966d21fe76aba06b9ba/routing/single_vehicle_world_graph.cpp#L149
https://github.com/mapsme/omim/blob/dc7b25dd8ea2bcf0fde9d1a9a6c5ae79e5c7cdd6/routing/base/astar_algorithm.hpp#LL108C3-L108C3
Пробовали. Там иначе переоценка получается. Так же пробовали ALT.
Поясните п-та.
Сергей, спасибо за комментарий и за предложение!
Вы говорите про алгоритм с индексом или без?
Вы пишите про вершины, лежащие на плоскости ребра. П-та уточните, что имеется ввиду. Существенная доля вершин лежит в плоскости ребра? Верно?
Вы пишите, скорости сопоставимы. Если говорить про дорожную сеть, то формально есть дороги без ограничений. Правда их не много. Но в реальности скорости на дугах часто отличаются раз 20.
Состояние дел с прокладкой маршрутов по графам дорог не плохо было описано в этой обзорной статье: https://arxiv.org/pdf/1504.05140.pdf . Вероятно, там есть что-то похожее и вашу задумку. Если да, то скажите п-та какой это алгоритм. Если нет, но напишите п-та поконкретнее в чем идея.
Коллеги, обзорная статья 2015 года. Если у кто-то знает более новую подобную статью - пришлите ссылку п-та.
Кажется, что просто на константу. Но на большую. Приведу довольно грубые рассуждения для Дейкстра, которые наводят на такую оценку.
Допустим у нас есть граф, вершины которого распределены равномерно на плоскости. Допустим от старта до финиша R метров.
Рассмотрим односторонний Дейкстра на этом графе. Чтоб получить кратчайший путь от старта до финиша нужно раскрыть вершины на круге с центром в старте. Площадь круга будет Pi*R^2.
Представим двусторонний Дейкстра на этом же графе. Чтоб получить кратчайший путь от старта до финиша нужно раскрыть вершины в кругах вокруг старта и финиша. Площадь каждого R/2. Суммарная площадь, на которой раскрыты вершины будет: 2*Pi*(R/2)^2 = (Pi*R^2)/2.
Т.е. в этом частном случае, кол-во раскрытых вершин уменьшиться в двое.
Это не ответ на вопрос. Кол-во раскрытых вершин удобно использовать для оценки сложности алгоритма роутинга, но это не сложность в среднем. И эти рассуждения актуальны для Дейкстра, но не для A*. Я подумаю, над более точным ответом.
Уточните п-та вопрос. Индекс, который мог бы обновляться при обновлении весов дуг графа?
Это правда очень тонкий момент и интересное наблюдение. Кажется этот момент важен при условии, что у нас есть какая-то эвристика позволяющая оценить пробки в будущем. Тогда односторонний A* (только прямая волна) позволит нам их учесть. А для двухстороннего придется придумывать предсказание для финиша. Да еще такое предсказание, чтоб эвристика A* не дала переоценки. У нас были пробки только в текущий момент времени, так что я не столкнулся с указанной проблемой.
Да. Это правда. Но MLD в OSRM появился в 2017, а мы реализовывали поддержку пробок в Maps.me в 2016.
Спасибо за комментарии!
Да. Это основная идея! Но все же формальное доказательство существенно длиннее. Но и к нему, желательно описание алгоритма, чтоб договориться, что мы доказываем. Мне нравится вариант доказательства корректности - через потенциалы вершин. Думаю, это было бы не плохим дополнением к статье.
Кажется без описания алгоритма не обойтись, если писать статью и доказательство. Я наверно, так сделаю. Завтра или после завтра напишу не большой набросок, в какую сторону смотреть, прямо в этой ветке. А статью уже позже и отдельно. Спасибо, за замечание!
Примерно сотни миллионов дорожных фичей в OpenStreetMap (https://taginfo.openstreetmap.org/keys/highway#overview). Далее, в среднем 5-7 сегментов на фичу. Т.е. грубо получается 1-2 миллиарда вершин графа дорог. Можно, уменьшить кратно их кол-во рассматривая в качестве вершин только перекрестки. Такой подход не позволит по-простому реализовать разворот в произвольном месте, где он возможен, но он вполне оправдан. Развороты при таком подходе будут возможны только на перекрестках.
Отличный вопрос! Я изначально думал это написать в статье, но она оказалась и без того достаточно объемной. Предлагаю так. Я или напишу ответ на Ваш комментарий, где покажу, корректность алгоритма. Или напишу отдельную статью на эту тему. Как продолжение к этой статье.
Спасибо за статью!
В начале прошлого века начали появляться машины, и был бум на автомехаников. Бум прошел. Машины остались. Хороший автомеханик востребован по сей день :) Компьютеры как и машины вошли в нашу жизнь. Думаю, профессии, которые их создают, обслуживают и поддерживают так же будут востребованы.
Спасибо за отличную статью!
Кажется, что так начиная с С++20. Я писал статью полагаясь на стандарт С++17, и не досмотрел, что-то поменяется в стандарте C++20 :)
С другой стороны, пока есть вероятность, что код могут скомпилировать, компилятором C++17, я бы не поленился и привел руками.
Все так, но ведь в примере в выводах я предложил написать `int32_t signed_offset = -signed_width;`, где и
signed_offsetиsigned_widthзнаковые типы. Как раз это нам и позволит уйти от unspecified behaviour, насколько я понимаю. Тогда 8.5.2.1.8 применен не будет. А 7.8.3 будет задействован в строчке выше: `int32_t signed_width = width;` в части value is unchanged.@code_panik верно ли я понял вашу идею? Если нет, уточните п-та.
Вот пример из выводов:
Уверен, при написании кода, имеет смысл полагаться на стандарт и на то, что он разрешает, запрещает как-то регламентирует.
Я не мало писал на C++ под мобильные девайсы. Мне иногда доводилось сталкиваться с ошибками, к которым приводил unspecified behaviour. Как раз та самая ситуация, когда обычно поведение одно и тоже (хотя и unspecified), но на каком-нибудь девайсе, в редком случае и только в релизной сборке оно другое. Притом, как правило, этот класс ошибок очень не просто выявить и исправить, т.к. они редко воспроизводятся.