Comments 48
Пользуясь случаем, попрошу: было бы хорошо что-то поделать с поиском в 2Гис. Проблема такая: если искать не точное название компании, магазина, торгового центра, а, скажем, само понятие или тип товара («масло» или «компьютеры»), то в поиске обязательно выдаются точки выдачи заказов интернет-магазинов (того же Озон-а). Подозреваю, проблема в том, что такие магазины заявляют в списке товаров «все, и еще чуть-чуть», т.е. (почти) любой товар отлично поиском находится. Все бы хорошо, но в центре выдачи заказа, разумеется, нет ни одного из этих товаров — они там только на заказ. В результате, когда выбрался в город, и хочешь найти, скажем, «масло для двигателя», и пользуешься 2ГИС (пытаясь найти магазин, куда можно зайти и купить товар), выдача поиска приносит множество центров выдачи товаров, которые в наличии ничего не имеют — поиск и визуально карту такие точки засоряют неимоверно.
Было бы очень удобно либо как-то помечать (или хотя бы по дефолту фильтровать, с возможностью включить вывод по желанию) таких «точек выдачи». Иначе при определенном масштабе просмотра (больше одной-двух улиц) среди многих «центров выдачи» найти, скажем, 2-3 настоящих, содержащих продаваемые товары, магазина «Масло и смазки» становится проблематичным.
P.S. По поводу темы статьи: есть у 2ГИС такая тенденция — при прокладке пути в городе срезать дорогу по узким улочкам или по дублерам, если по основной магистрали имеются задержки на светофорах. Нельзя ли сделать эту фичу отключаемой, иначе вместо проезда «только прямо» по проспекту длиной 5 км получаем 10 маневров «на дублера — прямо — на проспект — перекресток — опять на дублера — »… Неудобно иногда!
Было бы очень удобно либо как-то помечать (или хотя бы по дефолту фильтровать, с возможностью включить вывод по желанию) таких «точек выдачи». Иначе при определенном масштабе просмотра (больше одной-двух улиц) среди многих «центров выдачи» найти, скажем, 2-3 настоящих, содержащих продаваемые товары, магазина «Масло и смазки» становится проблематичным.
P.S. По поводу темы статьи: есть у 2ГИС такая тенденция — при прокладке пути в городе срезать дорогу по узким улочкам или по дублерам, если по основной магистрали имеются задержки на светофорах. Нельзя ли сделать эту фичу отключаемой, иначе вместо проезда «только прямо» по проспекту длиной 5 км получаем 10 маневров «на дублера — прямо — на проспект — перекресток — опять на дублера — »… Неудобно иногда!
Что касается поиска, переслал поближе к теме.
Про дублёры, мы пытаемся нащупать середину между теми, кому это полезно и недовольными.
Вносить в интерфейс пока видится негуманным.
Про дублёры, мы пытаемся нащупать середину между теми, кому это полезно и недовольными.
Вносить в интерфейс пока видится негуманным.
Да, спасибо, и спасибо за вашу работу вообще! Я знаю, что вы ищете, и вижу, как продукт меняется постоянно, и обычно в лучшую сторону.
С дублерами вопрос обычно выливается вот во что: если заезжаешь в незнакомый город, то, спроси дорогу у местных, человек скажет — езжай по этому проспекту 10 кварталов, потом налево. При этом я могу ехать по проспекту, могу пользоваться дублерами, но в голове будет четкое понимания, что проехать до указанного (характерного, так сказать, в контексте маршрута) поворота надо еще, скажем, 5 перекрестков. Навигатор же будет детализировать дорогу, и, при выводе дороги по дублерам, вывалит столько маневров, что за этими «деревьями леса не увидеть».
Баланс тут трудно найти, понимаю. Я бы рад, наверное, был бы видеть все время только маршрут по главной широкой дороге (проспекту), и менее ярко варианты объезда, но чтобы инфа до ключевых поворотов выводилась именно про проспект. Хотя, это то, как мне кажется понятнее.
Ну и конечно, ситуации разные бывают. Для меня очень характерным был пример одной дороги, в которой примерно километров 100, и на которой много поворотов и маленьких поселков, но которая по всем картам проходит как единая дорога (а не как сумма отрезков от поселка до поселка). Поэтому в начале пути навигатор говорит «едем прямо 100 км» и молчит всю дорогу. Была бы кнопка «выводить длину и информацию только о большом пути / выводить подробности о каждом отрезке», может, было бы и проще.
С дублерами вопрос обычно выливается вот во что: если заезжаешь в незнакомый город, то, спроси дорогу у местных, человек скажет — езжай по этому проспекту 10 кварталов, потом налево. При этом я могу ехать по проспекту, могу пользоваться дублерами, но в голове будет четкое понимания, что проехать до указанного (характерного, так сказать, в контексте маршрута) поворота надо еще, скажем, 5 перекрестков. Навигатор же будет детализировать дорогу, и, при выводе дороги по дублерам, вывалит столько маневров, что за этими «деревьями леса не увидеть».
Баланс тут трудно найти, понимаю. Я бы рад, наверное, был бы видеть все время только маршрут по главной широкой дороге (проспекту), и менее ярко варианты объезда, но чтобы инфа до ключевых поворотов выводилась именно про проспект. Хотя, это то, как мне кажется понятнее.
Ну и конечно, ситуации разные бывают. Для меня очень характерным был пример одной дороги, в которой примерно километров 100, и на которой много поворотов и маленьких поселков, но которая по всем картам проходит как единая дорога (а не как сумма отрезков от поселка до поселка). Поэтому в начале пути навигатор говорит «едем прямо 100 км» и молчит всю дорогу. Была бы кнопка «выводить длину и информацию только о большом пути / выводить подробности о каждом отрезке», может, было бы и проще.
«Кратчайший маршрут/оптимальный». Вроде самое рапространенное и весьма популярное решение.
Хорошая статья, спасибо ),
У меня такой вопрос. А почему при оценке остатка пути не используются резистивные расстояния? Или потенциалы узлов, которые появляются после выбора начального и конечного? Данный подход я на хабре описывал, как пример использования потенциалов лапласиана. Тут чистая математика без эвристик и костылей.
Просто я в данной области чисто теоретик и от практики далек. Видимо, на практике это не взлетает по каким-то причинам, о которых и спрашиваю. Невозможно посчитать матрицу резистивных расстояний для больших графов? Или еще что-то?
У меня такой вопрос. А почему при оценке остатка пути не используются резистивные расстояния? Или потенциалы узлов, которые появляются после выбора начального и конечного? Данный подход я на хабре описывал, как пример использования потенциалов лапласиана. Тут чистая математика без эвристик и костылей.
Просто я в данной области чисто теоретик и от практики далек. Видимо, на практике это не взлетает по каким-то причинам, о которых и спрашиваю. Невозможно посчитать матрицу резистивных расстояний для больших графов? Или еще что-то?
Упс… не читал эти статьи. Изучу и отпишусь.
Насколько я понял, метод заключается в наложении разности потенциалов на стартовую и финишные точки,
затем с помощью лапласиана находятся потенциалы в узлах и кратчайший путь прокладывается по максимальному потоку.
Боюсь, что для больших графов это будет весьма расточительно,
особенно, учитывая то, что даже когда старт и финиш рядом, считать придётся весь граф или значительную его часть.
затем с помощью лапласиана находятся потенциалы в узлах и кратчайший путь прокладывается по максимальному потоку.
Боюсь, что для больших графов это будет весьма расточительно,
особенно, учитывая то, что даже когда старт и финиш рядом, считать придётся весь граф или значительную его часть.
Спасибо ). Я, конечно, надеялся на что-нибудь более конкретное. Типа, в таком-то году такие-то ребята пробовали данный подход, но столкнулись с такими-то проблемами, которые описали в такой-то статье ).
Фишка в том, что резистивные расстояния (ну или потенциалы 2-го порядка) считаются только один раз (для всего графа), и редко пересматриваются (для пересмотра уже не надо по новой все пересчитывать). А потенциалы узлов строятся «на лету» при заданных начальной и конечной точках j, k по приведенной в статьей формуле (2.5):
dUi = dCjk (Uik + Ujk — Uij)/2
Здесь Uik — заранее посчитанные потенциалы (резистивные расстояния). Величина dCjk — произвольная, можно взять 1.
При этом совсем необязательно считать потенциалы узлов всего графа. Берем за начальный узел исходную точку и считаем потенциалы для всех соседних. Далее выбираем из них (минимальный или максимальный — от знака dCjk) и повторяем процедуру. Пока не придем в заданный. Это быстрый и надежный вариант, но он может оказаться не самым оптимальным, да.
Природа сама использует подобную процедуру, чтобы определить, по каким маршрутам лететь фотонам/электронам из области высокого потенциала к низкому.
Фишка в том, что резистивные расстояния (ну или потенциалы 2-го порядка) считаются только один раз (для всего графа), и редко пересматриваются (для пересмотра уже не надо по новой все пересчитывать). А потенциалы узлов строятся «на лету» при заданных начальной и конечной точках j, k по приведенной в статьей формуле (2.5):
dUi = dCjk (Uik + Ujk — Uij)/2
Здесь Uik — заранее посчитанные потенциалы (резистивные расстояния). Величина dCjk — произвольная, можно взять 1.
При этом совсем необязательно считать потенциалы узлов всего графа. Берем за начальный узел исходную точку и считаем потенциалы для всех соседних. Далее выбираем из них (минимальный или максимальный — от знака dCjk) и повторяем процедуру. Пока не придем в заданный. Это быстрый и надежный вариант, но он может оказаться не самым оптимальным, да.
Природа сама использует подобную процедуру, чтобы определить, по каким маршрутам лететь фотонам/электронам из области высокого потенциала к низкому.
Если честно, меня немного пугает перспектива обращать пусть даже сильно разреженную матрицу размером 300млн Х 300млн, хотя бы и всего один раз :) Она ведь сильно вырожденная, за точностью чуть не уследил и бац!
С Дейкстрой и А* всё проще — простая идея, интуитивно понятное поведение, простая реализация.
С Дейкстрой и А* всё проще — простая идея, интуитивно понятное поведение, простая реализация.
Интересная, имхо, задача — обращение таких матриц. Даже не обращение, а именно вычисление всех резистивных расстояний (потенциалов) для огромных разреженных матриц.
Я не сталкивался, но в алгоритме ранжирования страниц Page Ranking схожая проблема. Правда там рассчитываются потенциалы 1-го порядка, а не 2-го. Но размер матриц вряд ли меньше. Гугл вроде как-то справляется (если еще использует его).
Я не сталкивался, но в алгоритме ранжирования страниц Page Ranking схожая проблема. Правда там рассчитываются потенциалы 1-го порядка, а не 2-го. Но размер матриц вряд ли меньше. Гугл вроде как-то справляется (если еще использует его).
Часто требуется найти окрестность досягаемости, как быть в таком случае?
Наложить только один потенциал и смотреть куда ток утечки идёт?
Наложить только один потенциал и смотреть куда ток утечки идёт?
Что такое «окрестность досягаемости»? Мне надо формулировку, чтобы ответить.
Надо еще подумать над задачей расчета потенциалов между ограниченным множеством узлов заданного графа. На самом деле ведь не нужно считать резистивные расстояния (потенциалы) между всеми узлами. Достаточно только между заданными. Должен быть простой способ сделать это.
Надо еще подумать над задачей расчета потенциалов между ограниченным множеством узлов заданного графа. На самом деле ведь не нужно считать резистивные расстояния (потенциалы) между всеми узлами. Достаточно только между заданными. Должен быть простой способ сделать это.
Если «условия ограниченных ресурсов[памяти — времени работы процессора] и/или неограниченных данных», то напрашивается использование предварительных вычислений. Таблица предварительно вычисленных и хранимых расстояний между узлами высокой, средней (средних) и мелкой иерархии.
Таблицы Атлас мира — европы — Италии — Тосканы с Лацио.
Таблицы Атлас мира — европы — Италии — Тосканы с Лацио.
Это и есть иерархический подход.
В данном случае иерархический. Только акцент делаю не на иерархии, а в предварительных вычислениях. Задачу можно решать за счет адресного пространства данных, а можно за счёт мощности процессора.
У предварительных вычислений беда с ребрами где динамически меняются стоимости.
Здесь надо (пардон, имею в виду по смыслу надо) оценить насколько велик вес динамических данных и насколько он «расползается» по сети. Например, ремонт дороги, как правило, приведет к локальному объезду. А шторм на морской переправе может кардинально сменить дальний маршрут. Но в таком случае, переходим к предварительно просчитанному варианту «Б».
Ещё говорил о Дата-ориентированном программировании. Может слишком абстрактно получилось и поэтому непонятно. Тогда так. Автомобилист, при поиске пути проезда не чертит колесами такие маршруты, как в алгоритме. А почему? Он использует указатели — «предварительно просчитанные» маршруты. Разумеется, в идеальном случае расставленных обильно на перекрестках.
К тому же используются туннелирование — наиболее часто используемые маршруты чисто статистически. То есть люди не едут из произвольных точек, а из таких-то чаще туда-то. Причем летом — одни маршруты, зимой — другие и.т.п. То есть решение как бы хочет привязаться к конкретной сети и обстановке. Вот эту конкретику я и обозвал «дата-ориентированный подход».
Ещё говорил о Дата-ориентированном программировании. Может слишком абстрактно получилось и поэтому непонятно. Тогда так. Автомобилист, при поиске пути проезда не чертит колесами такие маршруты, как в алгоритме. А почему? Он использует указатели — «предварительно просчитанные» маршруты. Разумеется, в идеальном случае расставленных обильно на перекрестках.
К тому же используются туннелирование — наиболее часто используемые маршруты чисто статистически. То есть люди не едут из произвольных точек, а из таких-то чаще туда-то. Причем летом — одни маршруты, зимой — другие и.т.п. То есть решение как бы хочет привязаться к конкретной сети и обстановке. Вот эту конкретику я и обозвал «дата-ориентированный подход».
Ну почему шторм, например паром по расписанию или разводные мосты.
На большой площади предрасчет будет будет зависеть от того, с какого направления куда мы едем.
Это уже накладно. Планом Б не отделаешься.
Ориентироваться на пользовательские привычки тоже опасно. Зимой одни привычки, летом другие. А в межсезонье? В одном городе выпал снег, а в другом нет, на какую модель ориентироваться?
На большой площади предрасчет будет будет зависеть от того, с какого направления куда мы едем.
Это уже накладно. Планом Б не отделаешься.
Ориентироваться на пользовательские привычки тоже опасно. Зимой одни привычки, летом другие. А в межсезонье? В одном городе выпал снег, а в другом нет, на какую модель ориентироваться?
Шторм, ремонт, аварии (последнее чаще) — как нерегулярное явление. Все расписания и периодические явления предрасчитываются на доп шкале времени. То есть не только схема проезда, но и расписание проезда.
Направлений мало до безобразия. Если из Москвы их десятки, то для Пензы пяток, а для Гадюкино вообще одно. Фазовое пространство реальности вырождается весьма эффективно.
Привычки ометают подавляющее количество случаев. Пикассо и Дали — единицы. Конечно, хочется к ним быть поближе… но неумолимый рынок толкает нас в объятия миллионов посредственностей.
Поэтому насыщение схемы/расписания проезда реальными данными вроде бы как должно существенно снизить необходимость массивных универсальных абстрактно-математических вычислений.
Направлений мало до безобразия. Если из Москвы их десятки, то для Пензы пяток, а для Гадюкино вообще одно. Фазовое пространство реальности вырождается весьма эффективно.
Привычки ометают подавляющее количество случаев. Пикассо и Дали — единицы. Конечно, хочется к ним быть поближе… но неумолимый рынок толкает нас в объятия миллионов посредственностей.
Поэтому насыщение схемы/расписания проезда реальными данными вроде бы как должно существенно снизить необходимость массивных универсальных абстрактно-математических вычислений.
Ок, для столицы нашей необъятной Родины десятки, пусть N.
Через Казань M, Ё-бург — K,…
В результате надо поддерживать как минимум (N+M+K)**2 вариантов матриц расстояний как результат разных стыковок.
Через Казань M, Ё-бург — K,…
В результате надо поддерживать как минимум (N+M+K)**2 вариантов матриц расстояний как результат разных стыковок.
скорость работы A* примерно одинакова, для указанного пути это 4.5 сек (рядовой десктоп) с чтением и
распаковкой данных, 0.5 сек — только проход волны на разогретом кэше;
А название статьи "… на смартфоне", было бы интересно узнать сколько считается на смартфоне.
Привет, отличная статья! Можно задать вопрос немного из другой области? Я занимаюсь разработкой игр, и поиск кратчайшего пути — весьма распространенная задача, которую приходится решать с учетом множества других факторов. Зачастую в играх бывают очень большие графы, и я готов пожертвовать качеством маршрута в угоду производительности. Какие способы нахождения «приблизительного» (т.е. не самого короткого) пути могут оказаться самыми эффективными? Конечно, в общем случае, без учета специфики графа.
Когда же алгоритмы начнут учитывать что дороги это не рандомная сетка, что ими пытались соединить чтото. Например из западной Польши в Испанию есть всего 2 маршрута, а в италию 1.
Ну, вообще, они графы и строят, чтобы проехать можно было. Учитывая качество дороги и даже «ездабельную» скорость по каждому отрезку.
Беда только, что в той же Польше можно найти хайвей и рядом идущую поселкового значения дорогу, которые обе имеют асфальтовое покрытие, и по рейтингу скорости и качеству покрытия отличющиеся в БД карты не сильно. Но это в теории, а на практике на поселковой дороге будет куча бампов и странных знаков, так что по ней не разгонишься и быстро не сгоняешь, куда надо.
А что за проблемы про «2 маршрута»? Если есть два, так карта только их и учтет же?
Беда только, что в той же Польше можно найти хайвей и рядом идущую поселкового значения дорогу, которые обе имеют асфальтовое покрытие, и по рейтингу скорости и качеству покрытия отличющиеся в БД карты не сильно. Но это в теории, а на практике на поселковой дороге будет куча бампов и странных знаков, так что по ней не разгонишься и быстро не сгоняешь, куда надо.
А что за проблемы про «2 маршрута»? Если есть два, так карта только их и учтет же?
Италию от Европы отделяют горы Альпы, выехать в сторону Польши можно только через перевал Бренер А22. Между Исп. и Фр. горы Пиренеи есть только 2 варианта А63 или А9. Если ехать из Итали на Словению там тоже не так много вариантов для транзита как нарисовано(всег один если учитывать дорожные указатели). Ваш алгоритм нашел националку через Альпы на высоте пару км над уровнем моря вроде бы не существенная проблема. А тапер представте себя в этот момент ночью в кабине с дальнобойщиком 40т общий вес длина состава 16м.
Вы ошиблись, я не топикстартер. А вы точно по 2gis по Европе колесите?
Вообще, обычно навигаторы дают возможность выбора параметров маршрута (тупо хотя бы «короче путь / меньше время в пути», и, если не ошибаюсь, есть специальные версии навигаторов на большегрузов. Который и массу транспорта учитывают, и что-то еще. Не очень моя предметная область, но Гугл говорит, что есть такие:
В конце концов, ведя трак, купить специализированную программу, которая отобьется за 10 минут, буквально даже на цене нервов, если не сэкономленного топлива, вроде как логично?
Вообще, обычно навигаторы дают возможность выбора параметров маршрута (тупо хотя бы «короче путь / меньше время в пути», и, если не ошибаюсь, есть специальные версии навигаторов на большегрузов. Который и массу транспорта учитывают, и что-то еще. Не очень моя предметная область, но Гугл говорит, что есть такие:
напр., GO Truck Navigation
В конце концов, ведя трак, купить специализированную программу, которая отобьется за 10 минут, буквально даже на цене нервов, если не сэкономленного топлива, вроде как логично?
У 2ГИС на данный момент нет междугородного навигатора,
то, что описано, всего-лишь прототип, способ обозначить проблемы.
Спасибо за мнение, попробуем учесть.
то, что описано, всего-лишь прототип, способ обозначить проблемы.
Спасибо за мнение, попробуем учесть.
Именно. Например, на дорогах есть указатели. Сеть становится векторной. Люди ездят не вообще из точки А в точку Б, а потоки генерализуются в определенных каналах и из определенных точек. А мы наблюдаем попытки построения универсального и оторванного от данных подхода.
Дата ориентированное программирование — вот чем надо заниматься. Надо понимать предмет программирования. У нас программисты на Си, Ява и т.п А не программисты дорожники, энергетики, текстильщики. В результате, с одной стороны, генерируются кони в вакууме, а с другой производятся любительские, но привязанные к жизни поделки энтузиастов.
Дата ориентированное программирование — вот чем надо заниматься. Надо понимать предмет программирования. У нас программисты на Си, Ява и т.п А не программисты дорожники, энергетики, текстильщики. В результате, с одной стороны, генерируются кони в вакууме, а с другой производятся любительские, но привязанные к жизни поделки энтузиастов.
Спасибо за интересную статью! Подскажите, пожалуйста, где можно почитать о методах хранения таких большых графов в памяти, или как загружать его по частям с диска.
В далеком 2002, для дипломного проекта, в интернете было еще не так много информации, а в офлайне спросить было не у кого, придумал такую оптимизацию для поиска кратчайшего пути:
Все очень просто, в первую очередь нужно идти в сторону конечной точки. В каждой вершине находятся все ребра и сортируются по углу от вектора текущей вершины к конечной. Тот у кого угол меньше, проверяется первый. На первом этапе я находил первый кратчайший путь, он не был самым оптимальным, поэтому на втором этапе я перебирал оставшиеся варианты, до тех пор пока они были короче найденного и не помечены как уже пройденные.
Чудом сохранившийся бекап https://github.com/ilio/RoadMap/blob/master/src/roadmapproject/RoadTracer.java
Все очень просто, в первую очередь нужно идти в сторону конечной точки. В каждой вершине находятся все ребра и сортируются по углу от вектора текущей вершины к конечной. Тот у кого угол меньше, проверяется первый. На первом этапе я находил первый кратчайший путь, он не был самым оптимальным, поэтому на втором этапе я перебирал оставшиеся варианты, до тех пор пока они были короче найденного и не помечены как уже пройденные.
Чудом сохранившийся бекап https://github.com/ilio/RoadMap/blob/master/src/roadmapproject/RoadTracer.java
Растеризация/дискретизация по квадратным градусам напомнила волновой метод трассировки.
Доклад «Знакомьтесь, М*» Муратшин Борис, 2ГИС на DUMP 2017, если кто-то будет искать
Sign up to leave a comment.
M* — алгоритм поиска кратчайшего пути, через весь мир, на смартфоне