Ориентирование по выбору. Выбор варианта.

Вот мои соображения на эту тему с формальной, математической позиции: http://vist.diverse.org.ru/tsp/
А как на самом деле происходит выбор варианта в голове? Поделитесь опытом.

Очень интересно, спасибо огромное!
Все варианты не просматривала, из нескольких разобранных - иногда получалось выбрать оптимальный результат :-)



Исправлений: 1. Последний раз редактировал lemur в 22.12.2007, 22:56.

Замечание в статье о том, что всё это хорошо при одинаковой проходимости весьма существенно.

Но уже в Шуваловском парке всё не так просто. Так по расстоянию напрашивался вариант 34-35-40, но 35 был внизу, а 40 снова наверху. Выгоднее было 34-40, а 35 забрать на обратном ходу. Некоторый перебор расстояния и набор высоты снизу на 35 компенсировался ещё и тем, что на 36 можно было бы пробежать берегом пруда без потери высоты. Кроме рельефа, влияет ещё и гидрография.

Есть ещё проблема выбора направления (по или против часовой), только вот на снежной тропе старт и финиш обычно разносят, так что с направлением выбора не возникает. Я бы решал эту проблему так: нужно, чтобы первая половина дистанции была более трудной.

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

Рогейн - отдельная тема. Там в игру вступают новые факторы. Стоимость пунктов не одинаковая. Самих пунктов гораздо больше, чем на классической дистанции. Карту не везде рисуют идеально - дороги прорисованы хорошо, но на территориях между ними можно попасть и в плохую проходимость, и в неожиданный рельеф. Выясняется, что если с одного направления КП берётся легко, то с другого - проблемно, а это заставляет перестраивать весь план. Или днём какой-то КП взять легко, а ночью - это сверхсложная задача. Необходимо учитывать в планировании расположение пунктов питания и попадание на них в удобное время. Правда, и времени на планирование дают существенно больше.

Валерий, не могли бы применить Ваш алгоритм и рассчитать оптимальный путь для дистанции Российского Азимута в СПб-2008? Очень было бы интересно посмотреть. Отсутствовала гидрография, рельеф, и прочие объекты, которые мы принимаем в расчёт на "обычных" дистанциях. Дистанция получилось чисто "беговой" и, думаю, многим любопытно было бы оценить свои решения.

Можно попробовать. У меня, правда, нет карты - я не участвовал. Вы не могли бы померить обычной линейкой декартовы координаты и прислать мне список: "номер пункта" "x" "y" для каждого пункта, старта и финиша? valeri.mytinski at gmail.com

Попробую. Карта в страшном виде. За начало координат можно принять угол листа карты?

Можно. Все числа получатся положительными - ну и хорошо.

На РА было 18 КП, а программа, вроде, считала только до 14 пунктов?

lemur Написал(а):
-------------------------------------------------------
> На РА было 18 КП, а программа, вроде, считала
> только до 14 пунктов?

Точно так - время счёта растёт как факториал, так что для "честного" обсчёта 18 пунктов и года не хватит.
Надо на "карту" посмотреть. Например, если всё множество пунктов явно распадается на 2, можно эти два куска по отдельности обсчитать.

Распадаются на два множества: 12 и 6 пунктов.

будут варианты соединения: перегоны 41-44 (или 32-44) и 42-48 (это для тех, кто бегал и кого осталось что-то от карты :-))



Исправлений: 1. Последний раз редактировал lemur в 18.05.2008, 22:33.

Отлично. Координаты получу - посчитаю.

Три варианта соединений дают следующие минимальные пути:

1)К-41-44-Ф 578.1мм=4.336км

К-42-40-39-38-37-36-35-34-33-32-31-41-44-46-45-43-47-48-Ф

2)К-32-44-Ф 562.2мм=4.217км

К-42-41-40-39-38-37-35-34-36-31-33-32-44-46-45-43-47-48-Ф

3)К-42-48-Ф 579.8мм=4.349км

К-41-31-32-33-34-35-36-37-38-39-40-42-48-47-43-45-46-44-Ф

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

Спасибо!

Я бежала по первому варианту.

наверное данный алгоритм можно улучшить! http://en.wikipedia.org/wiki/Travelling_salesman_problem#cite_note-3


не забываем копировать всю ссылку до конца!



Исправлений: 1. Последний раз редактировал serg-yakor в 19.05.2008, 22:47.

