Oleg P, маршрут рассчитывается на сервере, ведь для учёта пробок нужно иметь доступ ко всему графу скоростей, который постоянно обновляется. Поэтому маршрут рассчитывается на сервере, и на телефон передаётся уже только оптимальный маршрут.
Почему бы не использовать алгоритм А* или какую-нибудь еще эвристику типа Reach или ALT? И кстати,прокомментируйте плиз момент в финальной части видео,а то я недопонял - вы используете для поиска решения уже просчитанные ранее участки пути,считавшиеся когда-то для похожих задач,верно? Вы считаете их по усредненной дорожной ситуации с пробками,так? Как часто вы пересчитываете участки типа "въезд/выезд из города" при условии меняющейся дорожной обстановки? * я сейчас говорю не про ДТП,а про дорожные работы,например. *
Хорошо. С маршрутом без пробок все в принципе понятно и просто. Но вот как оптимизировать построение маршрута в городе с учетом пробок? (как было показано на первом примере)
Пример, строится маршрут, на пути есть светофор, а я знаю, что есть объезд светофора и приеду я быстрее чем буду стоять на светофоре. Чтобы учитывались такие моменты, что сделать? Или например, левые повороты, выезды на главную, где я по долгу могу стоять и уступать?
Если использовать время с учётом пробок, т.е. по сути полученное от предыдущих автомобилистов, которые здесь проезжали, то все эти факторы автоматически войдут в среднюю скорость (если, каждый второй стоит на светофоре, а каждый второй проезжает свободно, то будет посчитано какое-то среднее время). Таким образом, если маршрут через светофор в среднем быстрее - будет предложен он, если в среднем быстрее объезд - поведёт в объезд. Другой вопрос, что в среднем - не гарантирует, что для данного конкретного водителя вариант будет более удачный. Что здесь можно сделать? Например, можно участкам, где высокая вероятность простоять существенно больше среднего добавлять какое-то штрафное время. Тогда маршрутизатор будет стремиться избегать участков, где время проезда нестабильно.
Вариант запоминания маршрутов очень интересен. Но где гарантия, что не изменится ситуация с пробками? Или при таком методе прокладки пробки не учитываются?
При помощи алгоритма Дейкстры можно строить маршруты и без учёта пробок, и с их учётом, но считая картину пробок фиксированной во времени. Однако, можно модифицировать алгоритм, если у нас есть прогноз пробок. Достаточно на каждом следующем шаге использовать граф времён проезда, который соответствует прогнозным пробкам на тот момент, когда мы подъехали к ребру.
То есть если маршрут "запоминается", получается, что для каждой конкретной ситуации в городе, в зависимости от пробок на этот маршрут могут накладываться штрафы и тогда алгоритм ДОЛЖЕН выбрать другой маршрут. Выбирает ли он его? Если да, тогда при постоянной изменчивости ситуации на дорогах приходится запоминать множество альтернативных маршрутов, либо перебирать заново все. Как вы решили вопрос оптимизации в этом варианте?
Вы правы, такую схему оптимизации затруднительно применять при изменяющихся данных. Как оптимизировать производительность в этом случае - выходит за рамки рассказа.
Очень странно что яндекс навигатор не учитывает при построении маршрута что к тому времени как я доберусь до определенной точки маршрута, там точно будет пробка. Если выезжать из помосковья в москву часов в 7 утра, то с вероятностью более 90% во время пути, прогноз по времени увеличится довольно значительно. Неужели сложно прогнозировать появление пробок, там где они появляются каждый день в одно и то же время? И еще. Иногда маршрут строится в виде лесенки, но в этом варианте добавляется не только время прохождения поворота, но и время на торможение перед поворотом, и время разгона после поворота. То есть в данном случае лучше брать средние скорости не между двух точек, а между трех точек, тогда не нужно будет добавлять непонятные штрафы, и автоматически просчитается что например перед поворотом придется еще постоять в поворотном ряду. Можно еще добавить функцию, проезд через перекресток в зависимости от того горит сейчас стрелка или зеленый. Иногда в определенный конкретный момент можно проехать быстрее опираясь на сигнал светофора. Яндекс не дает альтернативных вариантов в таких местах, и никак о них не подсказывает.
Алгоритм перебирает все возможные варианты. В базовой версии ему всё равно какие повороты, он считает лишь затраты времени на проезд по дорогам, но не на поворот. Однако можно добавить в каждой вершине либо полный запрет на какой-либо поворот (если он запрещён правилами), либо некое штрафное время за манёвр, если мы хотим, чтобы при небольшом проигрыше во времени выбирался маршрут с меньшим числом манёвров.
Один из предлагаемых маршрутов - самый быстрый с учётом пробок, другой маршрут - самый быстрый без учёта пробок, обычно он является более простым. Таким образом водителям предлагается либо самый быстрый или простой маршрут. Если и с учётом пробок и без их учёта оптимальным оказывается один и тот же маршрут, то показывается он один без альтернативы.
Вы офисный планктон не понимаете, что компьютер рассчитывает цифры. И если он направляет половину потока машин в объезд пробки по узкой улочке, то за 10 минут там создаётся коллапс.
Как то все не вяжется. Исходя из вашего доклада вы один раз проложили маршрут по городу от въезда до выезда, запомнили его и на пробки вам получается наплевать. А между городами где зачастую одна дорога вы постоянно пересчитываете маршрут. Теперь я понял почему Яндекс навигатор так неадекватно прокладывает маршруты!
Что касается оптимизации производительности, то пример был для маршрутизации без учёта пробок. Что делать в случае меняющихся пробок - это отдельная тема, которая выходит за рамки рассказа.
Яндекс маршрут подвел меня под "кирпич". Еду, еду себе, по навигатору, смотрю, кто то мне дорогу перекрывает автомобилем, вижу гаишник уже выходит, говорит: "Ты кирпич проехал!". Лишение прав от 4-х до 6 мес. Хрен знает, может он и омбанул меня, но спорить я с ним не стал, на тот момент, я как то был слегка шокирован, что ЗЕЛЕНЫЙ маршрут проходит прямо по одностороннему движению, в противоположную сторону. Я заподозрил не ладное метров через 10-20) Но было уже поздно, он (Гаишник) уже там ждал.. Он мгновенно подрулил ко мне, и говорит: "Лишение прав от 4- до 6 мес". Я много раз просматривал, этот проклятый перекресток с разных устройств - НЕТ ТАМ ОДНОСТОРОННЕГО ДВИЖЕНИЯ! А знаки видно новенькие, и да их отлично видно, на перекрестке, висит очень высоко, да и навигатор говорит "Прямо один километр.." Случайность?? Не думаю..
Медников очень хороший докладчик, приятно слушать.
Oleg P, маршрут рассчитывается на сервере, ведь для учёта пробок нужно иметь доступ ко всему графу скоростей, который постоянно обновляется. Поэтому маршрут рассчитывается на сервере, и на телефон передаётся уже только оптимальный маршрут.
Если заранее расчитать все возможные графы внутри Ярославля для пар въезд-выезд, то как в этом случае быть с пробками? Их заранее не просчитать же.
Чёрт возьми мне нравиться как этот парень объясняет и говорит. Показывайте нам его чаще, пожалуйста.
P.S: Чуть меньше "э" и будет супер.
"Э" -это последствия знания английского языка .Все этим грешат.
вспомнил 2007 и его навигаторы на непонятной ОС до Андроида, которые рисовали маршруты по полям между городами😂😂 а Яндекс это был только поисковик.
Какой же Яндекс был крутым раньше
Почему бы не использовать алгоритм А* или какую-нибудь еще эвристику типа Reach или ALT? И кстати,прокомментируйте плиз момент в финальной части видео,а то я недопонял - вы используете для поиска решения уже просчитанные ранее участки пути,считавшиеся когда-то для похожих задач,верно? Вы считаете их по усредненной дорожной ситуации с пробками,так? Как часто вы пересчитываете участки типа "въезд/выезд из города" при условии меняющейся дорожной обстановки? * я сейчас говорю не про ДТП,а про дорожные работы,например. *
Не хватает исходного графа дорог и упрощенного «запомненного» для городов/районов, было бы наглядно и сильно проще для понимания. ;-)
Спасибо, КЭП!
Хорошо. С маршрутом без пробок все в принципе понятно и просто. Но вот как оптимизировать построение маршрута в городе с учетом пробок? (как было показано на первом примере)
Пример, строится маршрут, на пути есть светофор, а я знаю, что есть объезд светофора и приеду я быстрее чем буду стоять на светофоре. Чтобы учитывались такие моменты, что сделать? Или например, левые повороты, выезды на главную, где я по долгу могу стоять и уступать?
Если использовать время с учётом пробок, т.е. по сути полученное от предыдущих автомобилистов, которые здесь проезжали, то все эти факторы автоматически войдут в среднюю скорость (если, каждый второй стоит на светофоре, а каждый второй проезжает свободно, то будет посчитано какое-то среднее время). Таким образом, если маршрут через светофор в среднем быстрее - будет предложен он, если в среднем быстрее объезд - поведёт в объезд. Другой вопрос, что в среднем - не гарантирует, что для данного конкретного водителя вариант будет более удачный. Что здесь можно сделать? Например, можно участкам, где высокая вероятность простоять существенно больше среднего добавлять какое-то штрафное время. Тогда маршрутизатор будет стремиться избегать участков, где время проезда нестабильно.
До 8:50 алгоритм Дейкстры
Подскажите для игры пакман когда с другим соревнуешься, то что использовать?
Вариант запоминания маршрутов очень интересен. Но где гарантия, что не изменится ситуация с пробками? Или при таком методе прокладки пробки не учитываются?
При помощи алгоритма Дейкстры можно строить маршруты и без учёта пробок, и с их учётом, но считая картину пробок фиксированной во времени. Однако, можно модифицировать алгоритм, если у нас есть прогноз пробок. Достаточно на каждом следующем шаге использовать граф времён проезда, который соответствует прогнозным пробкам на тот момент, когда мы подъехали к ребру.
Академия Яндекса Давно волнует вопрос. Учитывает ли текущий алгоритм яндекс.пробок прогноз пробок при построении маршрутов?
То есть если маршрут "запоминается", получается, что для каждой конкретной ситуации в городе, в зависимости от пробок на этот маршрут могут накладываться штрафы и тогда алгоритм ДОЛЖЕН выбрать другой маршрут. Выбирает ли он его? Если да, тогда при постоянной изменчивости ситуации на дорогах приходится запоминать множество альтернативных маршрутов, либо перебирать заново все. Как вы решили вопрос оптимизации в этом варианте?
Вы правы, такую схему оптимизации затруднительно применять при изменяющихся данных. Как оптимизировать производительность в этом случае - выходит за рамки рассказа.
Очень странно что яндекс навигатор не учитывает при построении маршрута что к тому времени как я доберусь до определенной точки маршрута, там точно будет пробка. Если выезжать из помосковья в москву часов в 7 утра, то с вероятностью более 90% во время пути, прогноз по времени увеличится довольно значительно. Неужели сложно прогнозировать появление пробок, там где они появляются каждый день в одно и то же время? И еще. Иногда маршрут строится в виде лесенки, но в этом варианте добавляется не только время прохождения поворота, но и время на торможение перед поворотом, и время разгона после поворота. То есть в данном случае лучше брать средние скорости не между двух точек, а между трех точек, тогда не нужно будет добавлять непонятные штрафы, и автоматически просчитается что например перед поворотом придется еще постоять в поворотном ряду. Можно еще добавить функцию, проезд через перекресток в зависимости от того горит сейчас стрелка или зеленый. Иногда в определенный конкретный момент можно проехать быстрее опираясь на сигнал светофора. Яндекс не дает альтернативных вариантов в таких местах, и никак о них не подсказывает.
При построении маршрута значения рёбер графа нельзя складывать, т.к. это неаддитивные величины.
когда заезжаешь во дворы "я.н" не учитывает шлагбаумы дворовые и предлагает проехать сквозь них
Скажите, плиз, рассчитывается ли по этому алгоритму отрезки пути с левыми поворотами? Или за поворот просто добавляется штрафное время?
Алгоритм перебирает все возможные варианты. В базовой версии ему всё равно какие повороты, он считает лишь затраты времени на проезд по дорогам, но не на поворот. Однако можно добавить в каждой вершине либо полный запрет на какой-либо поворот (если он запрещён правилами), либо некое штрафное время за манёвр, если мы хотим, чтобы при небольшом проигрыше во времени выбирался маршрут с меньшим числом манёвров.
Каким образом выбирается альтернативный маршрут и почему он только один?
Один из предлагаемых маршрутов - самый быстрый с учётом пробок, другой маршрут - самый быстрый без учёта пробок, обычно он является более простым. Таким образом водителям предлагается либо самый быстрый или простой маршрут. Если и с учётом пробок и без их учёта оптимальным оказывается один и тот же маршрут, то показывается он один без альтернативы.
Где рассчитывается маршрут - в телефоне или на сервере?
Только на сервере, телефон с таким не справится однозначно)
купил телефон, на телефоне предустановлен только яндекс сторе, как установить гугл плей? или надо телефон менять?
купи слона ;-)
Используй алгоритм Дейкстры, чтобы найти путь к ближайшей точке продаж. Гениальное место для данной темы ты выбрал!
Меняй телефон и переезжай в другой город на новом автомобиле.
На каком языке написан алгоритм?
Строит этот навигатор где нет дорог или грунтовые с огромными ямоми где сам черт не проедет или ведёт где придется нарушать пдд.
Графы
Вы офисный планктон не понимаете, что компьютер рассчитывает цифры. И если он направляет половину потока машин в объезд пробки по узкой улочке, то за 10 минут там создаётся коллапс.
Как то все не вяжется. Исходя из вашего доклада вы один раз проложили маршрут по городу от въезда до выезда, запомнили его и на пробки вам получается наплевать. А между городами где зачастую одна дорога вы постоянно пересчитываете маршрут. Теперь я понял почему Яндекс навигатор так неадекватно прокладывает маршруты!
Что касается оптимизации производительности, то пример был для маршрутизации без учёта пробок. Что делать в случае меняющихся пробок - это отдельная тема, которая выходит за рамки рассказа.
Вы всё перепутали, слушайте внимательнее. Он сказал все с точностью до наоборот.
Яндекс маршрут подвел меня под "кирпич". Еду, еду себе, по навигатору, смотрю, кто то мне дорогу перекрывает автомобилем, вижу гаишник уже выходит, говорит: "Ты кирпич проехал!". Лишение прав от 4-х до 6 мес. Хрен знает, может он и омбанул меня, но спорить я с ним не стал, на тот момент, я как то был слегка шокирован, что ЗЕЛЕНЫЙ маршрут проходит прямо по одностороннему движению, в противоположную сторону. Я заподозрил не ладное метров через 10-20) Но было уже поздно, он (Гаишник) уже там ждал.. Он мгновенно подрулил ко мне, и говорит: "Лишение прав от 4- до 6 мес".
Я много раз просматривал, этот проклятый перекресток с разных устройств - НЕТ ТАМ ОДНОСТОРОННЕГО ДВИЖЕНИЯ!
А знаки видно новенькие, и да их отлично видно, на перекрестке, висит очень высоко, да и навигатор говорит "Прямо один километр.."
Случайность??
Не думаю..
Гугл карты считают лучшие маршруты и как минимум 2-3 варианта. Яндекс последнее время вообще не адекватен