Ханойская башня что это

Ханойские башни — теоретическое решение без рекурсии

Задача Ханойских башен — одна из самых первых задач, которые предлагаются начинающим программистам, в основном, чтобы проиллюстрировать концепцию рекурсивных решений. В этой статье приводится метод, который позволяет теоретическим путем, без рекурсии, указывать оптимальное решение для текущего хода.

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

Классическое решение данной задачи с тремя стержнями предполагает, что для заданного количества колец n количество перекладываний вычисляется по формуле
.

Дополнительную привлекательность данной задаче придаёт и сопровождающая её легенда:

В Великом храме города Бенарес, под собором, отмечающим середину мира, находится бронзовый диск, на котором укреплены 3 алмазных стержня, высотой в один локоть и толщиной с пчелу. Давным-давно, в самом начале времён, монахи этого монастыря провинились перед богом Брахмой. Разгневанный Брахма воздвиг три высоких стержня и на один из них возложил 64 диска, сделанных из чистого золота. Причем так, что каждый меньший диск лежит на большем. Как только все 64 диска будут переложены со стержня, на который Брахма сложил их при создании мира, на другой стержень, башня вместе с храмом обратятся в пыль и под громовые раскаты погибнет мир.

Между делом новичку предлагается оценить сложность данного решения, чтобы впечатлить результатом: число перемещений дисков, которые должны совершить монахи, равно 18 446 744 073 709 551 615. Если бы монахи, работая день и ночь, делали каждую секунду одно перемещение диска, их работа продолжалась бы 584 миллиарда лет.

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

Александр Бусаров MrShoor написал очень информативный пост, отлично дополняющий соответствующую статью в Википедии, с очень подробным программным кодом, рекомендую ознакомиться с его реализацией рекурсии.

В том же посте имеется описание фрактальной природы алгоритма. Я попытаюсь продолжить это направление, раскрыв применение кода Грея для данной конкретной задачи.

Приведу цитату из соответствующей статьи в Википедии:

Коды Грея применяются в решении задачи о Ханойских башнях. Пусть N — количество дисков. Начнём с кода Грея длины N, состоящего из одних нулей (то есть G(0)), и будем двигаться по кодам Грея (от G(i) переходить к G(i+1)). Поставим в соответствие каждому I-ому биту текущего кода Грея I-ый диск (причём самому младшему биту соответствует наименьший по размеру диск, а самому старшему биту — наибольший). Поскольку на каждом шаге изменяется ровно один бит, то мы можем понимать изменение бита I как перемещение I-го диска. Заметим, что для всех дисков, кроме наименьшего, на каждом шаге имеется ровно один вариант хода (за исключением стартовой и финальной позиций). Для наименьшего диска всегда имеется два варианта хода, однако имеется стратегия выбора хода, всегда приводящая к ответу: если N нечётно, то последовательность перемещений наименьшего диска имеет вид f->t->r->f->t->r->… (где f-стартовый стержень, t-финальный стержень, r-оставшийся стержень), а если N чётно, то f->r->t->f->r->t->.

Оптимальное решение задачи сводится к определению положения дисков после очередного хода. В самом начале (при нулевом ходе) все диски находятся на одном и том же стартовом стержне f. Нумерация весов дисков осуществляется с номера 1 по возрастанию. Требуется описать положение дисков на ходе с номером m.

Очевидно, что при оптимальном решении после хода m количество перемещаемых дисков n будет не более

(1).
Остальные диски большего размера можно не брать в расчёт, что очень удобно при более общем предположении о бесконечном количестве дисков в начальной задаче с тремя стержнями.

Далее, определившись с количеством перемещенных дисков, определимся с их положением.

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

В частности, во время данного хода перемещается тот диск, чей «вес» i коррелирует с максимальной степенью двойки в двоичном разложении номера m текущего хода минус единицу:
(2).

В той же нотации Pascal/Delphi, которую использует MrShoor в своем коде, это может быть записано следующим образом:

Таким образом, для каждого из дисков с весом i мы можем определить тот ход j, на котором диск данного веса был перемещен последний раз:

.

Код для определения номера хода num_move последнего перемещения диска с весом i может выглядеть подобным образом (с условием включения модуля Math):

