Jump to content
GPS навигатор СитиГИД

Соединим постранство и время


Recommended Posts

  • Replies 56
  • Created
  • Last Reply

Top Posters In This Topic

Top Posters In This Topic

Popular Posts

Сегодня в очередной раз задумался над вопросом как научить СитиГид не водить кругами ради экономии двух минут. И вот такая шальная мысль пришла в голову (немного математики): при выборе оптимального

Признаться, не сразу сообразил, как Sorg собрался время с расстоянием складывать. Кроме Эйнштейновского пространства-времени не помню такого замеса. Из-за этого непонимания наверно раньше никто до

Для чего появилась эта тема? Для решения проблемы о включении навигатором в маршрут длинных скоростных отрезков ради небольшой экономии времени. Даже если пробочная информация абсолютно точно отража

Posted Images

Если хотели достучаться до разрабов, то пишите в саппорт.

Link to post
Share on other sites

Всё верно, коллега. :)

Link to post
Share on other sites

Дружно реквестируем фичу?

Идея однозначно хороша. Возможно кто то из администрации прокомментирует возможность тестирования данного алгоритма внутри команды СГ?

ИМХО: проверить работу на реальных данных - время одного дня. Возможно - я ошибаюсь.

Короче нужны комментарии от СГ, т.к. весь алгоритм (простейший!) пользователи уже обсудили.

  • Upvote 1
Link to post
Share on other sites
  • 2 weeks later...

Что-то все здесь притихли :)

Пожалуй, подкину немного теории

И на затравку - загадка (правда, она на английском, но понять можно)

Краткое описание:

Требуется соединить между собой 4 города так, чтобы длина построенных дорог была минимальной.

Предлагается найти решение для городов расположенных на углах квадрата с длиной стороны в одну милю.

Ответ под спойлером даёт решение для любого количества городов (думаем, господа)

Link to post
Share on other sites

Ответ под спойлером даёт решение для любого количества городов (думаем, господа)

И сразу сказал кто убийца в этом детективе.

Собачья кость с длиной пути: 1+sqr(3) мили.

А для построения указал бы сразу http://ru.wikipedia.org/wiki/%D0%A2%D0%BE%D1%87%D0%BA%D0%B0_%D0%A4%D0%B5%D1%80%D0%BC%D0%B0

Откуда длина средней перемычки кости: 1-1/sqr(3) и 4 отростка на концах перемычки по 1/sqr(3) мили.

Link to post
Share on other sites

andrej, вот иллюстрация для конкретно этого случая

1307639822-582.jpg

Link to post
Share on other sites

С иллюстрациями у меня так быстро не получается.

А если соединить три точки через точку Ферми, а четвертую добавить одномильным отрезком к соседней, то будет путь 2,66 мили (надеюсь не ошибся). L=2/3 *sqr(6) + (3*sqr(2)-sqr(6))/6 + 1 ~2,93 мили. Ошибся однако.

А в собачьей кости 2,73 мили.

Edited by andrej
Link to post
Share on other sites

Т.е. при a=0.5 (50%) мы получаем целевую функцию f=0.5*t+0.5*s

Если просто так использовать эту формулу, получится что в положении 50:50 один километр будет оцениваться так же как один час (или одна секунда, или одна минута) - что глупо. В прямую складывать километры с часами нельзя.

В теории относительности интервал считается как l^2=-(ct)^2+s^2.

Т.е. одна секунда сравнивается с расстоянием, которую свет проходит за одну секунду.

Соответственно, формула для автомобиля должна выглядеть как

f=V*t*(A)+s*(1-A),

где V - характерная скорость автомобиля, или просто ожидаемая средняя скорость автомобиля в городе, например 20 км/ч.

Edited by Пирс
  • Upvote 2
Link to post
Share on other sites

Если просто так использовать эту формулу, получится что в положении 50:50 один километр будет оцениваться так же как один час (или одна секунда, или одна минута) - что глупо. В прямую складывать километры с часами нельзя.

В теории относительности интервал считается как l^2=-(ct)^2+s^2.

Т.е. одна секунда сравнивается с расстоянием, которую свет проходит за одну секунду.

Соответственно, формула для автомобиля должна выглядеть как

f=V*t*(A)+s*(1-A),

где V - средняя скорость автомобиля, или просто ожидаемая средняя скорость в городе, например 20 км/ч.

Да, думал об этом и ждал когда кто-нибудь заметит :). А тут прямо с ответом и объяснением, спасибо.

Link to post
Share on other sites

Пирс, Sorg, Кто не работает, тот не ошибается! :)

andrej, Да. Если обозначим длину в центре L, а сторону квадрата a, то общая длина всей ломаной будет

