- 14.11.2016
- 591
- 1
Районная научно-практическая конференция старшеклассников
«Юность – науке и технике»
Секция: математика
Исследовательская работа.
Тема: Лабиринты: поиск выхода.
Семенова Юлия Дмитриевна Коновалова Ольга Викторовна
МОУ СОШ №69, 8 «а» класс учитель математики
Город Ижевск, 2008 год
Содержание.
Введение…………………………………………………………………..2
1. История…………………………………………………………………3
1.1 Лабиринты……………………………………………………..3
1.2 Судьба теории графов…………………………………………6
1.3 Ленинградские катакомбы……………………………………9
2. Исследование поиска выхода из лабиринта…………………………16
2.1 Теорема Тремо…………………………………………………16
2.2 Правила правой и левой руки…………………………………18
3. Теория графов………………………………………………………….20
3.1 Основные положения теории графов………………………...20
3.2 Лабиринт как геометрическая сеть…………………………...22
3.3 Теория графов на применении к задачам о лабиринтах…….24
Примеры задач на лабиринты……………………………………………26 Заключение………………………..28
Использованная литература……………………………………………...29
Приложение……………………………………………………………….30
В прошлом учебном году моя исследовательская работа называлась: «Лабиринты: поиск выхода». И в самой работе рассматривались лишь история возникновения лабиринтов и методы решения задач о лабиринтах, присущие младшим классам, а рассмотренные серьезные и действенные решения (но более трудные) были изучены поверхностно. И все же хотелось бы вспомнить методы нахождения выхода из лабиринта, изученные ранее:
1) Метод проб и ошибок.
2) Метод зачеркивания тупиков.
3) Правило одной руки.
4) Лабиринт - как геометрическую сеть.
В этом году мне хотелось бы более подробно рассмотреть геометрическую постановку задачи о лабиринтах, а именно: исследование лабиринтов с помощью теории графов, предложенных Леонардом Эйлером.
Целью работы является выявление более удобного и точного метода решения задач о лабиринтах.
Для осуществления поставленной цели необходимо было выполнить следующие задачи:
· Изучение различных методов нахождения выхода из лабиринта.
· Решение задач с помощью каждого из них.
· Сравнение данных методов решения задач.
1. Из истории
Наверняка, многие из нас встречали в каких - либо журналах или газетах такое занимательное развлечение, как лабиринты. Но не все знают - что такое «лабиринты» и откуда они появились. Хотя с лабиринтами встречаемся довольно часто: в рисунках ребенка, чертежах конструкторов, схемах работы городского транспорта можно заметить тот или иной вариант лабиринта. Так что же это такое «лабиринт»?
1.1 Лабиринты
Идя по жизни, мы понятия не имеем, где окажемся завтра. Мы стремимся к цели, но не знаем, как ее достичь. Плутаем, рискуя оказаться в тупике. Ломаем голову: какую дорогу выбрать? Символ нашей жизни - лабиринт. История лабиринтов длинна, сложна и запутанна. Как и жизнь человека.
(Автор неизвестен)
Слово «Лабиринт» произошло от греческого и означает ходы в подземельях.
Другой источник утверждает: «Лабиринт - храм
Зевса Лабрандского на Крите, т.е. Labrynthios, поскольку основным символом и
атрибутом этого Зевса является топор (по греч. - labrys). Среди рисунков во
многих помещениях дворца часто встречаются изображения двустороннего топорика.
Это символический знак, связанный с религиозным культом критских жителей. Такие
же топорики были найдены среди сталактитов и сталагмитов в одной из пещер, где,
по преданию, родился Зевс. Двойная секира с острием по-гречески называется
"лабрис". Ученые предполагают, что именно отсюда происходит слово
"лабиринт", которым первоначально называли "дом двойного
топора" - дворец царя Миноса.»
Действительно, существует очень много природных
подземных пещер с таким огромным количеством перекрещивающихся коридоров,
закоулков и тупиков, что нетрудно в них заблудиться и потеряться.
Примеры такого же рода, но уже искусственных лабиринтов, могут представить шахты иных рудников, или так называемые «катакомбы».
Возникшее на заре истории простое изображение лабиринта с петляющими дорожками было знакомо многим культурам. Лабиринт интернационален. Неизвестно, какой народ придумал его первым. Где бы ни жил человек, в Перу или Швеции, в Англии или России, он представляет один образ: путаные дорожки, ложные ходы и тупики, долгожданный выход, который не найти без помощи Ариадны. Примитивные формы лабиринта нередко выкладывались из камней или прорезались в торфе, и эта традиция жива и поныне.
И у древних писателей мы встречаем
указание на существование искусственных лабиринтов, например, у египтян. В
конце концов, словом «лабиринт» чаще всего обозначали именно искусственное
сооружение, составленное из большого числа аллей или галерей, бесчисленные
разветвления, перекрестки и тупики, которые заставляли попавшего туда
бесконечно блуждать в тщетных поисках выхода. Об устройстве таких лабиринтов
слагались целые легенды.
Известнее всего легенда о
лабиринте, построенном мастером Дедалом на острове Крит для мифического же царя
Миноса. В этом лабиринте обитало грозное чудовище с головой быка и туловищем
человека: Минотавр.
Лабиринты бывают самой разнообразной формы и устройства. До наших дней сохранились еще и галереи, и ходы пещер, и архитектурные лабиринты над могилами, и извилистые планы на стенах и полах, обозначенные цветным мрамором или черепицей, и извивающиеся тропинки на почве, и рельефные рисунки на скалах.
Рисунками лабиринтов украшались одеяния христианских императоров до девятого столетия, и остатки таких же украшений до сих пор на стенах церквей и соборов того времени.
Во Франции того времени лабиринты выкладывались из камня или изображались на полу церквей и соборов. Они назывались большей частью «путь в Иерусалим» и служили символом трудного земного путешествия в «святые места».
В городе Помпеи, погибшем в результате извержения Везувия в 79 году н. э., находилось, по крайней мере, два декоративных лабиринта.
В итальянском городе Клузоне был построен очень запутанный лабиринт в гробнице этрусского царя Порсены.
В Англии не встречаются лабиринты на церковном полу, но зато было очень много лабиринтов, сделанных из дерна на лужайках. О таких лабиринтах упоминает в своих пьесах Шекспир («Сон в летнюю ночь»; «Буря»).
Приведенная историческая справка показывает, насколько стар вопрос о лабиринтах. И вместе с тем он был актуален для многих в свое время.[2;6]
|
|
|
||||
|
||||
|
Родоначальником теории графов принято считать
математика Леонарда Эйлера (1707-1783). Историю возникновения этой теории можно
проследить по переписке великого ученого. Вот перевод латинского текста,
который взят из письма Эйлера к итальянскому математику и инженеру Маринони,
отправленного из Петербурга 13 марта 1736 года :
C B А D
"Некогда мне была предложена
задача об острове, расположенном в городе Кенигсберге и окруженном рекой, через
которую перекинуто семь мостов. Спрашивается, может ли кто-нибудь непрерывно
обойти их, проходя только однажды через каждый мост. И тут же мне было
сообщено, что никто еще до сих пор не мог это проделать, но никто и не доказал,
что это невозможно. Вопрос этот, хотя и банальный, показался мне, однако,
достойным внимания тем, что для его решения недостаточны ни геометрия, ни алгебра,
ни комбинаторное искусство... После долгих размышлений я нашел легкое правило,
основанное на вполне убедительном доказательстве, с помощью которого можно во
всех задачах такого рода тотчас же определить, может ли быть совершен такой
обход через какое угодно число и как угодно расположенных мостов или не может.
Кенигсбергские же мосты расположены так, что их можно представить на следующем
рисунке, на котором A и D обозначают острова, а B и C - части
континента, отделенные друг от друга рукавами реки. Семь мостов обозначены
буквами a, b, c, d, e, f, g».
По поводу обнаруженного им способа решать задачи подобного рода Эйлер писал:
"Это решение по своему характеру, по-видимому, имеет мало отношения к математике, и мне непонятно, почему следует скорее от математика ожидать этого решения, нежели от какого-нибудь другого человека, ибо это решение подкрепляется одним только рассуждением, и нет необходимости привлекать для нахождения этого решения какие-либо законы, свойственные математике. Итак, я не знаю, каким образом получается, что вопросы, имеющие совсем мало отношения к математике, скорее разрешается математиками, чем другими".
Так можно ли обойти Кенигсбергские мосты, проходя только один раз через каждый из этих мостов? Чтобы найти ответ, продолжим письмо Эйлера к Маринони:
"Вопрос состоит в том, чтобы определить, можно ли обойти все эти семь мостов, проходя через каждый только однажды, или нельзя. Мое правило приводит к следующему решению этого вопроса. Прежде всего, нужно смотреть, сколько есть участков, разделенных водой, - таких, у которых нет другого перехода с одного на другой, кроме как через мост. В данном примере таких участков четыре - A, B, C, D. Далее нужно различать, является ли число мостов, ведущих к этим отдельным участкам, четным или нечетным. Так, в нашем случае к участку A ведут пять мостов, а к остальным - по три моста, т. е. Число мостов, ведущих к отдельным участкам, нечетно, а этого одного уже достаточно для решения задачи. Когда это определено, применяем следующее правило: если бы число мостов, ведущих к каждому отдельному участку, было четным, то тогда обход, о котором идет речь, был бы возможен, и в то же время можно было бы начать этот обход с любого участка. Если же из этих чисел два были бы нечетные, ибо только одно быть нечетным не может, то и тогда мог бы совершиться переход, как это предписано, но только начало обхода непременно должно быть взято от одного из тех двух участков, к которым ведет нечетное число мостов. Если бы, наконец, было больше двух участков, к которым ведет нечетное число мостов, то тогда такое движение вообще невозможно... если можно было привести здесь другие, более серьезные задачи, этот метод мог бы принести еще большую пользу и им не следовало бы пренебрегать".
Обоснование вышеприведенного правила можно найти в письме Л. Эйлера к своему другу Элеру от 3 апреля того же года. Мы перескажем ниже отрывок из этого письма.
Математик писал, что переход возможен, если на участке разветвления реки имеется не более двух областей, в которые ведет нечетное число мостов. Для того, чтобы проще представить себе это, будем стирать на рисунке уже пройденные мосты. Легко проверить, что если мы начнем двигаться в соответствии с правилами Эйлера, пересечем один мост и сотрем его, то на рисунке будет изображен участок, где опять имеется не более двух областей, в которые ведет нечетное число мостов, а при наличии областей с нечетным числом мостов мы будем располагаться в одной из них. Продолжая двигаться так далее, пройдем через все мосты по одному разу. Открытия Эйлера, которые благодаря его оживленной переписке нередко становились известными задолго до издания, делают его имя все более широко известным. Улучшается его положение в Академии наук в 1727 году он начал работу в звании адъюнкта, то есть младшего по рангу академика, а в 1731 году он стал профессором физики, т. е. действительным членом Академии. В 1733 году получил кафедру высшей математики, которую до него занимал Д Бернулли, возвратившийся в этом году в Базель. Рост авторитета Эйлера нашел своеобразное отражение в письмах к нему его учителя Иоганна Бернулли. В 1728 году Бернулли обращается к «ученейшему и даровитейшему юному мужу Леонарду Эйлеру», в 1737 году — к «знаменитейшему и остроумнейшему математику», а в 1745 году — к «несравненному Леонарду Эйлеру — главе математиков».
А еще:
В 1892 г. М. Тремо изобрел алгоритм прохождения лабиринта. Спустя почти сто лет, алгоритм заново открыт Дж. Хопкрофтом и Тарьяном в контексте теории графов, которая, в действительности очень похожа на теорию лабиринтов.
Люк Тремо предлагал следующее
решение задач о лабиринтах. Выйдя из любой точки лабиринта, надо сделать
отметку на его стене (крест) и двигаться в произвольном направлении до тупика
или перекрестка; в первом случае вернуться назад, поставить второй крест,
свидетельствующий, что путь пройден дважды - туда и назад, и идти в
направлении, не пройденном ни разу, или пройденном один раз; во втором - идти
по произвольному направлению, отмечая каждый перекресток на входе и на выходе
одним крестом; если на перекресте один крест уже имеется, то следует идти новым
путем, если нет - то пройденным путем, отметив его вторым крестом.
Оказалось, что катакомбы, известные нам по многим детским фильмам, - есть разновидность лабиринтов.
Катакомбы Ленинградской области можно разделить на 4 типа:
1. Бывшие разработки кварцевого песка (Саблино, Старая Ладога, Борщево).
2. Бывшие разработки известняки и камня. (Телези, Аропаккузи, Кипень).
3. Подземные ходы специального назначения. (Румболовская гора и гора Парнас).
4. Карстовые и псевдокарстовые полости. (Жихарево и частично Рождествено).
Катакомбы первого типа сохранились ныне в наиболее сохранившемся виде. Причины этого две: первая - относительно недавнее происхождение большей их части; вторая - местами они велись в очень сильно сцементированном песчанике, практически не подверженному разрушению. Именно поэтому они преобладают в Ленинградской области (как по количеству, так и по размерам). В общем случае, они наименее опасны.
Катакомбы второго типа сохранились очень плохо: все дело в том, что известняки Ижорской возвышенности сложены из относительно мелких и тонких глыб и поэтому сильно подвержены разрушению.
Катакомбы третьего типа также находятся ныне в очень плохом состоянии - они рылись в основном в мягких породах, которые, конечно, позволяют делать очень быструю проходку, но с другой стороны очень неустойчивы. Первое их свойство и позволило наблюдать их ныне - в основном, они «собираются» по кускам с помощью выкапывания новых ходов. Пещер четвертого типа в Ленинградской области крайне мало и они все своеобразны. Карьеры искусственного происхождения подвержены гравитационному росту: частицы с потолка оседают на пол, из-за чего полость «всплывает». Чем больше пещера подвержена гравитационному росту, тем большая ее часть обвалена или отрезана. Большинство катакомб были «открыты» совсем недавно - в 80-е годы, на волне исследования искусственных подземных полостей Ленинградской области. Практически все катакомбы имеют перспективные
 |