Стоит обратить внимание на тот факт, что попутно в переменной q_move получено количество перемещений диска с весом i с начала игры.

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

Как отмечено в Википедии, перемещение верхнего диска циклично и, при выборе определенного стержня назначения t, если N нечётно, то последовательность перемещений наименьшего диска имеет вид f->t->r->f->t->r->… (где f-стартовый стержень, t-финальный стержень, r-оставшийся стержень), а если N чётно, то f->r->t->f->r->t->…

Вспоминая о фрактальности, можно заметить, что если отбросить верхнюю часть предшествующих дисков, то текущий диск также совершает подобное циклическое движение во время своих собственных ходов. Учитывая этот факт, становится очевидным, что в зависимости от четности номера диска, цикл перемещения нечетного диска совпадает с циклом перемещения первого диска, а цикл перемещения четных дисков разнится очередностью стержней t и r.
В частности, зная количество перемещения q_move и четность номера текущего диска, можно простым делением на 3 по остатку определить последний стержень, куда был перемещен данный диск.

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

Для тех, кому интересны вариации задачи Ханойских башен, в частности, случаи 4 и более стержней, предлагаю ознакомиться с опытом PapaBubaDiop, развивающего данное направление в виде игр, попутно пытаясь монетизировать некоторые версии на различных платформах.

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

Стиль и язык немного суховаты и годятся скорее для академических работ, потому прошу не судить особо строго, особенно с учетом попытки выправить карму и выбраться из минуса. Всем всего наилучшего и светлого, с Новым 2017 Годом: успехов и удач во всем хорошем!

UPD: Спасибо всем за комментарии, замечания и подсказки. Пример работающего по приведенному выше алгоритму скрипта доступен по этой ссылке. Использовалась библиотека GMP для обеспечения работы с большими числами.

Источник

Ханойская башня: красивая легенда и элегантный алгоритм. Как решить?

В XIX веке была очень популярна одна головоломка, которую придумал математик Франсуа Эдуард Анатоль Люка (François Édouard Anatole Lucas) из колледжа Сен-Луи (Saint Louis). Она была выполнена в форме игрушки и продавалась в качестве развлечения. И носила странное название «Профессор Claus из колледжа Li-Sou-Stian». Пытливые умы еще до решения задачи разгадали первую загадку еще в названии — это анаграмма, скрывающая настоящую фамилию создателя игры и названия колледжа: Lucas и Saint Louis.

Легенда

Игрушка состояла из 3 колышек, на одно из которых было нанизано несколько колечек — от большего к меньшему внизу наверх. Задача заключалась в том, чтобы перенести все колечки на другой колышек, но с несколькими условиями: за один ход можно перенести только одно колечко, сверху всегда должно быть колечко меньшего диаметра, нельзя откладывать кольца в сторону — только на промежуточный колышек. Как и у любой игры, у нее была легенда и красивое название — Ханойская башня.

Легенда заключалась в том, что в городе Ханой расположен храм бога Брамы. В нем находится плита с тремя стержнями из алмаза. При сотворении мира Брама нанизал на один стержень 64 золотых диска в форме пирамиды, и назвал это башней Брамы. Внизу лежал самый большой, а каждый следующий был все меньше и меньше. Если перенести все диски на другой стержень, соблюдая определенные условия, храм обратится в пыль, а мир — в небытие. А теперь, уважаемые знатоки, внимание, вопрос: через какое время наступит конец света, если жрецы будут беспрерывно переносить диски, скажем, по 1 в секунду?

Алгоритм

Эта задача — не просто забавная игра, а проверка интеллекта и функции мышления. Для ее решения есть несколько способов, мы рассмотрим алгоритм из 5 колец. Поняв его правила, мы сможем применить его к любому количеству колец и выяснить, когда же придет апокалипсис. Итак, у нас 3 правила:

У нас есть 3 стержня слева направо — A, B и C. На стержне A расположены кольца снизу вверх 1, 2, 3, 4 и 5. Простота решения заключается в том, чтобы перенести на соседний стержень всю пирамидку, кроме самого нижнего кольца:

Здесь у нас оказывается пирамидка, кроме самого большого кольца, на втором стержне. Далее нам необходимо перенести основание — 1 на самый дальний стержень — C, и далее так же за 15 ходов перенести остальную пирамидку на этот стержень.

