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

[Zvezdochet]

саркатических ;)

[aka_serge]

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

[andrej]

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

Из-за этого непонимания наверно раньше никто до этого и не додумался.

А посидел с карандашиком, проверил.. Алгоритму как оказалось всё равно, работает зараза.

Напоминаю себе самому условия задачи (извините за нудность, но раз сразу не дошло, лучше подробно, я же не один такой)

Имеется конфигурация графа из i рёбер (например i=1000), заданная картой дорог. Выбрано два узла графа (старт и финиш).

Каждому i-му ребру соответствуют:

-Длина ребра s(i) (берётся из карты дорог).

-Скорость на ребре v(i) (из карты дорог + корректировка из данных о пробках).

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

Как способ оптимизации маршрута задаётся формула, позволяющая вычислить для каждого ребра параметр f(i) из существующих параметров s(i) и v(i), привязанных к этому же ребру:

- для быстрейшего маршрута f(i)= s(i)/v(i). (По сути – время проезда ребра со скоростью на ребре).

- для кратчайшего маршрута f(i)=s(i). (По сути f(i)=s(i)/1 - время проезда ребра со скоростью 1 км/ч, для алгоритма главное что скорость одинакова для всех рёбер).

- для оптимального маршрута от Sorg: f(i)= s(i)/v(i) *(1-А)+ s(i)*А, где А - коэффициент, задаваемый пользователем ползуночком от 0 (приоритет времени) до 1 (приоритет расстояния):

Время...................Расстояние

<====================>

А=0..........А=0,5...........А=1

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

Идея однозначно интересна (плюс поставил) и реализуема. Несколько увеличится время расчёта маршрута. Но конкуренты курят в углу.

[WhAle_15]

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

[bobka_rus]

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

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

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

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

[WhAle_15]

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

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

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

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

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

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

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

[andrej]

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

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

Собачья кость с длиной пути: 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) мили.

[WhAle_15]

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

[andrej]

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

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

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

Изменено 9 июня, 2011 пользователем andrej

[Пирс]

Т.е. при 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 км/ч.

Изменено 10 июня, 2011 пользователем Пирс

[Sorg]

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

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

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

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

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

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

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

[WhAle_15]

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

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

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

минимум при L=a+3^1/2a ~ 2.73

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

[WhAle_15]

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

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

и второй, равный

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

Ну, и соответственно, общая длина будет

Минимальное значение этой длины будет

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

[andrej]

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

Изменено 11 июня, 2011 пользователем andrej

[Оцелоп]

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

[andrej]

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

Добавление в уравнение некоторой "правильной" скорости 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 предложил оптимизацию расчётов для варианта Пирс (минус одно действие в цикле).

Изменено 11 июня, 2011 пользователем andrej

[andrej]

Для чего появилась эта тема?

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

Но не все любят летать. Кто-то и на КАД больше 90 не ездит. Если маршрут дан по КАД, он будет в минусе, и ещё время лишнее потеряет.

Но навигатор же не спрашивает. Он учёл в расчёте например 105 км/ч - изволь лететь.

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

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

А поедешь быстрее, чем написал - лишнее время сэкономишь, тогда и за лишние километры не обидно.

Если совсем по правильному, то нужно указывать тип транспортного средства, тогда должны учитываться скорости для данного типа ТС для разных типов дорог согласно ПДД. Это всё равно будет актуально, когда CG дозреет до указания текущей разрешённой скорости и нормального предупреждения о превышении.

Изменено 11 июня, 2011 пользователем andrej

[dmalikov]

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

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

[Sorg]

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

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

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

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

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

[andrej]

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

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

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

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

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

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

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

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

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

[PsevDANIm]

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

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

[Sorg]

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

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

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

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

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

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

Изменено 13 июня, 2011 пользователем Sorg

[dmalikov]

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

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

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

[Sorg]

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

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

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

[eklmn]

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

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

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

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

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