Презентация, доклад по теме Лабиринты

из запутанных путей к выходу (и/или путей, ведущих в тупик).

Лабиринт  — топологическая фигура, в которой ищется путь между двумя точками.

XVIII династии египетских фараонов Аменемхет III (ок. 1456-1419 до н. э.) возвел пирамиду, заупокойный храм при которой был построен в виде лабиринта.

для того, чтобы поселить там Минотавра, человека-быка. Юный Тезей сразился с чудовищем Минотавром, и выбрался с помощью клубка, подаренным ему Ариадной, дочерью царя Миноса.

План лабиринта на Крите

Розамунды. Повторно она была построена в вудстокском парке в XII веке королем Генрихом II, который попытался спрятать в этом лабиринте возлюбленную Розамунду Прекрасную от свой супруги Элеоноры Аквитанской. Предание рассказывает, что нить Ариадны помогла Элеоноре проникнуть в центр лабиринта, где ослепленная ревностью королева заставила несчастную Розамунду принять яд.

Шартрского

святого Квентина

Сиенского

из живых изгородей, через который и по сей день пытаются отыскать путь сконфуженные туристы, был сооружен в 1690 году при дворце Вильгельма Оранского в Хэмптон-Корте.

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

заштриховать все тупики, тогда останутся только прямые пути к цели. Совсем иное дело, если нужно пробраться в лабиринт, плана которого нет…

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

касаясь стенки одной и той же рукой (все время правой или все время левой).

Задача. Простое прохождение лабиринта.
Нарисуйте прохождение лабиринта в Хэмптон-Корте, пользуясь простым алгоритмом.

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

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

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

ведя линию вдоль стенки, например, правой.

2. Дойдя до разветвления, выбираем любой новый путь.

3. Если, идя по новому пути (где нет линии вдоль левой стенки):
а) попадаем в тупик;
б) выходим на какой-нибудь перекресток, где уже были,— то поворачиваем обратно.

4. Если, идя по старому пути (где есть линия вдоль левой стенки),
выходим к перекрестку, то:
а) если есть новый путь, то выбираем его;
б) если нет нового пути, то идем по старому.

5. Никогда не пойдем по пути с отметками по обеим сторонам.
 

английский математик У.У. Роуз Болл. Цель указана точкой внутри лабиринта.

во внутренней области этой фигуры, проведем лучи x, y, u, v, z

Число точек пересечения любого из этих лучей с замкнутой кривой ι нечетно

заканчиваются в точке В, лежащей вне фигуры, ограниченной кривой ι.

Число точек пересечения одной из дуг АВ с кривой ι равно трём:
С1, С2 иС3

I. Если число точек пересечения дуг АВ с не самопересекающейся замкнутой кривой ι нечетно, то одна из точек А или В является для фигуры, ограниченной кривой ι, внешней, а другая - внутренней

точки с не самопересекающейся прямой ι четно.

ВНУТРЕННЯЯ ТОЧКА - если число точек пересечения луча, исходящего из данной точки с не самопересекающейся прямой ι нечетно.

F, либо пересекают (число пересечений четно)

Две точки А и В, лежащие во внешней области, соединены дугами, которые либо не пересекают фигуру F, либо пересекают ее (число пересечений четно)

II. Если число точек пересечения отрезка (или дуги) АВ с несамопересекающейся прямой ι четно, то точки А и В одновременно расположены или во внешней, или во внутренней области фигуры F

из данных точек можно соединить без пересечения контура лабиринта;
из какой (из данных) точки можно выйти без пересечения контура лабиринта.

точек, для этого проведем произвольные лучи с началом в данных точках и подсчитаем число точек пересечения этих лучей с контуром лабиринта.
Лучи а и с пересекают его нечетное число раз, а луч в – четное. Согласно свойству №1 – точки А и С находятся в одной области, а точки А и В, В и С – в разных областях лабиринта.
Только точки А и С можно соединить, не пересекая контур лабиринта

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

в точку В?

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





Точки А и В лежат в одной области (внутренней), значит задача имеет решение.

все комнаты так, чтобы через каждую дверь пройти только один раз.
В какой комнате закончится такой обход?

соединяющими эти точки.





Этот граф уникурсален, т.к. имеет только две нечетные вершины (20 и 23), значит его можно изобразить одним росчерком (свойство графа № 3).
Значит, если начать движение в комнате № 20, закончим его в комнате № 23.

него А и выход В.

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

Если есть, то найдите его.

поставленный палец окажется в петле при стягивании двух концов в одном направлении?

чтобы пройти через все двери этого здания только один раз?

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