Таким образом, количество перемещений равно 2 в степени Х минус 1, где Х — число колец. Проверяем: 2 в пятой степени = 32, 32 – 1 = 31 ход! Получается, монахам в храме Брамы нужно сделать 2 в 64-й степени перекладываний и минус одно: 18 446 744 073 709 551 615. Если взять один ход за одну секунду, то это 18 квинтиллионов 446 квадриллионов 744 триллиона 73 миллиарда 709 миллионов 551 тысяча 615 секунд или 584,9 миллиарда лет.

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

Источник

Ханойская башня

Задача

Головоломка «Ханойская башня», в общем, не нуждается в представлении.

Есть три стержня: A, B и C. На стержень A надеты 8 колец (дисков), наверху самое маленькое, каждое следующее больше предыдущего, а внизу самое большое. Два других стержня пусты. Необходимо перенести все кольца со стержня A на стержень C, пользуясь стержнем B как вспомогательным. В итоге кольца на стержне C должны быть в том же порядке, в котором они исходно находились на стержне A. Брать за один ход несколько колец нельзя. Кроме того, никогда нельзя класть большее кольцо поверх меньшего.

Это классическая версия головоломки. Наша же задача отличается от классики всего одной деталью:

Запрещается переносить кольца между стержнями A и C напрямую. За один ход перенести кольцо можно только либо с A на B (или обратно с B на A), либо с B на C (или обратно).

Сколько ходов потребуется для переноса башни из 8 колец с A на C?

Подсказка 1

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

Подсказка 2

Пусть в башне k колец. Сколько ходов нужно сделать перед тем, как удастся сдвинуть со своего места самое нижнее кольцо на стержень B? А сколько потом ходов нужно будет сделать перед тем, как его удастся сдвинуть с B на C?

Решение

Начнём с обозначений. Пусть H(k) — наименьшее число ходов, за которое удаётся решить нашу задачу для переноса k колец. Если вы воспользовались советом из первой подсказки, то уже знаете, что H(1) = 2, H(2) = 8, а возможно, сумели аккуратно сосчитать и H(3) = 26.

А теперь давайте ответим на вопросы, заданные в подсказке 2. Перед переносом нижнего (k-го) кольца с него нужно снять всю верхнюю часть башни из (k – 1) кольца. Для этого нам потребуется H(k – 1) ходов, и никак не меньше. В результате все эти кольца окажутся на стержне C, что и даст возможность перенести нижнее кольцо с A на B (за 1 ход). После этого, увы, придётся всё ранее сделанное повторить в обратную сторону: чтобы освободить для нижнего кольца стержень C, мы должны с него всю верхнюю часть башни убрать на стержень A. Это требует еще H(k – 1) ходов. Затем (за 1 ход) переносим нижнее кольцо с B на C, и еще раз повторяем H(k – 1) ход для того, чтобы собрать верхнюю часть на стержне C заново. Итого нам потребовалось три раза по H(k – 1) и еще два отдельных хода. Могли ли мы получить результат быстрее? Нет. А медленнее? Как это ни удивительно — тоже нет, разве что мы бы в какой-то момент вернули обратно тот ход, который сделали только что.

Какой промежуточный итог у нас получился? А вот какой:

Такие соотношения, в которых следующий член последовательности линейно (то есть с помощью линейной функции) выражен через предыдущий (один или несколько), называются линейными рекуррентами. Самый простой пример — способ задания арифметической прогрессии: a_k+1 = a_k + d. Чуть более сложный (но тоже очень известный) пример — числа Фибоначчи: f_k+2 = f_k+1 + f_k.

Что делать дальше? Ведь не применять же общие формулы — это как стрельба из пушек по воробьям.

Для восьми колец можно просто сосчитать ответ «в лоб» последовательными вычислениями по приведенной выше рекуррентной формуле. Он окажется равным 6560. Однако есть способ красивее.

Прибавим к H единичку: H’(k) = H(k) + 1. Тогда для H’(k) справедлива такая формула:

Послесловие

