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

[Sorg]

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

при выборе оптимального маршрута (быстрейшая стратегия) целевая функция алгоритма построения маршрута f=t, т.е. просто время. Алгоритм пытается его (время в пути) минимизировать.

при выборе кратчайшего маршрута целевая функция f=s, т.е. расстояние. Алгоритм пытается минимизировать расстояние.

оптимальный маршрут может быть построен, если учесть время и расстояние, т.е. целевая функция должна быть такая: f=t*(1-a)+s*a,

где a - коэффициент, задаваемый пользователем (у каждого же свое представление об оптимальности). Коэффициент этот задается в процентах (0-100%), а еще лучше ползуночком:

время <====================> расстояние

В крайнем левом положении a=0, целевая функция становится такой: f=t (т.е. быстрейшая стратегия).

В крайнем правом положении a=1 (100%), целевая функция тогда становится такой: f=s (т.е. кратчайшая стратегия).

В промежуточном положении учитывается как время в пути, так и расстояние. Т.е. при a=0.5 (50%) мы получаем целевую функцию f=0.5*t+0.5*s. Время и расстояние учитываются поровну, это значит что маршрут быстрее на 10% по времени и длиннее на 15% не будет более оптимальным, а быстрее на 10% и длиннее на 5% будет. При a=0.2 получим f=0.8*t+0.2*s, т.е. время в 4 раза ценнее расстояния, и выигрыш по времени на 5% будет оптимальнее при увеличении маршрута не более чем на 20%.

Выбор ползунком довольно удобен, как мне кажется, и интуитивно понятен.

Реализуется это дело просто (опять же как мне кажется), надо подправить целевую функцию в алгоритме.

Меню не захламляет (одним ползунком можно заменить как минимум 2 варианта стратегии расчета маршрута).

[aka_serge]

А откуда вы знаете, что не так реализовано? ;)

[WhAle_15]

Sorg,

[WhAle_15]

А откуда вы знаете

А мы и не знаем.

Вот, что ползунка нет - факт и то, что смело предложит мотать 50 км ради 5 минут экономии расчётного _{(что, далеко не истинно)} времени - тоже факт

[s35]

!!! Все гениальное-просто!!!

[demalina]

да ну нафиг. разорваться что ли между временем и расстоянием?

я вот не знаю что мне важнее.

проще считать по бензину.

если едем длинные участки по 60-120км/час - расход, к примеру, 7литров поставить.

если тупим короткие по 5-20 - поставить 10литров на сотню.

и считать деньги.

по минимуму денег и строить маршрут (включая ЗСД, кстати говоря)

[ERER]

А вот лично мне хотелось бы оптимизации по средней скорости, т.к. предпочитаю, к примеру, проехать по "пустому" КАДу на 10 минут дольше, чем на 10 минут меньше, но толкаясь в пробках. :)

[WhAle_15]

предпочитаю, к примеру, проехать по "пустому" КАДу на 10 минут дольше, чем на 10 минут меньше, но толкаясь в пробках.

Да, Вы, эстет, батенька!

Давайте ещё и опцию дорожного трафика реализуем ползунком. Для желающих побольше трафика - двигаем ползунок правее. Для любителей свободной езды - двигаем левее. Ваще кайф будет, блин!

Не, ну вы серьёзно?! ...Бензин... Скорость :lol::lol:

Изменено 24 мая, 2011 пользователем WhAle_15

[ERER]

Да, Вы, эстет, батенька!

...

Не, ну вы серьёзно?! ...Бензин... Скорость :lol:

Про скорость - абсолютно серьезно. Более того, это чаще всего приводит к значительной экономии времени, т.к. СГ всегда слишком оптимистичен в оценке времени при достаточной пробочности в городе.

[WhAle_15]

это чаще всего приводит к значительной экономии времени, т.к. СГ всегда слишком оптимистичен в оценке времени

Это уже недостатки алгоритма СГ, а никак не самой идеи, предложенной Sorg'ом. Разные вещи.

[ERER]

Это уже недостатки алгоритма СГ, а никак не самой идеи, предложенной Sorg'ом. Разные вещи.

А причем тут идея Sorg-a?