L+4* ( ((a–L)/2)2 + (a/2)2)1/2

минимум при L=a+31/2a ~ 2.73

2.66 не получается никак

Link to post
Share on other sites

Подытожил всё к удобоваримому виду:

1307707433-248.jpg

Далее простая геометрия. Имеем два катета, первый b = 1307707576-248.jpg

и второй, равный 1307707640-248.jpg

Далее по Пифагору вычисляем гипотенузу c, как корень из суммы квадратов.

Ну, и соответственно, общая длина будет 1307707881-248.jpg

Минимальное значение этой длины будет 1307708587-248.jpg

Соответственно, в нашем случае, при a=1, получаем значение ~ 2.73 мили

Link to post
Share on other sites

Это то я сразу посчитал, 2.73 (назвал собачья кость), и без окружностей. Проверил на всякий случай другой альтернативный вариант, сначала получил 2.66, обрадовался, написал, потом перепроверил - 2,93, извинился в этом же посте. Потерял уже навыки с первого раза без ошибок решать. Практики давно не было (лет 20). Разбаловали нас компьютеры. Ваше геометрическое решение для этой задачи красиво, правда непонятно как делать построения для более произвольного расположения городов. Имею в виду методику построения оптимальной сети дорог. Прежде чем посчитать вариант, его сначала нужно выбрать. Даже аппарат с мыльными пузырями не даст единственного решения для 20 городов. Он и для 4-х дал 2 варианта, благо, что недолго проверять.

Edited by andrej
Link to post
Share on other sites

Ни себе фига... а я тут путёвку по полчаса считаю, не могу две цифры столбиком правильно сложить.

Link to post
Share on other sites

Да, думал об этом и ждал когда кто-нибудь заметит :). А тут прямо с ответом и объяснением, спасибо.

Добавление в уравнение некоторой "правильной" скорости V может улучшить понимание методики, но не изменит результат.

Было f(i)= s(i)/v(i) *(1-А)+ s(i)*А - от Sorg (andrej добавил индексы)

Теперь предлагается f=V*t*(A)+s*(1-A) - от Пирс

Чтобы сравнить, приведём к однотипному виду.

С учётом, что t нет в исходных данных, оно считается, весовые коэффициенты А и (1-А) поменяны местами, складываются расстояния, а не времена, для удобства сравнения перепишем новое предложение в похожем виде (функциональность не изменится):

Пирс: f(i)= s(i)/v(i) *(1-А)+ s(i)/V*А

Sorg: f(i)= s(i)/v(i) *(1-А)+ s(i)*А (ранее отмечалось, что в правой части s(i)=s(i)/1 - время проезда ребра со скоростью 1 км/ч).

Т.е. в алгоритме Sorg V=1км/ч, а не V=20км/ч, как предлагает Пирс.

Sorg, возможно этого не планировал, но так получается из его формулы.

Оба алгоритма на одинаковых исходных данных дадут одинаковый быстрейший маршрут (для А=0) и одинаковый кратчайший маршрут (для А=1). Это потому, что для поиска маршрута важны не абсолютные значения ключевого параметра, а их соотношения для разных рёбер.

Для промежуточных значений А каждый из алгоритмов будет давать промежуточные варианты маршрутов.

Теперь самое интересное.

При рассмотрении варианта Sorg было понятно (но не озвучено, дабы не усложнять), что выбираемое пользователями удобное для них значение А, вряд ли будет А=0,5.

Ведь ничто не указывает на то, что шкала А (перевод положения ползунка в значение А) должна быть линейна. И тогда логично будет ввести элемент нелинейности в шкалу, (т.е. значение А должно считаться от координаты ползунка по нелинейной функции), чтобы среднее положение ползунка было удобно большинству пользователей.

В варианте алгоритма от Пирс просто изменена нелинейность шкалы (возможно уменьшена) введением произвольно взятого компенсирующего элемента V. Значение V (Пирс) обосновать нельзя (чем 20км/ч лучше 1 км/ч?), его придётся брать эмпирически, как и находить нелинейную функции шкалы.

Но ведь рациональнее один раз перед началом расчёта алгоритма посчитать А по нелинейной функции от положения ползунка (Sorg), чем в каждом цикле алгоритма выполнять лишнее действие (Пирс).

Вариант Пирс написан понятнее, не ломает голову читающему. Может и программисты СитиГида обратят внимание.

Если бы варианты алгоритмов поступили на рассмотрение сообщества в обратном порядке (Пирс, потом Sorg), то Sorg предложил оптимизацию расчётов для варианта Пирс (минус одно действие в цикле).