Обратите внимание, что в ответе получается формула, очень похожая на формулу для числа ходов в классической головоломке о ханойской башне, только у нас вместо 2 стоит 3. Это не случайно — и причины этой неслучайности будут объяснены чуть ниже.

Еще одно замечательное следствие из полученного нами результата состоит в том, что в процессе перекладывания колец встретятся все допустимые расположения колец на трёх стержнях, так сказать, «все позиции». Почему это можно утверждать? Потому, что общее число позиций равно 3 k (чтобы задать позицию, мы для каждого из k колец должны выбрать тот из трёх стержней, на котором оно в этой позиции находится — а порядок колец на стержне жёстко задан их размерами), и по той простой причине, что никакая позиция не встречается в процессе перекладывания дважды (иначе процесс можно было бы сократить). А поскольку мы вынуждены делать именно (3 k – 1) ходов, каждый раз получая неповторяющиеся позиции, то все позиции будут получены.

А теперь — небольшой экскурс в историю.

Как я честно написал в условии, головоломка «Ханойская башня» в дополнительной рекламе не нуждается. Тем не менее, история ее появления на свет не слишком широко известна.

В одном из храмов индийского города Бенареса установлена бронзовая плита с тремя алмазными стержнями. При сотворении мира верховный индуистский бог Брахма поместил на первый стержень 64 диска из чистого золота, в порядке уменьшения их размеров, и велел монахам переместить их на третий стержень, запретив при этом за один раз переносить более одного диска и помещать больший диск на меньший. С тех пор монахи день и ночь, сменяя друг друга, трудятся над этой задачей. Как только задача будет решена, храм рассыплется в прах и завершится жизнь Брахмы. Затем родится новый Брахма, и всё повторится.

Да, пока вы не успели поверить в то, что монахи индуистского монастыря действительно занимаются решением этой головоломки, спешу сообщить, что это всего лишь легенда. Причем вовсе не древняя, как большинство известных легенд. Придумал ее в конце XIX века французский математик Эдуард Люка. Красивая история оказалась очень удачным рекламным трюком для «раскрутки» (как сказали бы современные PR-менеджеры) придуманной Люка изящной головоломки, выполненной из дерева и состоящей из восьми дисков. Начиная с 1883 года она продавалась под разными названиями — «Башни Брахмы»,«Головоломка о конце света», «Пагода-головоломка», да и место действия легенды неоднократно переносилось то в Китай, то в Тибет, но в итоге «прижилось» во Вьетнаме — вместе с названием «Ханойские башни».

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

Впрочем, с помощью взрослых головоломку можно изготовить и из самых неожиданных «деталей»:

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

На рис. 4 показаны графы H₁–H₄ башен с числом колец от 1 до 4. Ходы по сторонам самых маленьких треугольничков соответствуют переносу самого маленького кольца, ходы между такими треугольниками (но внутри треугольника следующего размера) — переносу следующего кольца, и т. д. Это в стандартной головоломке, когда все переносы разрешены. А что получается в нашей версии, когда между стержнями A и С ничего переносить нельзя?

Картинка с изображением графа, который получается из H₃, приведена на рис. 5:

Попробуем понять, почему граф «обрезается» именно так, как показано на этой картинке. Для этого «укрупним» изображения точек на исходном графе и поместим на них информацию о том, какому расположению колец соответствует данная точка (рис. 6):

Здесь «cbb», например, означает, что самое маленькое кольцо находится на стержне C, а оба остальных — на стержне B. При этом можно либо перенести маленькое кольцо (в стандартном графе — на любой из стержней A или B, то есть получить abb или bbb), либо перенести следующее кольцо на свободный стержень (то есть получить cab). В нашей версии переносы с A на C и с C на A запрещены, так что ровно один из этих трех ходов оказывается невозможным, — а это означает, что каждая позиция, кроме первой и последней, имеет ровно две соседних. Тем самым весь путь по графу оказывается одной длинной ломаной линией без всяких ответвлений. Собственно, именно об этом и была наша задача.

Основное предназначение кодов Грея в наше время — защита информации от помех и ошибок при передаче по каналам связи. Используют коды и разработчики электронных устройств. Например, в статье о графических планшетах рассказано, как это делалось в 1960-е годы в графических устройствах фирмы RAND. Забавно, что изобретателем графического планшета считают Элишу Грея — а «отец» кода Фрэнк Грей, судя по всему, даже не родственник Элише, а всего лишь однофамилец.