Оптимизация по скорости это еще один вариант оптимизации, отличный от времени и расстояния. И дело тут не только в недостатке алгоритма СГ. Даже при идеальной оптимизации по СГ-овски, он не поведет по маршруту на 10 км длиннее и 5 минут дольше, но при большей средней скорости движения.

[WhAle_15]

Оптимизация по скорости

Пытаюсь представить себе в чём разница этого типа от "временного" (?)

С датчиков собираются данные о скорости на участках дорог, по ним вычисляется расчётное время в пути. Для чего использовать просто скорость?

Поясни.

[Sorg]

да ну нафиг. разорваться что ли между временем и расстоянием?

я вот не знаю что мне важнее.

проще считать по бензину.

если едем длинные участки по 60-120км/час - расход, к примеру, 7литров поставить.

если тупим короткие по 5-20 - поставить 10литров на сотню.

и считать деньги.

по минимуму денег и строить маршрут (включая ЗСД, кстати говоря)

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

1. Сдается мне, что хотите вы одного и того же. Прокладку маршрутов с максимальной средней скоростью. Там и выигрыш по времени из-за проблем в алгоритме, и экономия бензина на крейсерской скорости.

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

[WhAle_15]

Вообще у меня есть что сказать по вашим пожеланиям, но в отдельной теме.

Давай здесь, бро! Основная мысль понятна, думаю, можно и расширить саму тему размышлениями непосредственно по алгоритмам.

_{PS. Люблю математику}

[Sorg]

Давай здесь, бро! Основная мысль понятна, думаю, можно и расширить саму тему размышлениями непосредственно по алгоритмам.

Ну разве что по просьбам трудящихся. Но если тема превратится в флейм я буду в тебя тыкать пальцем

Для оптимизации по максимальной средней скорости целевая функция f=t/s. Но в чистом виде использовать такую функцию небезопасно.

При наличии быстрой длинной трассы неподалеку может ей злоупотреблять. Т.е. две точки, между ними по прямой 5км со средней скоростью 60км/ч, а по КАД 200км (вокруг города, к примеру) со средней скоростью 100км/ч. Более оптимальным по скорости будет мотать 200км по КАД.

Для исключения такой ситуации надо учитывать кроме средней скорости еще длину полученного маршрута с небольшим коэффициентом (f=0.1*s+0.9*t/s), тогда вполне себе получится удобный режим для любителей погонять по КАД.

[WhAle_15]

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

Предполагаю, что для типа "кратчайший", в расчётах используется такой признак ребра, как "длина". А для типа "быстрейший" уже используется его признак "скорость". То есть, при поиске кратчайшего маршрута от точки А в точку Б, находим такой, где сумма признаков "длина" на всём протяжении маршрута является минимальной. При поиске быстрейшего маршрута, подобный расчёт производим уже по признаку "скорость"(абсолютно не учитывая длину). Непонятно пока, как в связующей функции (для ползунка) распределись зависимости между этими признаками. Это выглядит как сравнение тёплого с мягким.

Либо нужно сперва находить "кратчайший маршрут", затем сразу искать "быстрейший" и на основании полученных данных оптимизировать итоговый маршрут, в зависимости от настроек оговоренных коэффициентов. Но эта процедура может сильно утяжелить по ресурсам и времени сам поиск. В общем, есть на форуме шахматисты?

_{PS: это только мои догадки}

Изменено 24 мая, 2011 пользователем WhAle_15

[aka_serge]

А какие бы алгоритмы предложил уважаемый Sorg для вариантов "блондинко" и "я сам знаю как быстрее"?

[IШIN]

Кстати, помните? -

некоторые идеи перекликаются.

[IШIN]

А какие бы алгоритмы предложил уважаемый Sorg для вариантов "блондинко" и "я сам знаю как быстрее"?

Для "я сам знаю как быстрее" надо добавить только всплывающее сообщение "зря вы не купили белку" (Помните Вупи Голдберг в "Крысиных бегах"?)

Последние три раза (в течение трех недель), когда я говорил "я сам знаю как быстрее", я утыкался в разного рода препятствия (типа дорожников, пропускающих потоки в реверсивном режиме). Раньше я чаще угадывал. То ли я тупею, то ли СГ умнеет.

Кстати, а для блондинок в теме "маршрут экономичный" (см. прошлый пост) предлагалось оставить все как есть - минимум настроек. Финиш-Фавориты-Мама-Поехали.