Edited by andrej
Link to post
Share on other sites

Соглашусь с andrej - иногда реально получается так, что по КАДу ехать быстрее по времени получается, если только ехать по рассчётной скорости, которая чаще всего "120" и это средняя (!) скорость на участке. Мне же, например, комфортней не нестись по левому ряду, а спокойненько плестись соточку - и бензин экономится, и нервов меньше, и тормозной путь короче. Вроде как в ближайшей версии обещали отделить дороги платные от обычных и магистрали от остальных. И тут то и можно бы для себя выставить максимальную скорость на трассах, чтоб в рассчёт бралась именно она, если текущая скорость на участке выше этого лимита.

И тогда может осуществиться мечта многих пользователей - чтоб не тянуло на КАД ради экономии в несколько минут. Для этого просто надо будет поставить себе ограничение чуть меньше, чем твоя "любимая" скорость на КАДе. Тогда СитиГид поведёт туда только в случае реальной экономии времени при движении именно с твоей скоростью, а не как сейчас "если ты пролетишь 130 в час как тот Мазератти с мигалками и сиреной по левому ряду обмигивая всех дальним светом, то сэкономишь целых 6 минут из часового маршрута".

Link to post
Share on other sites

Поставь себе максималку 80-90 км/ч и из-за двух минут тебя на КАД не выгонят.

Выгонят. Если по городу будет 10км со скоростью средней 40, а по КАД будет 20км с твоей выставленной 90 - поедешь по КАД. Полторы минуты экономии на 15 минут маршрута и двойное увеличение расстояния.

И тогда может осуществиться мечта многих пользователей - чтоб не тянуло на КАД ради экономии в несколько минут. Для этого просто надо будет поставить себе ограничение чуть меньше, чем твоя "любимая" скорость на КАДе. Тогда СитиГид поведёт туда только в случае реальной экономии времени при движении именно с твоей скоростью, а не как сейчас "если ты пролетишь 130 в час как тот Мазератти с мигалками и сиреной по левому ряду обмигивая всех дальним светом, то сэкономишь целых 6 минут из часового маршрута".

Если на КАД стоит 120, то в 99% случаев там можно без мигалок и обмигивания дальним проехать 120+. Если все кроме "мазератти" едут 80, то и будет стоять там 80 в абсолютном большинстве случаев. Скорость ставится не максимальная, а последняя пришедшая, т.е. почти всегда будет стоять скорость, с которой большинство едет.

В итоге получается оптимальность маршрута по времени/расстоянию и ограничение расчетной скорости - это две отдельные проблемы, которые в некоторых случаях имеют общие симптомы (прокладывание необоснованно длинного маршрута). Соответственно и решать их надо отдельно. Для ограничения расчетной скорости никаких алгоритмов и формул не нужно, просто надо ввести это ограничение и обсуждать даже нечего.

Link to post
Share on other sites

Выгонят. Если по городу будет 10км со скоростью средней 40, а по КАД будет 20км с твоей выставленной 90 - поедешь по КАД. Полторы минуты экономии на 15 минут маршрута и двойное увеличение расстояния.

Точно, выгонят, нужно дальше думать... А пока за неимением умных мыслей мелкое соображение. Может кого на мысль натолкнёт.

Если свести всю оптимизацию только к экономии топлива, то получается, что при разных способах расчёта маршрута происходит оптимизация под разные автомобили.

Извиняюсь за графики, нацарапал на навигаторе и сюда вставил кое-как (первый блин). Здесь везде показана зависимость мгновенного расхода топлива r(л/сек) от скорости автомобиля v(км/ч).

post-8718-0-81750300-1307912667_thumb.jp

При расчёте Быстрейшего маршрута (А=0) маршрут будет оптимизирован для автомобиля с графиком расхода а). Это строительная техника с расходом топлива по моточасам. Что стоит, что едет - ест одинаково.

При расчёте Кратчайшего маршрута (А=1) маршрут будет оптимизирован для автомобиля б). Это некий идеальный автомобиль, с расходом пропорциональным скорости движения.

При расчёте с А=0,5 предположительно будет оптимизация под автомобиль с графиком расхода в). (Усреднённый между а) и б) ).

Соответственно г) - реальный автомобиль, как я понимаю. На низких скоростях расход не падает к нулю из-за холостого хода, на скоростях выше крейсерской (точка на графике) расход нелинейно возрастает.

Объяснить не могу, но интуитивно чувствую, что по-настоящему оптимальный алгоритм должен оптимизировать маршрут под график г).

Link to post
Share on other sites

Ни себе фига... а я тут путёвку по полчаса считаю, не могу две цифры столбиком правильно сложить.