Спасибо, Валерий! Бежал в точности по 2-му варианту, как и многие, действительно. Заранее известная карта на старте помогла выбрать оптимальный маршрут правильно.

МАлевский Написал(а):
-------------------------------------------------------
> Спасибо, Валерий! Бежал в точности по 2-му
> варианту

Спасибо Вам за координаты и карту, lemur спасибо за варианты разбиения.
serg-yakor, спасибо за ссылку, надеюсь, с оптимизациями можно будет сделать что-то практически полезное для народа.

serg-yakor Написал(а):
-------------------------------------------------------
> самое смешное что большая часть ориентировщиков
> именно так и бежала ( 2 вариант )
> так что во многих случаях даже на подсазнательном
> (интуитивном уровне )
> задача решается правильно!

Я тоже шёл по варианту 2. Но неужели задача решается "интуитивно"?! Я, например, за минуту правильного решения не видел - только где-то через 5. На "Снежной тропе" так много думать не дают.

А решается задача вот как: из восемнадцати перегонов второго варианта четырнадцать представляют собой движение к ближайшему невзятому КП. Исключение составляют перегоны: 42-41, 37-35, 35-34 и 46-45, которые определяются визуально и позволяют взять стоящие в стороне от "генеральной линии" 41, 35, 34, 46, 45.

Это я к вопросу об эффективности программы, осуществляющей полный перебор. Конечно, полный перебор - это 100% надёжности, но время решения растёт в факториале от числа КП, т.е. гораздо быстрее геометрической прогрессии. Для решения "задачи коммивояжёра" существуют и другие алгоритмы, моделирующие мышление человека. Можно, например, ввести, кроме таблицы координат КП таблицу "реальных" перегонов, связывающих каждый КП с 3-4 ближайшими и запретить рассмотрение остальных перегонов. Можно на каждый такой перегон дать (экспертно)поправочный коэффициент к длине, учитывающий проходимость, рельеф и гидрографию, тогда можно будет работать и с парками типа Шуваловского.

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

Решение задачи начал опять-таки по принципу ближайшего КП. Таковых два - 36 и 34 (визуально сложно уловить разницу). Но 36 - ближайший к финишу, стартовать нужно однозначно через 34. Дальше получается связка 32-37-40, к которой нужно присоединить не вписывающийся в принцип ближайшего КП 35. Сравнение по распечаткам показало, что 32-35-37-40 оптимальнее, хотя визуально за минуту я этого не уловил и проиграл 20 метров на варианте 32-37-35-40. Дальше выбор между 42 и 43 должен быть сделан в пользу 42 с вариантом: 42-43-46-49-45. Если начать с 43, то в конце петли окажешься на 42 и будешь гораздо дальше и от 44, и от 48. Дальнейшее однозначно и полностью отвечает принципу ближайшего КП. Таким образом, оптимальный маршрут длиной 4,99км это: 34-32-35-37-40-42-43-46-49-45-48-44-47-41-39-38-33-31-36-100. Сомневаюсь, что просчёт на компьютере даст иной результат. Спасибо организаторам - всё было интересно и в то же время решаемо за одну минуту.

Ну и по горячим следам - только что опубликованы результаты со сплитами. В четырёх группах, где нужно было взять все 20 КП, спортсмены, избравшие указанный путь, добились следующих лучших результатов:
М18: Заслонкин Пётр - 2 место
М20: Махнев Вячеслав - 4 место
М21: никто так не бежал. Игорь Горбатенков (1 место), похоже, настолько был уверен в своих силах, что не задумывался над порядком взятия (чего стоит только финиш 44-100). Александр Райков (2 место) отклонился от оптимального пути, уйдя с 40 на 43 (см. 2-ю развилку в моём описании)
М40: Дмитрий Новокшёнов - 1 место

То есть, в отличие от "Российского Азимута" (где времени на размышление было больше), оптимальный путь нашло не так много спортсменов, а сильнейшие (кроме умудрённых опытом ветеранов) и не пытались этого сделать.

Если есть возможность, выложите, пожалуйста, карту дистанции. Очень хочется посмотреть на эти варианты.

Роман Написал(а):
-------------------------------------------------------
> Если есть возможность, выложите, пожалуйста, карту
> дистанции. Очень хочется посмотреть на эти
> варианты.

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