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

Sorg,

1306240379-248.jpg

Link to post
Share on other sites

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

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

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

Link to post
Share on other sites

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

Link to post
Share on other sites

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

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

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

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

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

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

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

  • Upvote 1
Link to post
Share on other sites

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

  • Upvote 1
Link to post
Share on other sites

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

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

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

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

Edited by WhAle_15
Link to post
Share on other sites

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

...

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

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

Link to post
Share on other sites

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

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

Link to post
Share on other sites

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

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

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

Link to post
Share on other sites

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

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

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

Поясни.

Link to post
Share on other sites

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

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

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

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

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

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

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

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

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

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

Link to post
Share on other sites

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

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

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

Link to post
Share on other sites

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

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

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

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

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

Link to post
Share on other sites

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

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

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

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

Edited by WhAle_15
Link to post
Share on other sites

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

Link to post
Share on other sites

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

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

Link to post
Share on other sites

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

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

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

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

Edited by IШIN
Link to post
Share on other sites

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

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

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

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

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

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

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

Edited by Sorg
  • Upvote 1
Link to post
Share on other sites

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

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

Link to post
Share on other sites

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

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

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

Link to post
Share on other sites

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

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

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

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

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

Edited by andrej
  • Upvote 1
Link to post
Share on other sites

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

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

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

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

  • Upvote 1
Link to post
Share on other sites

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

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

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

×
×
  • Create New...