# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: Python 2
#     language: python
#     name: python2
# ---

#  

# # Урок "Лабиринты"

# На этом уроке мы изучаем что такое лабиринты и обсуждаем историю, географию, греческие мифологию и язык, а также алгоритмические вопросы в прохождении лабиринтов.

# ---
#
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
#
# ![](figures/hampton.gif)
#
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
#
# **Hampton Court Palace Maze:**
# ![](figures/hampton-court.jpeg)
#
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
#
# ![](figures/hampton.gif)
# ![](figures/hampton-court.jpeg)
# ---
#
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
#

# ---
#
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
#
# ![](figures/minotaur.gif)
#
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
#
# ---

# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
#
# <NAME> с Минотавром. Иллюстрация из книги 1888 г. Минотавр - чудовище с телом человека и головой быка.
#
# <br>
# <br>
#
# ![](figures/TheseusundMinotaurosMKL1888.png)
#
# Минотавр (руский язык) - Μῑνώταυρος (греческий язык)
#
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>

# Сражение Тесея с Минотавром на древнегреческой вазе середины VI в. до н. э.
#
# <br>
#
#
# <img src="figures/1024px-Theseus_Castellani_Louvre_E850.jpg" alt="Drawing" style="width: 600px;"/>
#
# <br>
# <br>
#
# [Тесей, Минотавр и <NAME> (волшебный фонарь)](https://youtu.be/jXdJkQ6oF3Q?t=1236)
#
# <br>
# <br>
#
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>

# ---
#
# <img src="figures/maze.png" alt="Drawing" style="width: 400px;"/>
#
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
#
#
# <img src="figures/maze-with-nodes.png" alt="Drawing" style="width: 400px;"/>
#
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
#
#
# <img src="figures/maze-as-graph.png" alt="Drawing" style="width: 400px;"/>
#
# ---
#
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
#
#
# <img src="figures/tube.png" alt="Drawing" style="width: 800px;"/>
#
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
#
# <img src="figures/tube-large.png" alt="Drawing" style="width: 1200px;"/>
#
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>
# <br>

# ## Алгоритмы и правила исследования и прохождения лабиринтов

# Если вы входите в лабиринт, схему которого знаете, тогда преобразование схемы лабиринта в граф или сеть поможет вам быстро найти нужные пути в лабиринте. Это преобразование заключается в том, чтобы заменить маршруты между точками ветвления и тупиков прямыми линиями (как это мы делали наверху). 
#
# **Но что делать, если вы входите в лабиринт, не имея ни его схемы, ни средств для того, чтобы нарисовать её? Как вы должны поступать, проходя через узлы, если не хотите заблудиться?**

# ### Правило правой (левой) руки

# Один из методов состоит в том, чтобы в каждой узловой точке выбирать одно и то же направление. Например, можно всегда сворачивать на крайнюю правую ветвь. Если этот путь закончится тупиком, следует вернуться к узловой точке и выбрать следующую ветвь (если считать справа). Может оказаться, что в результате вы пройдете по каждой ветви дважды — по одному разу в каждом направлении, но в конце концов вы доберётесь до цели. На обратном пути можно либо продолжать выбирать крайние правые ветви в каждом узле (и в этом случае вы, вероятно, пройдёте по новым областям лабиринта), либо каждый раз сворачивать на крайнюю левую ветвь (и тогда вы в точности повторите первоначальный маршрут). Метод выбора одной и той же — правой или левой — ветви называется, соответственно, правилом правой или левой руки.
#
# Правило руки применимо только к, так называемым, односвязным лабиринтам. Этот термин означает, что лабиринт не содержит замкнутых маршрутов, т.е. таких, которые образуют замкнутую петлю. Замкнутый маршрут возникает в том случае, если существует ограниченный стенками «остров», который не соединяется с другими стенками лабиринта. Лабиринт с одним или более островами называется многосвязным. 

# *Пример:* Chevening House Maze<br><br>
# <img src="figures/CheveningHouseMaze.png" alt="Drawing" style="width: 1200px;"/>
#
# <br><br><br><br><br><br><br><br><br><br><br><br>
#
# <img src="figures/CheveningHouseMazeScheme.png" alt="Drawing" style="width: 1200px;"/>
# <br><br>
# Узлы пронумерованы от 1 (на входе) до 18 в точке-цели. Предположим, вы вошли в этот лабиринт, не имея схемы, и применяете правило правой руки, проходя через каждый узел. В этом случае вы пройдёте последовательно через узлы 1–2–3–4–14–13–9–11–8–10–2–1, не достигнув цели!
#
# <br><br><br><br>
# <img src="figures/CheveningHouseMazeRightArmBreaks.png" alt="Drawing" style="width: 1200px;"/>
#

# # Упражнения

# 1 http://www.mazes.ws/

# 2 ***Нарисуйте лабиринт для своего друга. Постарайтесь создать сложный (как можно более запутанный) лабиринт. Можно ли пройти ваш лабиринт используя правило правой (левой) руки?***

# 3 ***Я нарисую вам лабиринт, а вы мне должны будете сказать, работает в моем лабиринте правило правой/левой руки.***



StarcoderdataJupyterScriptsDedupFiltered