При поиске кратчайшего пути на графах большого размера плохо работает традиционная оценка стоимости т.к. данные заведомо не помещаются в памяти и общая стоимость больше зависит от числа обращений к диску нежели от числа просмотренных рёбер. А число дисковых операций — весьма субъективный фактор, зависимый от сложно формализуемой пригодности графа к хранению на диске в форме удобной для конкретного алгоритма. Кроме того, очень важным становится компактность — количество информации в расчете на ребро и вершину.
Под катом представлена обобщенная эвристика к алгоритму A*, полезная именно в свете практической пригодности на больших графах при ограниченных ресурсах, например, на мобилке.
Итак, наша задача — построение кратчайшего пути по графу из точки в точку. При этом граф достаточно велик, чтобы мы не имели возможности держать его целиком в памяти, а также невозможен предрасчет по сколь-нибудь значительному количеству вершин. Отличный образец — дорожный граф OSM. На данный момент число вершин в OSM превысило 4.6 млрд, общее число объектов — 400 млн.
Понятно, что в таких условиях поиск более-менее протяженного маршрута чистым алгоритмом Дейкстры или Левита невозможен в силу того, что мы не располагаем количеством памяти, необходимым для хранения промежуточных данных.
Как поступает алгоритм Дейкстры?
- Заносим в приоритетную очередь стартовую точку с нулевой стоимостью.
- Пока в очереди что-то есть — пусть вершина V, для каждого исходящего ребра (E), которое мы до сих пор не просматривали:
- проверяем что это не искомое ребро, если да, то конец;
- подсчитываем стоимость прохода E;
- и заносим конечную вершину ребра E в очередь со стоимостью её достижения — стоимость достижения V + стоимость E.
В результате для разреженных (например, геометрических) графов получаем стоимость O(n*log(n) + m*log(n)), где n-число просмотренных вершин, m-число просмотренных ребер.
Фиг.1 Здесь мы видим найденный маршрут и просмотренные при этом ребра.
Проблема в том, что алгоритм Дейкстры не использует никакой информации о свойствах графа и искомого маршрута и при его работе (распространении т.н. «волны») периметр этой «волны» движется от искомой точки во всех направлениях без какой-либо дискриминации.
С другой стороны, на геометрических графах, например, развитой дорожной сети, есть смысл стимулировать распространение «волны» по направлению к цели и штрафовать за остальные направления. Эта идея реализована в алгоритме A*, который является обобщением алгоритма Дейкстры.
В A* стоимость вершины при помещении её в приоритетную очередь не просто равна пройденному пути, а включает еще и оценку пути оставшегося. Как нам получить эту оценку?
Стоит отметить, что это должны быть достаточно вычислительно-дешевая оценка т.к. выполняется она большое число раз. Первое что приходит в голову — вычислить геометрическое расстояние от текущей точки до финиша и исходить из этого, например: осталось 10 км — средняя скорость при движении по городу 20 км/ч, значит наша оценка — полчаса.
При этом, если ребро ведет нас по направлению к финишу, оценка для него будет уменьшаться и компенсировать пройденный путь.
Для ребер, ведущих от цели, эта оценка станет расти, в результате такие точки попадут в очередь с большим весом и вполне вероятно, что до них дело так и не дойдёт.
Примерно такого же эффекта можно достичь, кстати, с помощью техники Beam Search, где принудительно ограничивается размер приоритетной очереди и «недостойные» с точки зрения эвристики кандидаты просто отбрасываются.
Фиг.2 Здесь мы видим поиск того же маршрута с использованием описанной эвристики, почувствуйте разницу.
A* превращается в алгоритм Дейкстры если оценка стоимости возвращает 0, как если бы мы считали, что остаток пути промчимся с бесконечной скоростью.
A* относится т.н. информированным алгоритмам т.к. в эвристике мы используем предположение, что движение в направлении цели скорее приведёт нас к успеху.
Каковы должны быть свойства функции оценки? Она должна быть правдоподобной. Как мы уже выяснили, слишком оптимистичная оценка сводит на нет наши попытки уменьшить просматриваемую часть графа. С другой стороны, слишком пессимистичная оценка заставит алгоритм построить путь строго по направлению, невзирая ни на что. Вряд ли это нас устроит.
Реалистичная оценка должна опираться на свойства графа а лучше на модель данных. Например, вычисляться из уровня загруженности дорог в это время суток и уровня транспортной связности графа. Например, в городе без рек хорошо работает Манхэттенское расстояние.
Но тут сразу возникает масса нюансов:
- Как определить что мы в городе? Это не так уж и дешево.
- А ничего, что большая часть городов построена на реках?
- В городе разные участки дорог могут быть загружены сильно по разному.
- А если мы должны проехать через множество городов и рек?
Можно использовать и разные эвристики в духе метода ветвей и границ:
- Находим путь с очень пессимистичной эвристикой, из чего следует, что, предположительно, есть и более эффективные маршруты.
- Теперь мы будем использовать стоимость найденного маршрута как оценку сверху, просто не включая в приоритетную очередь претендентов, которые заведомо не могут дать нам маршрут более эффективный, чем уже найденный.
- Делаем оценку менее пессимистичной и вновь строим маршрут с верхней границей стоимости.
- Получаем новую оценку.
- Продолжаем так до тех пор, пока не получим удовлетворительное решение.
Есть еще одна проблема с оценкой стоимости, о которой нельзя не упомянуть.
В жизни геометрически близкие объекты могут быть достаточно удаленными с точки зрения дорожного графа. Например, находиться на разных сторонах реки, горной гряды, моря… В таком случае оценка, основанная на геометрической близости начнёт усугублять ситуацию, упорно направляя «волну» в неправильном направлении.
Фиг.3 Вот так выглядит просмотренная A* часть графа OSM для поиска пути из Италии в Албанию.
Впрочем, это всё равно лучше чем алгоритмом Дейкстры. Хорошо видно как заполнив всю Италию, «волна» начала переливаться через край, набрала скорость и быстро достигла цели.
Фиг.4 А вот так выглядит просмотренная часть графа для алгоритма Дейкстры. По сравнению с ней всё не так уж и мрачно.
А можно ли еще как-то улучшить алгоритм, что по этому поводу говорит Сomputer Sience?
Двунаправленный поиск
Можно пустить две A* волны навстречу друг другу. Это называется bidirectional search и на первый взгляд кажется очень привлекательной идеей. В самом деле, при хорошей транспортной связности “волна” представляет собой эллипсоид, две малых волны, пущенные навстречу, заметут меньшую площадь по сравнению с одной большой. С другой стороны, возникает проблема обнаружения встречи «волн», точек в их периметрах может быть довольно много и проверять на каждом шагу наличие ребра в чужом периметре не так уж и дешево.
Фиг.5 встречные волны Дейкстры
Возможно, с этим можно было бы и смириться при реальном выигрыше в объеме просмотренной части графа. Но вот если мы рассмотрим вышеописанный пример поиска проезда из Италии в Албанию, то обнаружим, что двунаправленный поиск нам ничем не поможет, а только усугубит ситуацию т.к. кроме заливки всей Италии мы вынуждены будем просмотреть и всю Грецию с половиной Балкан, прежде чем волны встретятся. Ибо вместо одной «волны», упёршейся в препятствие, будем иметь две таковых.
Иерархические подходы
Использование иерархии дорог
Некоторые коммерческие системы, например StreetMap USA, используют для роутинга тот факт, что хорошо спланированная дорожная сеть имеет двухуровневую природу — есть сеть местных дорог и (значительно меньшая) сеть шоссе для поездок на дальние расстояния. Представляется естественным использовать этот факт. Вводятся шлюзы (transit nodes) — вершины, на которых происходит переход из одного уровня в другой. Нахождение “достаточно длинного” пути сводится к нахождению путей от:
- исходной точки до нескольких ближайших шлюзов;
- нескольких ближайших шлюзов до финальной точки;
- кратчайшего маршрута от любого из начальных шлюзов до любого из финальных, это, конечно, делается за один сеанс.
Фиг.6 Кусочек StreetMap
Выгоды такого подхода очевидны. Минусы таковы:
- Не везде дорожная сеть хорошо спланирована, кое-где она выросла стихийно, следовательно, исходный посыл не работает.
- Верхнеуровневая сеть должна быть связной и выверенной. Из OSM, например, невозможно получить такую сеть (лёгким движением руки) просто отфильтровав дороги по классам.
- Институт шлюзов также требует много ручной работы.
Построение иерархии графа
Если нет возможности и/или желания выверять граф, остаётся возможность построить иерархию автоматически.
Так или иначе, эксплуатируется идея, что хоть граф и не выверен, тем не менее, атрибуты рёбер позволяют строить маршруты приемлемого качества. Но в силу размеров графа, построение тем же A* в рабочем режиме непозволительно дорого.
Например, это может выглядеть так:
- на этапе предрасчета выбирается множество (пусть даже случайных) вершин;
- для пар пространственно удаленных вершин обычным A* строятся кратчайшие маршруты;
- на основе построенных маршрутов ведётся статистика пройденных рёбер;
- после того, как набралось достаточное количество данных, посещенные рёбра объявляются следующим уровнем иерархии;
- последовательно идущие рёбра без ветвлений сливаются в «макрорёбра» с сохранением стоимости проезда;
Построенный граф может быть снова подвержен описанной процедуре, таким образом строится необходимое число иерархий.
Маршрутизация в таком иерархическом графе осуществляется двунаправленным поиском (A* или алгоритмом Дейкстры).
Сепараторы
Основной идеей метода является попытка разделения графа на компоненты путём удаления небольшой части ребер — сепараторов. Эти сепараторы и предварительно вычисленные пути между ними образуют следующую иерархию. Утверждается [1], что затратив O(n*log(n)**3) времени и пространства на диске для предварительного расчета, можно выполнять запросы за O(sqrt(n)*log(n))
Grid Based Transit Nodes
Это в общем та же идея с сепараторами, но в целях масштабирования и простоты граф делится на фрагменты решеткой или квадро-деревом, ребра, которые пересекают границы фрагментов становятся транзитными. Понятно, что цена этому — эффективность. В плюсах — высокая автоматизация и как следствие отсутствие человеческого фактора.
Таблицы расстояний
На вышестоящих уровнях иерархии в процессе поиска пути не ищутся, а стоимость подсчитывается на основе пред-вычисленных таблиц расстояний между транзитными нодами. Когда маршрут определен, пути восстанавливаются локальным поиском.
Фиг.7 [1]
Reach [3]
Идея метода такова — замечено, что при построении длинных оптимальных маршрутов, «локальные» рёбра посещаются только в самом начале или конце маршрута. Следовательно, построив некоторое количество «обучающих» длинных маршрутов, можно понять, насколько близко расположено то или иное ребро к любому из концов маршрута.
Для некоторого обучающего маршрута P(s…..u.v…...t) вводится показатель reach — минимальное расстояние до концов reach(uv) = min(dist(s…..u), dist(v…..t)).
На всём обучающем множестве reach(uv) — максимальное значение на всех маршрутах, где встретилось ребро (uv).
При «боевом» поиске мы вдали от старта и финиша просто будем стараться избегать рёбер с маленьким значением reach.
Фиг.8 [21]
Идея метода очень красивая, вопросы вызывает лишь качество обучающей выборки, её достаточность и ресурсы, потраченные на обучение.
Целеустремленные алгоритмы
Arc-Flags [4]
Граф делится на фрагменты. Проводится обучение построением кратчайших маршрутов между предопределенными точками. При построении обучающего пути, для каждого ребра сохраняется факт, что через него проходит кратчайший маршрут в клетку финальной точки.
Таким образом для каждого ребра мы храним маску флагов, в какие фрагменты графа можно через это ребро добраться кратчайшим путём.
Специфические недостатки этого метода видны невооруженным взглядом:
- Количество фрагментов графа не может быть велико, 8К фрагментов (что не так уж и много) дадут нам (предположительно несжимаемый) килобайт на каждое ребро. Sic!
- Надо быть очень осторожным с нарезкой фрагментов, внутри фрагмента граф должен быть связным.
ALT [5]
Из всех вершин выбирается небольшое количество landmarks: ?. В изначальном варианте для каждой вершины предварительно рассчитывались стоимости до каждого ?. Это требовало колоссального количества дополнительной памяти и в дальнейшем требования смягчились и вершины стали группировать.
Поиск в ALT осуществляется как в A*, но оценка оставшегося пути делается на основе рассчитанных стоимостей. Пусть мы рассматриваем ребро (u,v) на пути к целевой вершине t. Для каждой ? в соответствии с неравенством треугольника мы имеем оценку оставшейся части пути (через ?): dist(?, t) ? dist(?, v) ? dist(v, t) и dist(v, ?) ? dist(t, ?) ? dist(v, t). Минимум для всех ? и даст искомую оценку.
Фиг.9
Предварительные итоги
Мы видим два основных направления, в которых идёт развитие:
- Иерархии. Позволяют весьма эффективно строить пути на больших расстояниях в структурированных графах. Но на маленьких расстояниях дешевле пользоваться обычным A* или Дейкстрой. Следовательно существует “серая” область, где оба алгоритма работают посредственно.
Кроме того, на аморфных графах попытка построить иерархию может лишь привести к проблемам. Представим себе граф в виде прямоугольной решетки из равнозначных дорог. При движении в некотором направлении правильным решением будет поворачивать в случайном направлении с вероятностью, связанной с направлением. Т.е. если азимут к цели составляет 45°, стоит с равной вероятностью поворачивать направо и налево, чтобы не создавать пробок.
Попытка же построить на такой сетке иерархию приведет к тому, что дорожная сеть станет использоваться неэффективно.
- Использование внутренней природы графа для принятия решения о направлении движения к цели. Идея выглядит многообещающей, но вызывает много вопросов. Основная проблема — человеческий фактор. Что lanmark’и, что фрагменты Arc-Flags требуют участия эксперта, если пустить их определение на самотёк, легко можно получить не то, что доктор прописал.
Кроме того, требуется (нелинейное от размера графа) количество дополнительной памяти.
Вот «если бы губы Никанора Ивановича да приставить к носу Ивана Кузьмича, да взять сколь-нибудь развязности, какая у Балтазара Балтазаровича, да, пожалуй…» ©
Справедливости ради стоит сказать, что таких попыток немало, некоторые из них можно найти в списке источников данной статьи. Но мы, конечно же, не изменим себе и придумаем свой собственный, «не имеющий аналогов» метод. ?
Эвристика
Поставим задачу разработать простую и дешевую (и вычислительно и с точки зрения дополнительно хранимой информации) эвристику оценки стоимости пути из одной точки в другую на основе их географических координат. Прямое расстояние не подходит, оно может ошибаться весьма сильно, достаточно посмотреть на Гибралтар и Танжер.
Идея восходит к этой работе.
- Раз уж мы работаем с OSM, масштаб графа — вся планета.
- Разобьем пространство сеткой в 1°, да, это даёт искажения к полюсам, но мы ведь разрабатываем всего лишь оценку.
- При построении графа будем растеризовать пути на этой сетке, допустим, для 2-го переулка Крупской в Новосибирске мы должны пометить клеточку, соответствующую 55°с.ш. и 82°в.д.
- После растеризации всех известных нам дорог, получим карту населенности с точностью до градуса.
Фиг.10 — число дорог на квадратный градус в логарифмической шкале
- Будем рассматривать нашу карту как граф, где населенные клеточки — вершины.
- Будем считать, что если соседние клеточки населены, то это ребро, из одной можно проехать в другую, стоимость прямого проезда — 111 км на экваторе, стоимость проезда наискосок умножается на корень из 2.
- Если в этом графе мы запустим волну в соответствии с алгоритмом Дейкстры, запоминая стоимость достижения каждой вершины, это даст нам оценку стоимости пути до финиша в любой достижимой точке. Например, если пустить волну из Новосибирска, это будет выглядеть так:
Фиг.11 Оценка стоимости проезда из Нск, чем ближе к оранжевому, тем длинней путь.
Итак, для поиска:
- Мы храним только по биту на квадратный градус поверхности.
- Один раз запускаем волну по этой битовой карте для финальной точки.
- Для любой вершины в графе, зная её координаты, мы за константное время получаем оценку стоимости проезда от этой точки до финиша.
Но ведь градус — это довольно грубая сетка, некоторые проливы могут слипнуться, например, «маленький остров» с Нормандией.
Не беда, в OSM есть тип — береговая линия. Мы растеризуем береговые линии и разрешим ходить из клетки, помеченной как прибрежная, только на «материковые» клетки.
Фиг.12 Береговая линия OSM
Но тут выясняется, что:
- береговая линия есть не везде;
- Япония и др. целиком состоит из прибрежных клеток;
- Гибралтар и Танжер оказались в одной клетке;
- ...
Ок, придется руками нарисовать разделительные линии в важных проливах, растеризовать их и запрещать пересекать при распространении волны.
Благо, это одноразовая работа, а таких проливов не очень много.
Вот, например, распространение «волны» из Италии, обратим внимание на Гибралтарский пролив.
Фиг.13 Оценка стоимости проезда в Италию, чем ближе к оранжевому, тем длиннее путь.
В целом схема приемлема, но:
- она требует ручной работы;
- ручной работы много;
- надо быть очень осторожным, если на одну клетку легло несколько разделительных линий.
Возможно, здесь хорошо сработает вариант, когда каждая «прибрежная» клетка представлена квадро-деревом, распространение волны следует проводить и по элементам квадродерева.
Но всё же чувствуется во всём этом какая-то натяжка, поэтому в дело вступает План Б.
План Б.
- Пусть мы имеем вышестоящий уровень иерархию графа, полученный, например, способом, описанным в разделе «построение иерархии графа».
- Этот уровень достаточно груб для того, чтобы поиск на любые расстояния в нем не представлял проблем.
- Итак, мы имеем на руках путь, построенный на более высоком уровне иерархии графа.
Фиг.14 Путь, проложенный по верхнеуровневому графу.
- Нанесем на этот маршрут опорные точки, например, через каждые 500 км, включая финиш, конечно
Фиг.15 Опорные точки.
- Для каждой опорной точки мы знаем остаток пути от неё до финиша. Теперь эвристика остатка пути для A* будет состоять из двух частей:
- геометрического расстояния до текущей опорной точки;
- остаток пути от текущей опорной точки до финиша.
- В начале поиска текущей назначается первая опорная точка. Как только ма приближаемся к ней на геометрическое расстояние ближе чем 200 км (условно, конечно), начинаем ориентироваться на следующую опорную точку. И так до самого финиша.
- Результат таков:
Фиг. 11 Хорошо видно, как волна начинает расползаться вширь, когда опорный путь резко меняет направление. Тем не менее, общий объем прочитанных данных весьма невелик. Наблюдается также ускорение в ~20 раз.
- Больше всего эта техника напоминает изображение из шапки к данной статье. Поэтому автор и дал ей название M* («M» значит «морковка»).
Выводы
Итак, на суд читателя представлены два варианта эвристики подсчета стоимости остатка пути для A*.
Для обоих вариантов:
- проверена их работоспособность на практике;
- скорость работы A* примерно одинакова, для указанного пути это 4.5 сек (рядовой десктоп) с чтением и распаковкой данных, 0.5 сек — только проход волны на разогретом кэше;
- количество дополнительно хранимой информации минимально — 0.2% для второго варианта, для первого еще меньше;
- т.к. A* работает с исходным графом, нет никаких препятствий к использованию временных ограничений, например, паромов, разводных мостов, данных о пробках…
Как бы то ни было, это еще один инструмент для работы с графами, весьма полезный в условиях ограниченных ресурсов и/или неограниченных данных. В частности, никто не запрещает использовать эту же технику для двустороннего поиска.
Peter Sanders and Dominik Schultes
[2] Combining Hierarchical and Goal-Directed Speed-Up Techniques for Dijkstra’s Algorithm
Reinhard Bauer, Daniel Delling, Peter Sanders, Dennis Schieferdecker, Dominik Schultes, and Dorothea Wagner
[3] R. J. Gutman. Reach-Based Routing: A New Approach to Shortest Path Algorithms Optimized for Road Networks. In Proceedings of the 6th Workshop on Algorithm Engineering, 2004
[4] E. Kohler, R. H. Mohring, and H. Schilling. Acceleration of Shortest Path and Constrained
Shortest Path Computation. In Proceedings of the 4th Workshop on Experimental Algorithms
(WEA’05), Lecture Notes in Computer Science, pages 126–138. Springer, 2005.
[5] Goldberg, A.V., Werneck, R.F.: Computing Point-to-Point Shortest Paths from External Memory. In: Proceedings of the 7th Workshop on Algorithm Engineering and Experiments (ALENEX 2005), pp. 26–40. SIAM (2005)
[6] Defining and Computing Alternative Routes in Road Networks
Jonathan Dees, Robert Geisberger, and Peter Sanders
[7] Alternative Routes in Road Networks
Ittai Abraham, Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck
[8] Partitioning Graphs to Speedup Dijkstra’s Algorithm
ROLF H. MOHRING and HEIKO SCHILLING
[9] SHARC: Fast and Robust Unidirectional Routing
Reinhard Bauer Daniel Delling
[10] Cambridge Vehicle Information Technology Ltd. Choice Routing
[11] Combining Hierarchical and Goal-Directed Speed-Up Techniques for Dijkstra’s Algorithm?
Reinhard Bauer, Daniel Delling, Peter Sanders, Dennis Schieferdecker, Dominik Schultes, and Dorothea Wagner
[12] Fast and Exact Shortest Path Queries Using Highway Hierarchies
Dominik Schultes
[13] Engineering Highway Hierarchies
Peter Sanders and Dominik Schultes
[14] Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks
Robert Geisberger, Peter Sanders, Dominik Schultes, and Daniel Delling
[15] Dynamic Highway-Node Routing
Dominik Schultes and Peter Sanders
[16] A FAST AND HIGH QUALITY MULTILEVEL SCHEME FOR PARTITIONING IRREGULAR GRAPHS
GEORGE KARYPIS AND VIPIN KUMAR
[17] Multilevel Algorithms for Partitioning Power-Law Graphs
Amine Abou-rjeili and George Karypis
[18] Impact of Shortcuts on Speedup Techniques?
Reinhard Bauer, Daniel Delling, and Dorothea Wagner
[19] Transit Node Routing based on Highway Hierarchies
Peter Sanders Dominik Schultes
[20] In Transit to Constant Time Shortest-Path Queries in Road Networks?
Holger Bast Stefan Funke Domagoj Matijevic Peter Sanders Dominik Schultes
[21] Reach for A?: an Efficient Point-to-Point Shortest Path Algorithm Andrew V. Goldberg
PS: статья по результатам доклада на DUMP 2017
Комментарии (43)
dmagin
17.04.2017 12:20+2Хорошая статья, спасибо ),
У меня такой вопрос. А почему при оценке остатка пути не используются резистивные расстояния? Или потенциалы узлов, которые появляются после выбора начального и конечного? Данный подход я на хабре описывал, как пример использования потенциалов лапласиана. Тут чистая математика без эвристик и костылей.
Просто я в данной области чисто теоретик и от практики далек. Видимо, на практике это не взлетает по каким-то причинам, о которых и спрашиваю. Невозможно посчитать матрицу резистивных расстояний для больших графов? Или еще что-то?
zzeng
26.04.2017 12:43Насколько я понял, метод заключается в наложении разности потенциалов на стартовую и финишные точки,
затем с помощью лапласиана находятся потенциалы в узлах и кратчайший путь прокладывается по максимальному потоку.
Боюсь, что для больших графов это будет весьма расточительно,
особенно, учитывая то, что даже когда старт и финиш рядом, считать придётся весь граф или значительную его часть.dmagin
26.04.2017 15:51Спасибо ). Я, конечно, надеялся на что-нибудь более конкретное. Типа, в таком-то году такие-то ребята пробовали данный подход, но столкнулись с такими-то проблемами, которые описали в такой-то статье ).
Фишка в том, что резистивные расстояния (ну или потенциалы 2-го порядка) считаются только один раз (для всего графа), и редко пересматриваются (для пересмотра уже не надо по новой все пересчитывать). А потенциалы узлов строятся «на лету» при заданных начальной и конечной точках j, k по приведенной в статьей формуле (2.5):
dUi = dCjk (Uik + Ujk — Uij)/2
Здесь Uik — заранее посчитанные потенциалы (резистивные расстояния). Величина dCjk — произвольная, можно взять 1.
При этом совсем необязательно считать потенциалы узлов всего графа. Берем за начальный узел исходную точку и считаем потенциалы для всех соседних. Далее выбираем из них (минимальный или максимальный — от знака dCjk) и повторяем процедуру. Пока не придем в заданный. Это быстрый и надежный вариант, но он может оказаться не самым оптимальным, да.
Природа сама использует подобную процедуру, чтобы определить, по каким маршрутам лететь фотонам/электронам из области высокого потенциала к низкому.zzeng
27.04.2017 07:43Если честно, меня немного пугает перспектива обращать пусть даже сильно разреженную матрицу размером 300млн Х 300млн, хотя бы и всего один раз :) Она ведь сильно вырожденная, за точностью чуть не уследил и бац!
С Дейкстрой и А* всё проще — простая идея, интуитивно понятное поведение, простая реализация.dmagin
27.04.2017 08:21+1Интересная, имхо, задача — обращение таких матриц. Даже не обращение, а именно вычисление всех резистивных расстояний (потенциалов) для огромных разреженных матриц.
Я не сталкивался, но в алгоритме ранжирования страниц Page Ranking схожая проблема. Правда там рассчитываются потенциалы 1-го порядка, а не 2-го. Но размер матриц вряд ли меньше. Гугл вроде как-то справляется (если еще использует его).
ACPrikh
17.04.2017 12:53+1Если «условия ограниченных ресурсов[памяти — времени работы процессора] и/или неограниченных данных», то напрашивается использование предварительных вычислений. Таблица предварительно вычисленных и хранимых расстояний между узлами высокой, средней (средних) и мелкой иерархии.
Таблицы Атлас мира — европы — Италии — Тосканы с Лацио.zzeng
17.04.2017 12:53Это и есть иерархический подход.
ACPrikh
26.04.2017 14:21В данном случае иерархический. Только акцент делаю не на иерархии, а в предварительных вычислениях. Задачу можно решать за счет адресного пространства данных, а можно за счёт мощности процессора.
zzeng
26.04.2017 15:11У предварительных вычислений беда с ребрами где динамически меняются стоимости.
ACPrikh
26.04.2017 16:09Здесь надо (пардон, имею в виду по смыслу надо) оценить насколько велик вес динамических данных и насколько он «расползается» по сети. Например, ремонт дороги, как правило, приведет к локальному объезду. А шторм на морской переправе может кардинально сменить дальний маршрут. Но в таком случае, переходим к предварительно просчитанному варианту «Б».
Ещё говорил о Дата-ориентированном программировании. Может слишком абстрактно получилось и поэтому непонятно. Тогда так. Автомобилист, при поиске пути проезда не чертит колесами такие маршруты, как в алгоритме. А почему? Он использует указатели — «предварительно просчитанные» маршруты. Разумеется, в идеальном случае расставленных обильно на перекрестках.
К тому же используются туннелирование — наиболее часто используемые маршруты чисто статистически. То есть люди не едут из произвольных точек, а из таких-то чаще туда-то. Причем летом — одни маршруты, зимой — другие и.т.п. То есть решение как бы хочет привязаться к конкретной сети и обстановке. Вот эту конкретику я и обозвал «дата-ориентированный подход».zzeng
27.04.2017 07:34Ну почему шторм, например паром по расписанию или разводные мосты.
На большой площади предрасчет будет будет зависеть от того, с какого направления куда мы едем.
Это уже накладно. Планом Б не отделаешься.
Ориентироваться на пользовательские привычки тоже опасно. Зимой одни привычки, летом другие. А в межсезонье? В одном городе выпал снег, а в другом нет, на какую модель ориентироваться?
ACPrikh
27.04.2017 08:48Шторм, ремонт, аварии (последнее чаще) — как нерегулярное явление. Все расписания и периодические явления предрасчитываются на доп шкале времени. То есть не только схема проезда, но и расписание проезда.
Направлений мало до безобразия. Если из Москвы их десятки, то для Пензы пяток, а для Гадюкино вообще одно. Фазовое пространство реальности вырождается весьма эффективно.
Привычки ометают подавляющее количество случаев. Пикассо и Дали — единицы. Конечно, хочется к ним быть поближе… но неумолимый рынок толкает нас в объятия миллионов посредственностей.
Поэтому насыщение схемы/расписания проезда реальными данными вроде бы как должно существенно снизить необходимость массивных универсальных абстрактно-математических вычислений.zzeng
27.04.2017 09:00Ок, для столицы нашей необъятной Родины десятки, пусть N.
Через Казань M, Ё-бург — K,…
В результате надо поддерживать как минимум (N+M+K)**2 вариантов матриц расстояний как результат разных стыковок.ACPrikh
27.04.2017 09:35Опять Вы с матрицами. А куда иерархический подход делся?
Ну хорошо, скажу по-другому. Матрицы будут сильно-сильно разреженными. В основном нули будете хранить. Что не гуд совсем. Нужен упакованный специализированный граф.
apro
17.04.2017 14:12скорость работы A* примерно одинакова, для указанного пути это 4.5 сек (рядовой десктоп) с чтением и
распаковкой данных, 0.5 сек — только проход волны на разогретом кэше;А название статьи "… на смартфоне", было бы интересно узнать сколько считается на смартфоне.
zzeng
17.04.2017 14:16Примерно в 5 раз медленнее чем на десктопе.
3-4 сек на разогретом кэше и 20-25 с холодного старта.
Из Италии в Тунис.
natexriver
17.04.2017 15:13Привет, отличная статья! Можно задать вопрос немного из другой области? Я занимаюсь разработкой игр, и поиск кратчайшего пути — весьма распространенная задача, которую приходится решать с учетом множества других факторов. Зачастую в играх бывают очень большие графы, и я готов пожертвовать качеством маршрута в угоду производительности. Какие способы нахождения «приблизительного» (т.е. не самого короткого) пути могут оказаться самыми эффективными? Конечно, в общем случае, без учета специфики графа.
zzeng
18.04.2017 06:49С эвристикой надо играться, стимулировать «правильные» пути и наказывать остальные.
Правильные с точки зрения стратегии игры.
54300
17.04.2017 23:26Когда же алгоритмы начнут учитывать что дороги это не рандомная сетка, что ими пытались соединить чтото. Например из западной Польши в Испанию есть всего 2 маршрута, а в италию 1.
dmitry_ch
18.04.2017 09:46+1Ну, вообще, они графы и строят, чтобы проехать можно было. Учитывая качество дороги и даже «ездабельную» скорость по каждому отрезку.
Беда только, что в той же Польше можно найти хайвей и рядом идущую поселкового значения дорогу, которые обе имеют асфальтовое покрытие, и по рейтингу скорости и качеству покрытия отличющиеся в БД карты не сильно. Но это в теории, а на практике на поселковой дороге будет куча бампов и странных знаков, так что по ней не разгонишься и быстро не сгоняешь, куда надо.
А что за проблемы про «2 маршрута»? Если есть два, так карта только их и учтет же?54300
18.04.2017 13:01+1Италию от Европы отделяют горы Альпы, выехать в сторону Польши можно только через перевал Бренер А22. Между Исп. и Фр. горы Пиренеи есть только 2 варианта А63 или А9. Если ехать из Итали на Словению там тоже не так много вариантов для транзита как нарисовано(всег один если учитывать дорожные указатели). Ваш алгоритм нашел националку через Альпы на высоте пару км над уровнем моря вроде бы не существенная проблема. А тапер представте себя в этот момент ночью в кабине с дальнобойщиком 40т общий вес длина состава 16м.
dmitry_ch
18.04.2017 13:18+1Вы ошиблись, я не топикстартер. А вы точно по 2gis по Европе колесите?
Вообще, обычно навигаторы дают возможность выбора параметров маршрута (тупо хотя бы «короче путь / меньше время в пути», и, если не ошибаюсь, есть специальные версии навигаторов на большегрузов. Который и массу транспорта учитывают, и что-то еще. Не очень моя предметная область, но Гугл говорит, что есть такие:
напр., GO Truck Navigationzzeng
18.04.2017 13:33+1У 2ГИС на данный момент нет междугородного навигатора,
то, что описано, всего-лишь прототип, способ обозначить проблемы.
Спасибо за мнение, попробуем учесть.
ACPrikh
18.04.2017 11:11-1Именно. Например, на дорогах есть указатели. Сеть становится векторной. Люди ездят не вообще из точки А в точку Б, а потоки генерализуются в определенных каналах и из определенных точек. А мы наблюдаем попытки построения универсального и оторванного от данных подхода.
Дата ориентированное программирование — вот чем надо заниматься. Надо понимать предмет программирования. У нас программисты на Си, Ява и т.п А не программисты дорожники, энергетики, текстильщики. В результате, с одной стороны, генерируются кони в вакууме, а с другой производятся любительские, но привязанные к жизни поделки энтузиастов.
KingOfNothing
18.04.2017 12:06Спасибо за интересную статью! Подскажите, пожалуйста, где можно почитать о методах хранения таких большых графов в памяти, или как загружать его по частям с диска.
zzeng
18.04.2017 12:39Вряд ли это где-то подробно описано.
Каждый делает кто во что горазд.
Вот так, например.KingOfNothing
18.04.2017 12:51Спасибо! Как вы думаете, возможно ли использовать mmap для чтения графа с диска?
zzeng
18.04.2017 13:27Можно, но тогда данные сжимать невозможно или придется разжимать на лету, не исключено, что много раз одно и то же.
Iqorek
18.04.2017 23:51+1В далеком 2002, для дипломного проекта, в интернете было еще не так много информации, а в офлайне спросить было не у кого, придумал такую оптимизацию для поиска кратчайшего пути:
Все очень просто, в первую очередь нужно идти в сторону конечной точки. В каждой вершине находятся все ребра и сортируются по углу от вектора текущей вершины к конечной. Тот у кого угол меньше, проверяется первый. На первом этапе я находил первый кратчайший путь, он не был самым оптимальным, поэтому на втором этапе я перебирал оставшиеся варианты, до тех пор пока они были короче найденного и не помечены как уже пройденные.
Чудом сохранившийся бекап https://github.com/ilio/RoadMap/blob/master/src/roadmapproject/RoadTracer.javazzeng
19.04.2017 14:20Это довольно популярная методика, многие её изобретают.
Спасибо за ссылку, может кому пригодится.
HKA
25.04.2017 12:03+2Растеризация/дискретизация по квадратным градусам напомнила волновой метод трассировки.
dmitry_ch
Пользуясь случаем, попрошу: было бы хорошо что-то поделать с поиском в 2Гис. Проблема такая: если искать не точное название компании, магазина, торгового центра, а, скажем, само понятие или тип товара («масло» или «компьютеры»), то в поиске обязательно выдаются точки выдачи заказов интернет-магазинов (того же Озон-а). Подозреваю, проблема в том, что такие магазины заявляют в списке товаров «все, и еще чуть-чуть», т.е. (почти) любой товар отлично поиском находится. Все бы хорошо, но в центре выдачи заказа, разумеется, нет ни одного из этих товаров — они там только на заказ. В результате, когда выбрался в город, и хочешь найти, скажем, «масло для двигателя», и пользуешься 2ГИС (пытаясь найти магазин, куда можно зайти и купить товар), выдача поиска приносит множество центров выдачи товаров, которые в наличии ничего не имеют — поиск и визуально карту такие точки засоряют неимоверно.
Было бы очень удобно либо как-то помечать (или хотя бы по дефолту фильтровать, с возможностью включить вывод по желанию) таких «точек выдачи». Иначе при определенном масштабе просмотра (больше одной-двух улиц) среди многих «центров выдачи» найти, скажем, 2-3 настоящих, содержащих продаваемые товары, магазина «Масло и смазки» становится проблематичным.
P.S. По поводу темы статьи: есть у 2ГИС такая тенденция — при прокладке пути в городе срезать дорогу по узким улочкам или по дублерам, если по основной магистрали имеются задержки на светофорах. Нельзя ли сделать эту фичу отключаемой, иначе вместо проезда «только прямо» по проспекту длиной 5 км получаем 10 маневров «на дублера — прямо — на проспект — перекресток — опять на дублера — »… Неудобно иногда!
zzeng
Что касается поиска, переслал поближе к теме.
Про дублёры, мы пытаемся нащупать середину между теми, кому это полезно и недовольными.
Вносить в интерфейс пока видится негуманным.
dmitry_ch
Да, спасибо, и спасибо за вашу работу вообще! Я знаю, что вы ищете, и вижу, как продукт меняется постоянно, и обычно в лучшую сторону.
С дублерами вопрос обычно выливается вот во что: если заезжаешь в незнакомый город, то, спроси дорогу у местных, человек скажет — езжай по этому проспекту 10 кварталов, потом налево. При этом я могу ехать по проспекту, могу пользоваться дублерами, но в голове будет четкое понимания, что проехать до указанного (характерного, так сказать, в контексте маршрута) поворота надо еще, скажем, 5 перекрестков. Навигатор же будет детализировать дорогу, и, при выводе дороги по дублерам, вывалит столько маневров, что за этими «деревьями леса не увидеть».
Баланс тут трудно найти, понимаю. Я бы рад, наверное, был бы видеть все время только маршрут по главной широкой дороге (проспекту), и менее ярко варианты объезда, но чтобы инфа до ключевых поворотов выводилась именно про проспект. Хотя, это то, как мне кажется понятнее.
Ну и конечно, ситуации разные бывают. Для меня очень характерным был пример одной дороги, в которой примерно километров 100, и на которой много поворотов и маленьких поселков, но которая по всем картам проходит как единая дорога (а не как сумма отрезков от поселка до поселка). Поэтому в начале пути навигатор говорит «едем прямо 100 км» и молчит всю дорогу. Была бы кнопка «выводить длину и информацию только о большом пути / выводить подробности о каждом отрезке», может, было бы и проще.
AllexIn
«Кратчайший маршрут/оптимальный». Вроде самое рапространенное и весьма популярное решение.
zzeng
У нас это есть, но конкретно здесь не сработает.