Общая характеристика Саблинских катакомб.
Саблинские катакомбы были созданы в связи с добычей белого кварцевого песчаника в период с конца восемнадцатого до начала двадцатого веков. Чтобы понять геологию пещер, надо познакомиться с породами, создающими «слоеный пирог» в высоких берегах каньона Тосны. В этом районе это удобно сделать на Пляжнике - обрыве на правом берегу Тосны, напротив автобусной остановки.
На высоте примерно метра над уровнем Тосны лежит локальный водоупор - слой глины, с этого уровня бьют ключи. Выше лежат песчаники силурийского времени: серовато-синие, с большим содержанием глинистых частиц, его мощность около метра; далее расположен белый кварцевый песчанник - промышленный горизонт, местное полезное ископаемое, используемое в стокольной промышленности. Мощность его различна - от 4 м в Береговой, до 1 м. Залегает он не везде ровно - порой образует линзы - утолщения, или наоборот, исчезает, изгибается в складки. Еще выше цвет песчаника становится кремовым или розовым, и чем выше, тем больше густота красного цвета. Верхние слои уже темно-малиновые, их мощность может достигать 10 и более метров, они не пригодны для производства стекла. Над песчаниками идет бронировка - слой ордовикских известняков, в виде плит, которую пещерники называют плитняком, а каменотесы - бут. Толщина одной плиты обычно 10-15 см, а мощность всего слоя около полуметра. Выше бута еще встречаются слабосцементированные пески и песчаники. Сверху залегает несколько метров моренных четвертичных пород - как говорят пещерники, «зеркало травы».
Как уже говорилось, катакомбы
прорубались в белом кварцевом песчанике, однако вследствие процесса
гравитационного роста современные пещеры в большинстве идут в малиновых
песчаниках, реже в буте. Местами есть провалы с выходом четвертичных пород и
водотоками - «гумоз». Наиболее опасны для посещения ходы, выросшие до бута,
особенно в тех местах, где бут уже начал обрушаться. В пещерах (Жемчужной,
меньше в Береговой) встречаются проходимые бутовые завалы («мясорубки»), однако
соваться в них без специальной подготовки, а тем более разбирать такие завалы
не рекомендуется.
Катакомба Трехглазка.
Катакомба Трехглазка («Ленинский Тупик») расположена на левом берегу Тосны, чуть ниже по течению автомобильного моста. Она хорошо видна с кладбища в Никольском - песчаный обрыв с тремя входами. Для входа в нее следует спуститься на нижнюю террасу поймы Тосны и немного пройти по ней к рыжему песчаному выносу, ведущему к входу в пещеру. Входить лучше всего через центральный вход.
Общая длина ходов пещеры - 260 м, из них 220 м - основной ход. Высота потолков практически на всем протяжении около 150 см, у входа - около 100 см. В конце основ-ного хода имеется вырубка в потолке - старая штольня. Мест вероятного продолжения системы не найдено, так как пещера была «пробной» выработкой в поисках жилы белого песчаника, которую здесь так и не нашли.
Катакомба Береговая.
Катакомба Береговая (Янтарная, Помойка) расположена на левом берегу реки Тосна, немного выше по течению автомобильного моста. Имеет три входа, которые легко найти при движении по дороге с автобусной остановки в сторону моста. Главный вход (Воронка) выходит прямо в обрыв берега реки. Спуск к нему начинается от земляного бугра (в народе - «Пьяной горки»), расположенной почти у самого моста. Подойдя около нее к обрыву, можно увидеть поросшую мелколесьем воронку в склоне. Правее нее есть металлическая лестница, по которой подходят ко входу. Спуститься можно еще по тропе левее воронки. На входе в пещеру стоит металлическая дверь. Ниже воронки из пещеры вытекает ручей. Второй вход в пещеру (Решетка) расположен несколько выше по течению (правее, если смотреть от дороги), примерно в 100 м. Ориентиром служит бетонный столб ЛЭП в центральной части площадки для разворота автомобилей. Несколько левее его вниз по склону спускается желоб, по которому нужно спуститься на небольшую террасу. Здесь расположен металлический люк, через которой по металличес-кой лестнице можно спуститься в пещеру. Третий вход (Трупы) расположен на левой стороне автодороги. Около начала спуска к мосту следует свернуть на поле влево и выйти на поле, где искать овраг. В овраге течет ручей, по которому и следует войти через провал в пещеру. Из входов третий наименее комфортен.
Катакомба Береговая на настоящий момент, в связи с падением уровня озера и исследованием заозерной части, является самой протяженной в Саблино. Общая длина ее ходов превышает 7000 м (привходовой части - 3500 м). Высота потолков в привходовой части 160-180 см, с залами выше 500 см, в заозерной части колеблется в пределах от 50 до 350 см.
Топография пещеры довольно сложная. Она делится на привходовую часть, разделенную линией обвалов («Перевал Аврора») на две части - со входом «Решетка» и с Главным входом, заозерную часть, о составе которой речь пойдет ниже, и собственно главное озеро.
Привходовая часть со входом «Решетка» представляет собой разветвленный лабиринт («колонник»), ограниченный с одной стороны берегом реки Тосна, а с других - линиями завалов. Есть несколько перспективных мест для исследования. Основные достопримеча-тельные места этой части пещеры - вход «Решетка», Большой Банкетный зал, зал Гнома, «перевал Аврора».
Привходовая часть у Главного входа также представляет собой колонный лабиринт, однако ориентирование в нем проще. От Главного входа в глубь пещеры, пересекая озеро, уходит длинный прямой штрек («Бродвей»)- основной ход выработок. Первая его часть сухая, далее на него выходит ручей, до этого бывший правее по ходу, образующий не очень глубокую лужу, проходимую по камням вдоль левой стенки. Ручей вытекает из входа «Трупы», до которого от лужи около 20 м хода по Бродвею. За «Трупами» на Бродвее видно старое русло ручья, и наконец Бродвей утыкается в озеро. В левой части этого района (левее от входа Бродвея и ручья) следует отметить могилу Белого у самого входа на «Аврору», а в правой - грандиозный Горный зал.
Два района привходовой части пещеры Береговая соединяются через «перевал Аврора», линию завалов, на которой существует постоянная опасность дальнейших обрушений. Ходить здесь следует предельно осторожно, так как в последние годы ситуация здесь очень нестабильная. «Аврора» имеет 3 прохода. Левый очень опасный, центральный - наиболее высокий и наименее опасный, здесь в глине видна тропа, правый (здесь когда-то была стоянка «Аврора») имеет 2 очень узких места. В правом и левом проходах есть водяные капели.
Проход в Заозерную часть возможен двумя способами: по озеру или через «Кошачий лаз». Первый способ годен для прохождения в резиновых сапогах только при низком уровне озера (в дальнейшем - Второго озера). В продолжении Бродвея от старой деревянной крепи по дну озера проложены камни. Пройдя по ним и за озером через низкий проход, выходим в зал «Два туриста» в районе «поста ГАИ». «Кошачий лаз» - это следующий за входом «Трупы» ход влево от «Бродвея». Сначала ход довольно высок, однако вскоре начинается узкий 6-метровый лаз. Заканчивается от высоким залом с капелью.
Заозерная часть ныне делится на старую заозерную часть и «Остров» (за Вторым озером). Старая заозерная часть делится на район «поста ГАИ», Екатерининский лабиринт и «Круга».
Район поста ГАИ - наиболее разрушенный в пещере. Основные его ходы проходят в бутовых плитах и довольно опасны. На «посту ГАИ» стоит соответствующий дорожный знак и лежит журнал. Влево (если стоять лицом к знаку) уходит самый опасный ход в пещере - проблемник «Здравствуй и прощай». Правее (по ходу) района «поста ГАИ» рас-положены «Восьмерка» и «Круга». Ориентирование здесь относительно сложное.
Если идти от «поста ГАИ» прямо (по левой руке), то можно выйти ко Второму озеру. По его левому краю есть проход на «Остров». Это наименее исследованная часть пещеры. Совсем недавно здесь был обнаружены выходы к Третьему и Четвертому озерам пещеры.
Катакомба Жемчужная.
Катакомба Жемчужная расположена на правом берегу Тосны, выше по течению авто-мобильного моста. Если стоять на «Пьяной горке» левого берега Тосны, примерно напротив хорошо видны два входа в пещеру - нижний («Обсерватория»), более заметный, и Корни (выше и правее). Зимой ко входу можно идти прямо по льду Тосны, тогда удобнее входить через «Обсерваторию», а летом нужно перейти реку по мосту и по тропе выше обрыва берега выйти к прямо к входу «Корни». Есть еще третий провал (через обрушившийся взрывом потолок зала) в 5 м дальше по тропе от «Корней», но здесь по очевидным соображениям входить не рекомендуется. «Корни» и «Обсерватория» соединяются тропой (10 м).
Катакомба Жемчужная - вторая по протяженности в Саблино. Общая длина ее ходов составляет 5500 м. Высота ходов меняется в широких пределах. Пещера имеет весьма интересную и своеобразную топологию.
Все входы в пещеры ведут в привходовой лабиринт. Это небольшой по размерам колонник с высотой потолков около 160 см, имеющий два выхода. Первый - «Транструба», расположенный около провала в потолке зала, ранее соединял Жемчужную со Штанами, теперь он завален. Второй, расположенный в дальней части колонника, ведет далее в систему. Это низкий ход, преодолеваемый ползком.
Далее начинается довольно продолжительный ход (влево) выводящий к развилке. Влево расположен «Школьный» лабиринт с могилой, вправо ходы в зал «Для Курения» (МДК) и далее в систему. В этот зал можно попасть по грязному низкому ходу если идти от входа в эту часть пещеры вправо. Школьный лабиринт является весьма самостоятельной частью пещеры. Высота потолков здесь от 100 до 180 см. Около могилы раньше был самостоятельный выход наружу («Негретянка»), однако сейчас это только окно - здесь теперь не пролезет и ребенок.
За МДК, в котором лежит журнал, начинается «Метро». Это небольшой колонник с высотой потолков около 100-120 см, однозначно выводящий через один из трех узких низких ходов в зал «Русалка». Здесь разветвляются пути в дальнюю часть пещеры.
Влево от «Русалки» уходит «Гулкач» - узкий и низкий 12-метровый ход, ведущий в дальнюю часть пещеры. Прямо через 2 хода можно выйти в «Колонный» зал - значи-тельный по размерам запутанный лабиринт. Из него выходят ходы в дальние части пещеры.
Катакомба Санта-Мария.
Катакомба Санта-Мария расположена на правом берегу Тосны, выше по течению Жемчужной. Если идти тропой выше каньона, то, перейдя овраг, слева оказывается небольшой песчаный грот. В нем есть узкий и низкий ход, ведущий в пещеру.
Общая протяженность ходов катакомбы
Санта-Мария составляет 40 м. Высота потолков около 180
см в залах и 60 см в ходе. Катакомба, очевидно, была ранее частью большой
катакомбы, включающей Жемчужную, Штаны и, возможно, другие. Здесь есть
перспективные для прохождения завалы - в дальнем зале и у самого входа.
2. Исследование поиска выхода из лабиринта
2.1 Теорема Тремо
Универсальный алгоритм прохождения любых лабиринтов был описан только через столетие в книге французского математика Э. Люка "Recreations matematiques", изданной в 1882 году. Интересно, что Люка при описании алгоритма указал на первенство другого французского математика М. Тремо. Таким образом, алгоритм стал известен как алгоритм Люка-Тремо.
Тремо предлагает следующие правила: выйдя из любой точки лабиринта, надо сделать отметку на его стене (крест) и двигаться в произвольном направлении до тупика или перекрестка; в первом случае вернуться назад, поставить второй крест, свидетельствующий, что путь пройден дважды - туда и назад, и идти в направлении, не пройденном ни разу, или пройденном один раз; во втором - идти по произвольному направлению, отмечая каждый перекресток на входе и на выходе одним крестом; если на перекресте один крест уже имеется, то следует идти новым путем, если нет - то пройденным путем, отметив его вторым крестом.
Зная алгоритм Тремо, можно скорректировать поведение легендарного Тесея. Вдохновленный подарком любимой Ариадны, он уверенно идет по лабиринту. Вдруг перед ним возникает ход, по которому уже протянута нить... Что делать? Ни в коем случае не пересекать ее, а вернуться по уже известному пути, сдваивая нить, пока не найдется еще один непройденный ход.
Применив вариант алгоритма Тремо, отец теории информации Клод Шеннон (Claude Elwood Shannon) построил одного из первых самообучающихся роботов. Шеннон дал ему звучное имя "Тесей", но в истории "Тесей" стал больше известен как "мышь" Шеннона. "Мышь" сначала обследовала весь лабиринт, а затем (во второй раз) проходила весь путь значительно быстрее, избегая участков, пройденных дважды.
Тремо предлагает примерно такой вариант решения задач о лабиринтах. Всякий раз, идя по любому коридору в первый раз, ставим при входе в коридор и при выходе из коридора на стене по черточке, если идем по коридору вторично, то перечеркиваем черточки. Если мы имеем дело с действительным лабиринтом, или галереями подземных шахт, с разветвлениями пещер и т. д., то блуждающему в этих шахтах вместо черточек на бумаге придется делать уже иной знак, чтобы ориентироваться, и класть, например, камень при входе и выходе из каждого перекрестка – в галерее, которую он покидает, и в той, в которую он входит. [4]
1.
Если подошли к перекрестку, на котором ни разу небыли, то дальше идем по любому
коридору (рис. 1), если же попали в тупик – идем обратно (рис. 2).
2.
Если подошли к перекрестку, где уже побывали, и подошли к нему по такой дороге,
по которой мы идем в первый раз, то немедленно отправляемся обратно (рис. 3).
3.
Если подошли к перекрестку таким путем, по которому уже дважды шли, то далее,
если есть коридоры, по которым ещё не разу не ходили, идем по любому из них
(рис. 4).
Если же таких коридоров нет, то идем по любому пройденному один раз (рис. 5).
перекресток
2.2 Правила правой и левой руки
Одним из самых простых правил для прохождения лабиринта является правило "одной руки": двигаясь по лабиринту, надо все время касаться правой или левой рукой его стены. Этот алгоритм, вероятно, был известен еще древним грекам. Придется пройти долгий путь, заходя во все тупики, но в итоге цель будет достигнута. Хотя у этого правила и есть один недостаток, но о нем мы поговорим позже.
Попробуем описать робота, действующего в соответствии с правилом "правой руки".
В начале своей работы робот должен найти стену, по которой он будет следовать. Для этого он может просто двигаться вперед, пока не упрется в преграду.
После того как робот наткнулся на препятствие, он начинает передвигаться в соответствии с правилом "правой руки".
Двигаясь вдоль стены, робот
следит, есть ли проход справа. Если проход есть, робот должен идти по нему, чтобы
не оторваться от стены справа.
Если прохода нет - впереди стена - робот поворачивает налево. Если прохода снова нет, он еще раз поворачивает налево, таким образом разворачиваясь на 180 градусов, и идет в обратном направлении.
Блок-схема алгоритма для робота, работающего по правилу "правой руки", представлена на рисунке.
Робот, решая задачу о лабиринте, робот прошел следующие шаги алгоритма:
переменная флаг
фон = maze1.gif
поднять перо
место 115, 545
' поиск первой стены
повторять пока датчик > 50 {
вперед 12
}
' правило правой руки
повторять пока флаг = 0 {
направо 90
вперед 12
если датчик = 0 то
флаг = 1
иначе
если датчик < 50 то
назад 12
налево 90
вперед 12
если датчик < 50 то
назад 12
налево 90
конец условия
конец условия
конец условия
}
пиши "цель достигнута"
Если известно, что у лабиринта
нет отдельно стоящих стенок, то есть нет замкнутых маршрутов, по которым можно
возвращаться в исходную точку, то такой лабиринт называют односвязным и его
всегда можно обойти полностью, применив правило "одной руки".
Если же лабиринт содержит отдельно стоящие стенки, то, применяя правило "одной руки", не всегда можно пройти все коридоры и тупики. Лабиринты с отдельно стоящими стенками и с замкнутыми маршрутами называются многосвязными. При этом многосвязные лабиринты можно разделить на две группы: без "петли" вокруг цели (замкнутый маршрут не проходит вокруг цели) и с замкнутой "петлей" вокруг цели (цель можно обойти по замкнутому маршруту).
В многосвязных лабиринтах второй группы правило "одной руки" не работает и, применяя его, достичь цели невозможно. Но и эти лабиринты можно пройти, полагаясь на точный алгоритм.
Решение задачи о таких
лабиринтах принадлежит сравнительно позднему времени, и начало ему положено
Леонардом Эйлером. Эйлер не без оснований полагал, что выход из любого
лабиринта может быть найден, и притом сравнительно простым путем.
3. Теория графов
3.1 Основные положения теории графов
В данной главе будут описаны основные теоремы и определения теории графов.
Итак, граф представляет собой непустое множество точек и множество отрезков, оба конца которых принадлежат заданному множеству точек. Данные точки называются вершинами графа, отрезки – ребрами графа. Граф будем обозначать Г. (приложение 1)
Вершина, не принадлежащая ни одному отрезку называется изолированной.
Степенью вершины называется число ребер графа, которым принадлежит эта вершина. Вершина называется четной, если её степень число четное. Вершина называется нечетной, если её степень – число нечетное.
Теорема (о сумме степеней вершин графа)
В графе Г сумма степеней всех его вершин – число четное, равное удвоенному числу ребер графа.
,
где p
– число ребер графа Г, n – число его вершин.
Теорема (о вершинах с одинаковыми степенями)
Во всяком графе с n
вершинами , где 
, всегда найдутся по меньшей мере две вершины с одинаковыми
степенями.
Каждая вершина графа с n вершинами может иметь степень, равную 0,1,2,3,4,…,n-1. Предположим, что существует граф Г, все вершины которого имеют разную степень, т. е. каждое из чисел последовательности 0,1,2,3,…, n-1 является степенью одной и только одной из его вершин. Но этого не может быть. Действительно, если в графе Г есть вершина A со степенью 0, то в нем не найдется такая вершина B со степенью n-1, так как эта вершина B должна соединятся со всеми остальными вершинами графа, в том числе и с A. Следовательно, найдутся хотя бы две вершины, степени которых одинаковы.
Путем в графе от A1 до Аn называется такая последовательность ребер, ведущая от А1 до Аn, в которой каждые два соседних ребра имеют общую вершину и никакое ребро не встречается более одного раза.
Путь от A1 до Аn называется простым, если он не проходит ни через одну из вершин графа более одного раза.
Циклом называется путь, в котором совпадают его начальная и конечная вершины.
Две вершины А и В графа называются связными, если в графе существует путь с концами А и В.Граф называется связным, если каждые две вершины его связные.
Гамильтоновым называется цикл, проходящий по каждой вершине графа ровно один раз.
Связный граф является эйлеровым тогда и только тогда, когда степени всех его вершин – чётные числа.
Теорема ( о цикличном маршруте в графе )
Если граф Г связный, то можно построить цикличный маршрут,
содержащий все ребра графа в точности два раза, по одному в каждом направлении.
E D В
Доказательство:
Дадим общее правило построения такого пути, предложенное Тарри.
С А
Из произвольной вершины A пройдем вдоль какого-нибудь ребра (А,В),
отметив его стрелкой, указывающей направление пути. Из В пройдем к третей
вершине, снова отметив стрелкой направление прибытия, и т. д.. Ребро, по
которому впервые прибываем к вершине, будем отмечать
3.2 Лабиринт как геометрическая сеть
Аллеи, дорожки, коридоры, галереи, шахты и т. п.. Лабиринты тянутся, изгибаясь во все стороны, перекрещиваются, расходятся по всевозможным направлениям, ответвляются, образуют тупики и т. п.. Но мы для большей ясности рассмотрения вопроса все перекрестки обозначим просто точками, а все эти аллеи, коридоры и т. д. будем принимать просто за линии, прямые или кривые, плоские или нет – все равно, но эти линии соединяют наши точки (перекрестки).
Эти точки и линии составляют геометрическую сеть, или лабиринт, если какая-либо точка, движущаяся по линиям этой сети, может пройти к любой другой точке, не покидая линий нашей системы (или сети).
Оказалось, что подобная движущаяся точка (представляющая, например человека) может последовательно описать все линии сети без всяких скачков и перерывов при этом по каждой линии сети она пройдет ровно два раза. При этом она конечно же пройдет через точку, обозначающую выход из лабиринта.
Возможность обхода следует, вообще говоря, из того, что фигуру, полученную из сети удвоением всех линий, можно описать одним росчерком. Можно доставить себе довольно интересное математическое развлечение.[3]
На листе белой бумаги взять произвольно несколько точек и соедините их по две столько раз, сколько захотите, произвольным числом прямых или кривых линий, но так, чтобы ни одна точка системы не осталась совершенно изолированной. Итак, получим геометрическую сеть. Например сеть трамваев или троллейбусов нашего города, сеть московского метро, сеть железных дорог страны, сеть рек и каналов и т. д..
 |
