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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Модель Ханойской башни с восемью дисками

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

История создания головоломки[править | править исходный текст]

Эту игру придумал французский математик Эдуард Люка, в 1883 году[1], её продавали как забавную игрушку. Первоначально она называлась «Профессор Клаус (Claus) из Колледжа Ли-Су-Стьян (Li-Sou-Stian)»[1], но вскоре обнаружилось, что таинственный профессор из несуществующего колледжа — не более чем анаграмма фамилии изобретателя игры, профессора Люка (Lucas) из колледжа Сен-Луи (Saint Louis).

Ход решения головоломки с четырьмя дисками

Решение[править | править исходный текст]

Блок-схема рекурсивного алгоритма решения

Минимальное число ходов, необходимое для решения головоломки, равно 2n - 1, где n — число дисков[2][3].

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

Применение кода Грея для решения[править | править исходный текст]

Код Грея, рефлексный двоичный код в двоичной системе счисления, в котором два соседних значения различаются только в одном двоичном разряде.

Изначально код Грея предназначался для защиты от ложного срабатывания электромеханических переключателей. Сегодня коды Грея широко используются для упрощения выявления и исправления ошибок в системах связи, а также в формировании сигналов обратной связи в системах управления. Код получил имя исследователя лабораторий Bell Labs Фрэнка Грея. Он использовал этот код в своей импульсной системе связи, для чего был написан патент за номером 2632058.

Коды Грея применяются в решении задачи о Ханойских башнях. Пусть 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->…

Варианты[править | править исходный текст]

С четырьмя и более стержнями[править | править исходный текст]

Хотя вариант с тремя стержнями имеет простое рекурсивное решение, оптимальное решение Ханойской башни с четырьмя стержнями является нерешённой проблемой.

Из этого не следует, что в случае четырёх и более стержней не существует алгоритма для нахождения оптимальных решений. Достаточно представить головоломку в виде неориентированного графа, сопоставив размещениям дисков вершины, а ходам — рёбра, и использовать любой алгоритм поиска (например, поиск в ширину) для нахождения оптимального решения. Однако эффективной стратегии определения оптимального решения для большого числа дисков нет: количество ходов, необходимое для решения головоломки с 10 стержнями и 1000 дисками, остаётся неизвестным.

Существует предположительно оптимальный алгоритм Фрейма — Стюарта, разработанный в 1941 году[4]. Связанная гипотеза Фрейма — Стюарта утверждает, что алгоритм Фрейма — Стюарта всегда находит оптимальное решение. Оптимальность алгоритма Фрейма — Стюарта была экспериментально проверена вплоть до 30 дисков на 4 стержнях[5].

Другие варианты Ханойской башни с четырьмя стержнями рассматриваются в обзорной статье Пола Стокмайера[6].

Алгоритм Фрейма — Стюарта[править | править исходный текст]

Алгоритм Фрейма — Стюарта, дающий предположительно оптимальное решение для четырёх (или более) стержней, описывается следующим образом:

  • Пусть n — количество дисков.
  • Пусть r — число стержней.
  • Определим T(n,r) как наименьшее число ходов, необходимое для переноса n дисков с использованием r стержней.

Алгоритм может быть описан рекурсивно:

  1. Для некоторого k, 1 \leq k < n, перенести верхние k на стержень i, не являющийся ни начальным, ни конечным стержнем, затратив на это T(k,r) ходов.
  2. Не используя стержень i, содержащий теперь верхние k дисков, перенести оставшиеся n-k дисков на конечный стержень, используя только оставшиеся r-1 стержней и затратив на это T(n-k,r-1) ходов.
  3. Наконец, переместить верхние k дисков на конечный стержень, затратив на это T(k,r) ходов.

На весь процесс требуется 2T(k,r)+T(n-k,r-1) ходов. Значение k выбирается таким образом, чтобы значение этого выражения было минимальным.

Легенды[править | править исходный текст]

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

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

Количество перекладываний в зависимости от количества колец вычисляется по формуле 2^n-1.

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

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

В культуре[править | править исходный текст]

В рассказе Эрика Фрэнка Рассела «Ваш ход» (Quiz Game, в другом переводе — «Игра на выживание»)[7], чтобы оттянуть время казни инопланетянами, главный герой выбирает игру в Ханойскую башню с 64 дисками в качестве последней игры. Объявленные правила модифицированы для двух игроков — игроки должны перекладывать диски по одному за ход, победителем считается тот, кто сделает последний ход. Герой называет такую игру «арки-маларки» и клянётся, что «священнослужители Бенаресского храма» на Земле играют в эту игру.

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

Примечания[править | править исходный текст]

  1. 1 2 Мартин Гарднер, Математические головоломки и развлечения
  2. Petković Miodrag Famous Puzzles of Great Mathematicians. — AMS Bookstore, 2009. — P. 197. — ISBN 0-8218-4814-3
  3. Graham Ronald Concrete Mathematics: A Foundation for Computer Science. — Addison–Wesley, 1998. — P. 21. — ISBN 0201558025
  4. Solution to advanced problem 3819, American Mathematical Monthly, 1941.
  5. Korf, Richard E., and Ariel Felner (2007). «Recent Progress in Heuristic Search: a Case Study of the Four-Peg Towers of Hanoi Problem». IJCAI: 2324–2329.
  6. Paul Stockmeyer (1994). «Variations on the Four-Post Tower of Hanoi Puzzle». Congressus Numerantium 102: 3–12.
  7. Рассел, Эрик Фрэнк (4 1994). «Ваш ход». Если: 34-42.

Ссылки[править | править исходный текст]