Задача коммивояжёра & GPS.

[Bulawka]

Какому навигационному софту по силу сабж?
Ну точнее, в БГ-смысле -- расставить заданные точки в оптимальной последовательности прохождения с учётом выбранного способа передвижения?
iGO точно может, СитиГид, насколько я понял, нет.
Кто ещё может?

[Nof]

Ох мудриииииите вы :)

Ну и я молчу о том, что о синих заборах навигатор, скорее всего, будет в неведении. Как и о проходных дворах :)

[MegaManiac]

Он на автомобиле.

[Bulawka]

Он на автомобиле.

Я этого не говорил. )))
На самом деле, она и в пешесмысле м.б. актуальна, ну в смысле если не охота думать головой.
В частности, с опцией "напрямик". Типа составил маршрут оптимальный напрямик, а потом уж думаешь, как этот напрямик пробежать максимально прямо.
Засада тока в реках (без мостов у нужном месте), КАД-ах, ж/д и т.п. линейных препятствиях.

[XYZ]

кроме igo я почему то нигде не встречал. хотя я им не пользуюсь, но думаю что наверняка tomtom может, они с igo главные конкуренты.
osmand ещё маршруты строит, но то как он это делает - привело меня в тихий ужас.

[Bulawka]

Он на автомобиле.

Я этого не говорил. )))
На самом деле, она и в пешесмысле м.б. актуальна, ну в смысле если не охота думать головой.

Я в своё время, кстати, пытался запрограммировать (точнее, пытался сформулировать задачу, поскольку не программист ни в одной букве) навигационный софт под городской рогейн.
Типа ввёл туда все КП (с "ценами"), контрольное время и свою расчётную скорость -- он тебе и выдал оптимальный маршрут, с учётом ценности КП, "коммивояжёристости" и т.п.
Видишь что скорость отличается от расчётной -- софт пересчитывает маршрут.
Но дальше поставновки задачи дело не пошло, по крайней мере пока. ))
Наверняка такое уже написано сто лет назад, кстати.

[Musatych]

Наверняка такое уже написано сто лет назад, кстати.

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

[Bulawka]

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

[MegaManiac]

Не вижу ничего особо сложного в алгоритме.

Ну, так Нобелевка почти в кармане тогда.

[Psevdo]

Нету Нобелевки по математике ((( Медаль Филдса, я так понимаю

[Musatych]

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

Если вдруг кто придумает полиномиальный алгоритм, то получит миллион долларов от института Клэя (как Перельман). Если хороший эвристический, то, может быть, премию Гёделя (собственно, Санжив Арора в 2010 году получил).

[Zoom]

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

для Минска такая программа существует и работает. CityInfo 2.8, можете проверить :)

[MegaManiac]

Для любого другого города она тоже существует. Про iGo уже сказано. А циклы светофоров и их количество ваша программа учитывает? А то, что прямо лучше чем зигзагом, даже если длиннее?

[stas-kh]

СитиГид

[Любитель Петербурга]

Что делает GPS в заголовке темы? По-моему, к обсуждаемой математике он никакого отношения не имеет.

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

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

[Bulawka]

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

Применительно к БГ -- десятков точек за глаза.
Тем более применительно к этапу, внутри которого точек менее 10.

[Bulawka]

Для любого другого города она тоже существует. Про iGo уже сказано. А циклы светофоров и их количество ваша программа учитывает? А то, что прямо лучше чем зигзагом, даже если длиннее?

Имхо, это (ситиинфо) чисто минская тема.
Циклы светофоров и их кол-во (а точнее, пропускную способность участка) учитывает имхо тот же "пробочный" ситигайд,
анализируя поступающие к нему данные по этому участку.

[Bulawka]

Например, таких, как неточная локализация КП, возможность движения "по площади" (диагональ через парк, двор) и т.п.

Неточная локализация -- ну нам сверхточность и не нужна.
Просто если решения (оптимальные пути) будут существенно разниться в зависимости от смещения КП  на ± 100 метров -- значит решения, в целом, равноправные.

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

Как раз для рогейна (точнее, для "идеального" рогейна) задача вполне решаема.
Ситуация когда лишний дорогой КП вдалеке, а потом бегом на финиш, окажется выгоднее чем неспешное возвращение с поеданием недорогих КП -- вполне возможна.
Другое дело что в рогейне нет роутинга, ну или почти нет...
Ну то есть софт "рогейн на плоскости без дорог" -- скажем огромное поле -- вполне написуем, согласитесь.
И мощности компьютеров будет хватать на суточное число точек даже простым перебором, согласитесь.
Если от поля перейти к реальной ситуации -- то да, учесть рельеф и тем более дороги -- довольно сложно (потому что нет хороших подробных векторных карт со всеми дорожками и с реальным учётом их бегопроходимости).
Блин, хоть садись и языг изучай.... ))) На чём счас круто программировать, что изучить для написания сабжа?

[MegaManiac]

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

Возможно. Но я не об этом.

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

[MegaManiac]

что изучить для написания сабжа?

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

[Musatych]

Bulawka, действительно рогейн из 15 точек на плоскости можно написать перебором на любом языке программирования. Если точек будет хотя бы 30, то уже надо будет использоваться метод ветвей и границ или что-нибудь ещё. Но проблема-то как раз в том, что у нас не плоскость, а граф из дорог, поэтому нужно искать кратчайший путь по дорогам, а тут уже промежуточных точек могут быть десятки, а всего точек в рассмотрении тысячи.

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

[Psevdo]

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

[MegaManiac]

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

Не спорю. :) А возможно, еще быстрее - дворами. Но 100% адекватных средств навигации в городе для пешеходов/велосипедистов просто не существует, так что пишу о том, что есть...

[Димас из Зелика]

а ещё и качество покрытия дороги играет свою немаловажную роль.это для всех категорий актуально

[Bulawka]

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

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