Главная /  Студентам /  ПрактикиОбщие вопроосы транспорта /  Поиск гномов методами задачи коммивояжера

Популярные авторы

  • Александр Нельевич
    Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript
  • Никита Анатольевич
    Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript
  • Ольга
    Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript
  • Дмитрий
    Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript
  • Илья
    Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript
  • Влад
    Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript
  • Алёна
    Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript
  • Александр
    Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript
  • Дамир Шамильевич
    Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript
  • Виктор Сергеевич
    Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript
jSharing.COM - Shape5 - Elegance Template
30.09.2011 11:56

Поиск гномов методами задачи коммивояжера

Автор:  Никита Анатольевич
Оценить
(10 голоса)

Поиск вроцлавских гномов – для любого туриста занимательное занятие, а для «ездуна» оно будет вдвойне интереснее, если подойти к нему творчески

Вроцлав– один из крупнейших и старейших городов Польши, расположенный на берегах 5 рек (Одра и 4 её притока), и входящий, наряду с Венецией, Амстердамом и Санкт-Петербургом в четверку городов с наибольшим количеством мостов и каналов. Здесь их более ста.

 

 

 

Причин побывать в этом городе множество – это и статус образовательного центра Польши (11 государственных вузов и более 10 негосударственных учебных заведений), и культурного центра (в городе ежегодно проводится множество музыкальных фестивалей), и места, где сохранены уникальные исторические архитектурные достопримечательности и расположен старейший парк с более чем 350-ю видами деревьев и кустарников.

Однако одной из главных достопримечательностей, притягивающих во Вроцлав туристов от мала до велика, являются вроцлавские гномы – талисманы и хранители города. С 2004 года – момента, когда на улицах появились первые бронзовые фигурки, и до настоящего времени численность гномов перевалила за сотню. Объясняется все очень просто, считается что гномы приносят удачу, и чем их больше на городских улицах, тем больше развивается и процветает город.

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

Можно, конечно, формально подойти к вопросу, сфотографироваться с фигурками, которые расположены у всех на виду (например, два Сизифа, катящих тяжелый гранитный шар по мостовой на Рыночной площади или три убогих гнома недалеко от Ратуши) и пойти пробовать пиво в старейшую в Европе пивную таверну «Piwnica Swidnica». Либо неформально, вспомнить детство, прятки, включить воображение и пойти бродить по улицам в поисках маленьких проказников.

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

Поэтому настоящему туристу еще до начала поисков приходит мысль «а как оптимально составит свой маршрут?». И туристу-транспортнику на ум приходит ответ –  используя методы задачи коммивояжера.

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

Но на практике, все гораздо труднее:

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

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

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

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

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

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

Способ третий. «Перебирай по карте варианты обхода всех гномов до тех пор, пока не отыщешь оптимальный маршрут». Такой способ решения называется методом ветвей и границ. Его идея заключается в разбиении (ветвлении) множества допустимых решений на подмножества с оценкой того, содержит ли данное подмножество оптимальное решение или нет. Если нижняя граница для подмножества A дерева поиска больше, чем верхняя граница какого-либо ранее просмотренного подмножества B, то A может быть исключено из дальнейшего рассмотрения. Путем перебора вариантов подмножеств и отсеивания вариантов с наибольшим расстоянием, из неотброшенных подмножеств выбирается наиболее перспективное. Способ самый трудоемкий, но позволяющий отыскать оптимальный вариант.

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

И самое главное, при встрече с гномом, если он не будет против, нужно обязательно потереть какую-нибудь часть его тела. Говорят, на удачу!

Источник


Изменено 02.10.2011 00:47
Еще в этой категории: « Кто изобрел колесо?

Добавить комментарий


Защитный код
Обновить

Текущие события


Августа
День железнодорожника
01 Августа, 2018 (Весь день)
__________________________
Октября
День работников азербайджанской железной дороги
13 Октября, 2018 (Весь день)
http://www.calend.ru/holidays/0/0/2200/
__________________________
День работников дорожного хозяйства
17 Октября, 2018 (Весь день)
http://www.calend.ru/holidays/0/0/163/
__________________________ __________________________
Ноября
День железнодорожника Украины
04 Ноября, 2018 (Весь день)
__________________________ __________________________ Смотреть весь календарь

Ближайшие консультации

Сегодня

    Нет консультаций

Сообщение администратору

...

Контактная информация

455000, Россия, г. Магнитогорск, пр. Ленина, 38, ауд. 110, кафедра промышленного транспорта, институт горного дела и транспорта, ФГБОУ ВПО "Магнитогорский государственный технический университет им. Г.И. Носова"

заведующий кафедрой Корнилов Сергей Николаевич, тел. +73519298534, ауд. 108,  kornilov_s_n@logintra.ru

ученый секретарь, разработка и сопровождение сайта Рахмангулов Александр Нельевич, тел. +73519298516, ауд. 110а, ran@logintra.ru

Рейтинги и каталоги

Copyright © 2017. logintra.ru. Designed by Shape5