Ты не одинок. Я тоже себя чувствую чужим на этом празднике жизни.

Link to post
Share on other sites

Точно, выгонят

Так вот, алгоритм предложенный мной в начале этой темы как раз и предназначен для того чтобы не выгоняли :) Только он не учитывает ограничения по скорости личные, т.е. если ты по КАД едешь 90 где у СГ стоит 120, то для тебя это возможно будет не оптимальный маршрут.

Решение в том чтобы использовать два подхода одновременно. Т.е. оптимальный маршрут должен рассчитываться по формуле f= s/v*(1-А)+ s*А, только скорость на ребре надо брать с ограничениями, т.е. v=min(vсг,vплз). vсг - скорость из пробочных данных, vплз - ограничение скорости, выставленное пользователем.

Объяснить не могу, но интуитивно чувствую, что по-настоящему оптимальный алгоритм должен оптимизировать маршрут под график г).

Оптимальность у каждого своя, кому то надо доехать быстрее невзирая на потраченный бензин и износ деталей автомобиля, кому-то надо доехать, потратив минимум топлива, кому-то просто надо спокойно доехать. По настоящему правильный алгоритм должен дать пользователю выбор что ему важнее и уже исходя из этого строить маршрут. Алгоритм изначально оперирует расстоянием, временем и скоростью, водителю также эти понятия хорошо знакомы, так что проще всего "подружить" алгоритм и водителя можно именно на основе этих понятий. Объяснять алгоритму про расход топлива - весьма непростая задача, да думается и водитель вряд ли сможет построить точный график скорость/расход топлива для своего авто. Так что вариант с оптимизацией по расходу мне кажется сильно сомнительным.

P.S. Вообще покупать автомобиль для того чтобы экономить на топливе - это мне кажется нелогичным. У меня, например, самый экономичный маршрут получается на метро :)

Edited by Sorg
Link to post
Share on other sites

Если на КАД стоит 120, то в 99% случаев там можно без мигалок и обмигивания дальним проехать 120+. Если все кроме "мазератти" едут 80, то и будет стоять там 80 в абсолютном большинстве случаев. Скорость ставится не максимальная, а последняя пришедшая, т.е. почти всегда будет стоять скорость, с которой большинство едет.

Именно можно проехать. А вот с какой скоростью поеду - совсем другой вопрос. Если будет острая необходимость сэкономить 10 минут на 50-километровом маршруте по КАД, то я тоже поеду 120+. Но обычно я там еду 90..100, даже если есть возможность лететь быстрее. И поэтому если ставить жёсткое ограничение чуть ниже "номинальной" для себя скорости, на КАД программа будет тянуть только в случае явного выигрыша во времени. Поедешь быстрее - сэкономишь ещё больше.

А вот обратный вариант - на КАДе свободно, и по рассчётам программы при 120 км/ч там реально быстрее, чем через город. Но я там всё равно поеду 90, плюс к моменту моего приближения к нужному съезду там движение уплотнится (а через другой съезд - ещё большая потеря времени).

Link to post
Share on other sites

Именно можно проехать. А вот с какой скоростью поеду - совсем другой вопрос. Если будет острая необходимость сэкономить 10 минут на 50-километровом маршруте по КАД, то я тоже поеду 120+. Но обычно я там еду 90..100, даже если есть возможность лететь быстрее. И поэтому если ставить жёсткое ограничение чуть ниже "номинальной" для себя скорости, на КАД программа будет тянуть только в случае явного выигрыша во времени. Поедешь быстрее - сэкономишь ещё больше.

А вот обратный вариант - на КАДе свободно, и по рассчётам программы при 120 км/ч там реально быстрее, чем через город. Но я там всё равно поеду 90, плюс к моменту моего приближения к нужному съезду там движение уплотнится (а через другой съезд - ещё большая потеря времени).

В предыдущем твоем посте я, видимо, не верно тебя понял. Я решил что ты пишешь про "левые" скорости, поставленные гонщиками с мигалками, т.е. стоит 120 там где реально только 80 можно проехать. Вариант решения про пользовательское ограничение скорости я написал уже в предыдущем своем посте.

Link to post
Share on other sites

Ну чего тут особо заморачиваться?

Всё равно, при любых значениях коэффициентов, будет граничная точка.

Значение чуть меньше отправит по городу, значение чуть больше отправит по КАДу.

Значит нужен ползунок, который позволит пользователю регулировать этот коэффициент.

И каждый сможет опытным путем подобрать то значение, которое его устроит.

Link to post
Share on other sites
Guest
This topic is now closed to further replies.

×
×
  • Create New...