Изменено 24 мая, 2011 пользователем IШIN

[Sorg]

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

Предполагаю, что для типа "кратчайший", в расчётах используется такой признак ребра, как "длина". А для типа "быстрейший" уже используется его признак "скорость". То есть, при поиске кратчайшего маршрута от точки А в точку Б, находим такой, где сумма признаков "длина" на всём протяжении маршрута является минимальной. При поиске быстрейшего маршрута, подобный расчёт производим уже по признаку "скорость"(абсолютно не учитывая длину). Непонятно пока, как в связующей функции (для ползунка) распределись зависимости между этими признаками. Это выглядит как сравнение тёплого с мягким.

Либо нужно сперва находить "кратчайший маршрут", затем сразу искать "быстрейший" и на основании полученных данных оптимизировать итоговый маршрут, в зависимости от настроек оговоренных коэффициентов. Но эта процедура может сильно утяжелить по ресурсам и времени сам поиск. В общем, есть на форуме шахматисты?

_{PS: это только мои догадки}

У каждого ребра есть параметры скорость (v) и длина (s). Из этих данных легко посчитать время, необходимое для поезда ребра (t=s/v). Все эти данные можно использовать для расчета целевой функции. Можно только s, можно только t, а можно и одновременно. Для типа "кратчайший" используется только s, для типа "оптимальный" только t. А для по-настоящему оптимального надо использовать сразу оба. Дополнительно ресурсов не должно много понадобиться.

А какие бы алгоритмы предложил уважаемый Sorg для вариантов "блондинко" и "я сам знаю как быстрее"?

Варианты "блондинко" и "я сам знаю как быстрее" предлагаю оставить как есть. Как это относится к обсуждаемой теме?

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

[PsevDANIm]

У каждого ребра есть параметры скорость (v) и длина (s). Из этих данных легко посчитать время, необходимое для поезда ребра (t=s/v).

Если ничего не путаю - это в данный момент реализовано.

[WhAle_15]

Для типа "кратчайший" используется только s, для типа "оптимальный" только t. А для по-настоящему оптимального надо использовать сразу оба. Дополнительно ресурсов не должно много понадобиться.

Звучит разумно. Тогда получается, что каждое ребро должно получить новый признак, так называемой, "оптимальности", который как раз и будет вычисляться в зависимости от длины s и скорости v, непосредственно для каждого ребра дорожного графа по указанной в начале темы формуле балансировки. Именно по этому признаку и должны будут производиться вычисления по поиску оптимального маршрута. И этот признак должен пересчитываться КАЖДЫЙ РАЗ при обновлении пробочной информации для всех ребер графа (или только для тех, значения которых изменились). Если это укладывается в рамки допустимых ресурсов и мощностей, используемого большинством железа, то идея здравая.

_{PS: А вообще, интересно обсуждать вещи, фактический принцип действия которых не известен. Будем считать, что мы на передаче Гордона анализируем математические алгоритмы}

[andrej]

В пробке (когда скорость по мониторингу меньше скорости допустимой Vm<Vd) время проезда ребра субъективно (по ощущениям водителя) увеличивается в меру его личной нетерпеливости.

Если дать водителю шкалу, где бы он движком сам выбрал свой темперамент Tm в границах от 1 до 3, то при выборе оптимальной стратегии (по времени) считаем:

Если на ребре Vm<Vd, то время проезда ребра не t=S/Vm, как сейчас, а t=Tm*S/Vm.

Дальше обработка графа как обычно.

Водителю достаточно выбрав стратегию "Оптимальную", один раз определить свой личный темперамент, и ему всегда будут предлагаться маршруты с наименьшей длиной потерянных нервов.

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

[Sorg]

Разброд таки начался... А вот еще так можно и вот так можно...

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

P.S. Конструктивная критика очень приветствуется (особенно ежели с примерами и формулами).

P.P.S. Я был бы безмерно счастлив услышать критику непосредственно от программистов МИТ (а также администрации, тестеров и вообще кого угодно, кто хотя бы в подзорную трубу видел исходники СитиГида).

[WhAle_15]

для того чтобы донести до программистов МИТ (а также администрации, тестеров и т.д.)

на этой фразе мир пополнился не одной дюжиной улыбок :)