Общее·количество·просмотров·страницы

четверг, 29 сентября 2011 г.

Маршрут №4 - Поиск вроцлавских гномов


Вроцлав – один из крупнейших и старейших городов Польши, расположенный на берегах 5 рек (Одра и 4 её притока), и входящий, наряду с Венецией, Амстердамом и Санкт-Петербургом в четверку городов с наибольшим количеством мостов и каналов. Здесь их более ста.
Причин побывать в этом городе множество – это и статус образовательного центра Польши (11 государственных вузов и более 10 негосударственных учебных заведений), и культурного центра (в городе ежегодно проводится множество музыкальных фестивалей), и места, где сохранены уникальные исторические архитектурные достопримечательности и расположен старейший парк с более чем 350-ю видами деревьев и кустарников.
Однако одной из главных достопримечательностей, притягивающих во Вроцлав туристов от мала до велика, являются вроцлавские гномы – талисманы и хранители города. С 2004 года – момента, когда на улицах появились первые бронзовые фигурки, и до настоящего времени численность гномов перевалила за сотню. Объясняется все очень просто, считается что гномы приносят удачу, и чем их больше на городских улицах, тем больше развивается и процветает город.
Для приезжающих туристов – отыскать и сфотографировать как можно больше маленьких местных жителей – увлекательная задача. Поэтому многие прокладывают маршрут следования по городу таким образом, чтобы отыскать максимально-возможное количество бронзовых фигурок. Даже есть чудаки, которые покупают в сувенирных лавках специальные наборы – мягкие тапочки (чтобы не спугнуть гнома), лупу (чтобы разглядеть) и мазь (чтобы натереть мозоли на ногах после долгих поисков).
Можно, конечно, формально подойти к вопросу, сфотографироваться с фигурками, которые расположены у всех на виду (например, два Сизифа, катящих тяжелый гранитный шар по мостовой на Рыночной площади или три убогих гнома недалеко от Ратуши) и пойти пробовать пиво в старейшую в Европе пивную таверну «Piwnica Swidnica». Либо неформально, вспомнить детство, прятки, включить воображение и пойти бродить по улицам в поисках маленьких проказников.
Главная проблема для туриста, который оказался во Вроцлаве проездом (на один день или еще хуже, на несколько часов) это сокращение временных затрат на поиски гномов (а точнее выделение времени на поиск из общего времени пребывания в городе). В конце концов, на гномах свет клином не сошелся, и в городе много других красивых и интересных мест куда можно сходить.
Поэтому настоящему туристу еще до начала поисков приходит мысль «а как оптимально составит свой маршрут?». И туристу-транспортнику на ум приходит ответ –  используя методы задачи коммивояжера.
Для тех, кто не знает, суть задачи коммивояжера заключается в том, что имеется несколько пунктов, которые коммивояжер должен посетить по одному разу, пройдя при этом минимальное расстояние (или затратив минимум времени). При этом коммивояжеру известны все расстояния между пунктами.  На первый взгляд все просто: коммивояжер – это турист, пункты – места, где прячутся гномы. Расстояния между пунктами (гномами) – тоже не проблема – в сувенирных лавках (а кому жалко злотых – в интернете) можно купить карту, на которой нанесено месторасположение краснолюдков (так гномов называют в Польше).
Но на практике, все гораздо труднее:
во первых, в отличие от коммивояжера, на туриста оказывает сильное влияние внешняя обстановка (начиная от изумительных по красоте зданий, на которые постоянно отвлекаешь внимание и заканчивая чудесными запахами из расположенных поблизости ресторанчиков и кафе). В такой обстановке, легко не заметить гномика. К слову, средний рост краснолюдков не превышает 30 см.
во вторых, сам процесс поиска достаточно сложный, поскольку большинство гномов находятся не на виду, а действительно спрятаны. Приходится смотреть не только под ноги, но и крутить головой по сторонам и вверх – располагаться они могут  где угодно – на фонарном столбе, стене дома, подоконнике, под крыльцом или в другом укромном месте.
в третьих, месторасположение гномов на картах достаточно условно, т.е. дана подсказка в виде дома, перекрестка или площади, где можно найти гнома, а дальше все зависит от внимания, смекалки и удачи туриста. К тому же число гномов на разных картах зачастую не совпадает.
Так вот, если отбросить математику, формулы и прочие вещи (да простят меня математики) и в двух словах описать идею способов решения задачи коммивояжера применительно к гномам, то вот что получится:
Способ первый. «Смотри в карту и иди к ближайшему гному, которого еще ни видел». Такой способ решения задачи коммивояжера принято называть жадным алгоритмом. Используя этот алгоритм нахождения наикратчайшего расстояния путём выбора самого короткого, ещё не выбранного ребра (т.е. пути от одного гнома другому), при условии, что оно не образует цикла с уже выбранными ребрами. А «жадным» этот алгоритм называется потому, что в конце маршрута за жадность придется расплатиться, поскольку обход последних в списке фигурок, будет осуществляется по самым длинным ребрам.
Способ второй. «Соедини на карте гномов и обходи их таким образом чтобы путешествуя от гнома к гному не смог вернутся в то место, где уже был». Такой способ решения называется алгоритмом минимального остовного дерева. Остовное дерево состоит из некоторого подмножества рёбер, таких, что из любой вершины можно попасть в любую другую вершину, двигаясь по этим рёбрами, то есть из любой вершины нельзя попасть в саму себя, не пройдя какое-то ребро дважды. Способ более эффективный по сравнению с предыдущим, но и более сложный по расчетам.
Способ третий. «Перебирай по карте варианты обхода всех гномов до тех пор, пока не отыщешь оптимальный маршрут». Такой способ решения называется методом ветвей и границ. Его идея заключается в разбиении (ветвлении) множества допустимых решений на подмножества с оценкой того, содержит ли данное подмножество оптимальное решение или нет. Если нижняя граница для подмножества A дерева поиска больше, чем верхняя граница какого-либо ранее просмотренного подмножества B, то A может быть исключено из дальнейшего рассмотрения. Путем перебора вариантов подмножеств и отсеивания вариантов с наибольшим расстоянием, из неотброшенных подмножеств выбирается наиболее перспективное. Способ самый трудоемкий, но позволяющий отыскать оптимальный вариант.
Конечно, использование любого из описанных способов поиска, без наличия специальных знаний (и умений), практически невозможно. И вряд ли найдется такой турист, который вооружившись учебником и калькулятором будет высчитывать оптимальную траекторию перемещения по городу. Скорее всего, данная траектория будет им выбрана интуитивно. Да и не нужна в таких делах математика. Достаточно уловить идею любого из способов, подойти к вопросу творчески и составить свой маршрут так, чтобы было интересно, и поездка запомнилась надолго.

И самое главное, при встрече с гномом, если он не будет против, нужно обязательно потереть какую-нибудь часть его тела. Говорят, на удачу! 
 ФОТОРЕПОРТАЖ

3 комментария:

  1. Чудесно!!!Уже мечтаю стать коммивояжером и найти всех гномов!!!!Уже размышляю над алгоритмами поисков этих самых маленьких человечков....действительно, не задумывалась, что и в этом вопросе можно проявить столько творчества!!!Молодец!!!

    ОтветитьУдалить
  2. Я пока что нашла 11 из них, хочется еще больше найти.. Но послезавтра уезжаем :(

    ОтветитьУдалить
  3. Я около 20 гномов отыскал за пару часов. Вот, если поможет ссылка на карту: http://victor.com.ua/poland/Wroclaw/Wroclaw_Gnom.htm

    ОтветитьУдалить