Впрочем, у этих кодов есть и более забавные применения. Представьте себе, что вы пытаетесь подобрать ключ к кодовому замку (например, на вокзальной камере хранения или на ремне, которым вы прошлым летом привязали свой велосипед к стенке сарая; рис. 7). Если перебирать все коды по порядку, то в процессе перебора нередко придётся крутить замок слишком долго. Например, для перехода от 999 к 1000 нужно вращать все четыре разрядных колёсика.

Однако если вы пользуетесь для подбора «секрета» кодом Грея (только не двоичным, который описан в статье Википедии по ссылке, и не троичным, который выше построили мы, а десятичным!), то перебор в режиме «один маленький поворот в секунду» займёт у вас ровно столько времени, сколько всего есть кодов, потому что каждый следующий код будет получаться из предыдущего ровно одним поворотом. То естьвсего 9999 секунд. Это, конечно, всё равно около трех часов, но всё-таки не так долго, как при стандартном переборе.

Кстати, о времени. Если в классической легенде Люка о башне Брахмы и «конце света» наступление конца света ожидается после (2 64 – 1) ходов, то в нашей версии головоломки монахам бы потребовалось (3 64 – 1) ходов. Попробуйте мысленно предположить, во сколько раз это больше. Хотя бы по порядку величины — в 100? В 1000? В 10 000? Я уверен, что правильный порядок не угадает почти никто. Наш ответ больше классического более чем в 10 11 раз.

И раз мы уже затронули тему времени, не могу не упомянуть в этой связи замечательный рассказ Эрика Фрэнка Рассела «Игра на выживание». В нем жестокие инопланетяне-гомбарийцы обрекают главного героя-землянина на казнь, но их обычай разрешает ему перед казнью сыграть в любую настольную игру. Результат поединка ничего не решает, но пока игра не закончится, пленник будет жить. Как вы думаете, какую игру выбирает герой?

Источник

Сортировка «Ханойская башня»

Ханойские башни
Про знаменитую игру Эдуарда Люка́ на Хабре не писа́л только ленивый. Кажется, все покровы сорваны и что-то ещё по поводу алгоритма добавить уже невозможно. Но нет, у данной темы есть ещё скрытые ресурсы. Сегодня, в частности, мы переделаем алгоритм решения этой головоломки в полноценную сортировку. (Зачем? Just for fun. В пятницу можно.)

Данный пост посвящается памяти истинного гуру программирования Андрея Mrrl Астрелина, который когда-то мне просто и доходчиво объяснил этот алгоритм. Псевдокод ниже по тексту — его авторства.

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

Кроме того, размеры дисков предполагаются уникальными. Не будем цепляться за это ограничение и разрешим повторы.

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

Остальные условия мы (почти) не меняем:

… и превратить его в сортировку!

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

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

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

Что касается разрешения повторов, то это вообще не имеет никакого значения. Потому что подряд идущие одинаковые диски мы просто перемещаем как один диск.

Алгоритм

Назовем столбики A, B, C (A в начале непустой).

А->С() — переложить один диск с А на С.
top(A), top(С) — размер верхнего диска А или С. Если столбик пуст, то этот размер = MaxInt.
В->С(К) — переложить с В на С все диски, размер которых меньше К (мы это можем сделать, если верхние диски А и С не меньше К).
swap() — переставить столбики В и С (или переименовать их — нам ведь все равно, где окажутся диски).
while(A) — цикл пока А не пуст.

Тогда работает такой алгоритм:

Сложность

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

Насчёт памяти можно сказать, что если используется рекурсия, то и затраты будут соответствующие.

Реализация

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

Характеристики алгоритма

Ссылки

Tower of Hanoi / Ханойская башня

Статьи серии:

Также есть ограничение на размер массива — не более 20-ти элементов. Сделано это сугубо в Ваших же интересах — если возьмёте слишком большой массив, то, может так статься, что сортировать его придётся до глубокой старости.

Статья написана при поддержке компании EDISON Software, которая профессионально разрабатывает умное городское освещение и поддерживает сайты на питоне

Источник