Карта Удмуртии Схема движения
городского транспорта г. Ижевска
3.3 Теория графов на применение к задачам о лабиринтах
Существует три алгоритма нахождения выхода из лабиринта с помощью теории графов.
Алгоритм прохождения лабиринтов называется поиском в глубину. Алгоритм поиска в глубину особенно удобен для задач с лабиринтами, поскольку его можно применять, не имея карты лабиринта. Достаточно лишь следовать локальным правилам в узлах и запоминать узлы и ребра, которые уже были пройдены. Даже если вы заблудились в лабиринте, алгоритм поможет вам найти выход.
1. Начать с произвольно выбранного узла;
2. Посетить любой соседний узел, который еще не посещался;
3. Повторять шаг 2, пока это возможно;
5. Вычеркнуть любое ребро, по которому произошел возврат;
3. Повторять шаги 1 и 2, пока это возможно.
5. Впредь игнорировать все переходы, по которым был совершен возврат.
Теория графов предлагает элегантный способ исследования
лабиринта, в котором надо найти минимальный маршрут. Начать следует с
составления матрицы соединений между соседними узлами. Сеть лабиринта,
изображенная рисунке ниже, имеет восемь узлов.
Рис. 3 перекресток Рис. 1
4. Примеры задач на лабиринты
Рассмотрим два простейших правила решения задач с лабиринтами, все стены которого имеют вид одной, нигде не пересекающей себя замкнутой линии (вход закрыт воротами). Отметим две точки на плане лабиринта.
1. Если обе точки находятся либо внутри, либо снаружи лабиринта, то любая соединяющая их линия пересечет границу лабиринта четное число раз.
2.
Если одна точка находится
снаружи лабиринта, а другие внутри, то любая соединяющая их линия пересечет
границу лабиринта такого вида нечетное число раз.
Например, отметим точку А внутри
лабиринта и точку B снаружи
лабиринта. Соединим эти точки линией. Она пересекает границу лабиринта пять
раз, то есть нечетное количество раз.
Задача №1
На цирковой арене.
На цирковой арене выступал канатоходец. На высоте трех метров от земли на пяти столбах был натянуты канаты, по которым он должен был проходить. Канаты были натянуты так, как это показано на рисунке 1.
Канатоходец должен был пройти по восьми канатам таким образом, чтобы по каждому из них пройти всего один раз. И это ему всегда удавалось, хотя он и не возвращался в то же место, откуда выходил. Но во время одного из выступлений оборвался канат №8, и осталось всего семь канатов (рис.2).
Может ли теперь канатоходец пройти все канаты, проходя по каждому из них всего раз? Покажите, как ходил канатоходец, когда все канаты были целы, и ответьте на поставленный вопрос.
Решение:
Когда все канаты были целы, канатоходец, выходя из точки А, заканчивал свой путь в точке В (рис.3). После того, как оборвался канат №8, канатоходец не сможет обойти все канаты по одному разу.
Задача №2
Тропинки в садах.
В саду Александра Ивановича тропинки
проложены, как это показано на рис. 4, а у Бориса Борисовича- как показано на
рис. 5. Кто из них может обойти все тропинки, проходя по каждой всего один раз?
Ответ: Александр Иванович.
Задача №3
Среди георгин.
Садовник имел квадратную клумбу 4*4 метра, на
которой он вырастил 16 кустов георгин. Расстояние между кустами было 1
метр. Пока кусты еще не расцвели, цветовод обходил все кусты, идя по
кратчайшему пути, но когда чудесные цветы распустились, садовник обходил их по
самому длинному пути. К каждому цветку он подходил всего один раз. Как выглядел
самый короткий путь от куста к кусту, а как самый длинный?
Решение:
1. Самый кратчайший путь:
1;2;3;4;8;7;6;5;9;10;11;12;16;15;14;13 (рис.6)
2. Самый длинный путь:
5;9;13;10;7;4;3;2;1;6;11;16;12;8;15;14 (рис.7)
Задача №4
Задача садовника.
Садовнику поручили высадить 10 деревьев на
площадке в форме равностороннего треугольника. Садовник имел два сорта
деревьев: 10 акаций и 10 лип. Чтобы придать некоторое разнообразие саду, он
решил несколько акаций и несколько лип, причем так, чтобы на каждой стороне
каждого из четырех равносторонних треугольников, которые при этом образовались,
росло не больше двух деревьев того же сорта. Как он это сделал?
Решение:
Садовник посадил 4 акации и 6 лип (рис.8).
Задача №5
Клад.
На рис.9 представлена схема лабиринта. Стороны
пяти квадратов, вписаны один в другой,- это коридоры, ведущие к наименьшему
внутреннему квадрату, где закрыт клад. Клад обладает таким свойством ,что
получить его может только тот, кто придет за ним и выйдет из лабиринта, пройдя
все коридоры по одному разу. Ни один коридор, даже частично, нельзя пройти
дважды. Попытайте счастья.
Решение:
Путь к кладу и обратно показан на рисунке 10.
Заключение.
Лабиринты – это странные явления природы или затейливые постройки человека, заставляют задумываться над поиском выхода из них.
Теория графов и ее применение к решению задач о лабиринтах довольно увлекательный материал, позволяющий на практике найти поиск выхода из тупика. Наверно, в моей работе оказался больше рассмотрен исторический материал, нежели математический. Но, пожалуй, эта та ситуация, которая позволяет продемонстрировать тесную связь математики не только с точными, но и гуманитарными дисциплинами. Конечно, очень жаль, что пока я пытаюсь найти поиск выхода из тупика только на бумаге с помощью карандаша (к сожалению, в Удмуртии нет настоящих лабиринтов), но хочется верить, что когда – нибудь у меня появится настоящая возможность проверить теорию выхода из тупика лабиринта на практике.
Использованная литература.
1. Лекции по теории графов. / Емеличев В.А., Мельников О.И. и др. М.: Наука, 1990.
2. Оре О. Теория графов. – М.: Наука, 1980.
3. Графы и их применение: Пособие для учителей. – М.: Просвещение, 1979.6 – 44 стр.
4. Комбинаторика и теория графов: Учебное пособие. – Носов Алексей Николаевич http://intsys/msu/ru
5. Наглядная геометрия, И. Ф.Шарыгин, Л. Н. Ерганжиева изд. Культурно – производительный центр «Марта» (Москва 1992 год)
6. В царстве смекалки, Е. И. Игнатьев, изд. «Наука» (Москва 1979 год)
7. Увлекательная математика, И. Леман, изд. «Знание», (Москва, 1985 год)
8. По следам Пифагора, Щ. Еленьский, изд. Детской литературы, (Москва, 1971 год)
9. Математика, занятия школьного кружка, О. Шейнина, изд. «НЦ ЭНАС», (Москва, 2003 год)
10. http://www.komok.ru/
|
|
|
Приложение
Рабочие листы
к вашим урокам
Скачать
6 663 820 материалов в базе
Настоящий материал опубликован пользователем Соломатина Юлия Владимировна. Инфоурок является информационным посредником и предоставляет пользователям возможность размещать на сайте методические материалы. Всю ответственность за опубликованные материалы, содержащиеся в них сведения, а также за соблюдение авторских прав несут пользователи, загрузившие материал на сайт
Если Вы считаете, что материал нарушает авторские права либо по каким-то другим причинам должен быть удален с сайта, Вы можете оставить жалобу на материал.
Удалить материал
Ваша скидка на курсы
40%
Курс повышения квалификации
36 ч. — 180 ч.
Курс профессиональной переподготовки
300 ч. — 1200 ч.
Курс повышения квалификации
36 ч. — 144 ч.
Мини-курс
4 ч.
Мини-курс
4 ч.
Оставьте свой комментарий
Авторизуйтесь, чтобы задавать вопросы.