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

Эта статья о математической дисковой игре. Чтобы узнать о карточной игре, см. Ханойскую башню . Чтобы узнать о вьетнамском небоскребе, см. Keangnam Hanoi Landmark Tower .

Набор моделей Ханойской башни (из 8 дисков)

Анимированное решение головоломки Ханойская башня для T (4, 3)

в Мехико Интерактивная выставка Ханойской башни в Музее Универсум

( Ханойская башня также называемая проблемой храма в Бенаресе). или Башня Брахмы или Башня Лукаса а иногда и во множественном числе как Башни или просто головоломка-пирамида. ) — математическая игра или головоломка, состоящая из трёх стержней и ряда дисков разного диаметра , которые могут надвигаться на любой стержень. Головоломка начинается с того, что диски складываются на один стержень в порядке убывания размера, самый маленький вверху, таким образом приближаясь к конической форме. Цель головоломки — переместить всю стопку на один из других стержней, соблюдая следующие правила:

1. Одновременно можно перемещать только один диск.
2. Каждый ход состоит в том, чтобы взять верхний диск из одной из стопок и положить его на другую стопку или на пустой стержень.
3. Ни один диск не может быть помещен поверх диска, который меньше его.

С тремя дисками головоломку можно решить за семь ходов. Минимальное количество ходов, необходимое для решения головоломки Ханойской башни, — 2. ^н − 1 , где n — количество дисков.

Происхождение

Головоломка была изобретена французским математиком Эдуардом Лукасом и впервые представлена ​​в 1883 году как игра, открытая «Н. Клаусом (де Сиамом)» (анаграмма «Лукаса д'Амьена»), и позже опубликован в виде буклета в 1889 году. и в посмертно опубликованном томе « Математических развлечений » Лукаса . К игре прилагался буклет с инструкциями, в котором описывалось предполагаемое происхождение игры в Тонкине и утверждалось, что, согласно легенде, брамины в храме в Бенаресе осуществляли движение «Священной Башни Брахмы », состоящей из шестидесяти четырех золотых дисков. , по тем же правилам, что и в игре, и что завершение строительства башни приведет к концу света. Почти сразу же появились многочисленные вариации этой легенды, касающиеся древней и мистической природы загадки.

Если бы легенда была правдой и если бы жрецы могли перемещать диски со скоростью один в секунду, используя наименьшее количество ходов, им потребовалось бы 2 ⁶⁴ − 1 секунда или примерно 585 миллиардов лет до завершения, что примерно в 42 раза превышает предполагаемый текущий возраст Вселенной .

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

Решение

В головоломку можно играть с любым количеством дисков, хотя во многих игрушечных версиях их от 7 до 9. Минимальное количество ходов, необходимое для решения головоломки Ханойской башни, — 2. ^н − 1 , где n — количество дисков. Это именно н ^й Число Мерсенна без требований простоты.

Итеративное решение

Анимация итерационного алгоритма решения задачи с 6 дисками

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

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

Итеративное решение эквивалентно повторному выполнению следующей последовательности шагов до тех пор, пока цель не будет достигнута:

• Переместите один диск с привязки A на привязку B или наоборот, в зависимости от того, какое перемещение разрешено.
• Переместите один диск с привязки A на привязку C или наоборот, в зависимости от того, какое перемещение разрешено.
• Переместите один диск с привязки B на привязку C или наоборот, в зависимости от того, какое перемещение разрешено.

При таком подходе стек окажется на привязке B, если число дисков нечетное, и на привязке C, если оно четное.

Рекурсивное решение

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

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

• обозначьте колышки А, Б, С,
• пусть n — общее количество дисков, а
• пронумеруйте диски от 1 (самый маленький, самый верхний) до n (самый большой, самый нижний).

Предполагая, что все n дисков правильно распределены по привязкам; привязке есть m верхних дисков предполагая, что на исходной , а все остальные диски больше m , поэтому их можно безопасно игнорировать; переместить m дисков из исходной привязки в целевую , используя запасную привязку, не нарушая правил:

1. Переместите m − 1 дисков из источника в резервную привязку, используя ту же общую процедуру решения . Правила не нарушаются, по предположению. В результате диск m остается верхним на исходной привязке.
2. Переместить диск m от исходной к целевой привязке, что, по предположениям, гарантированно будет допустимым перемещением — простой шаг .
3. Переместите m − 1 диск, который мы только что поместили на запасной, с запасного на целевую привязку, используя ту же общую процедуру решения , так, чтобы они были помещены поверх диска m, не нарушая правил.
4. Базовый вариант — переместить 0 дисков (на шагах 1 и 3), то есть ничего не делать, что не нарушает правил.

Затем полное решение «Ханойская башня» перемещает n дисков из исходной привязки A в целевую привязку C, используя B в качестве запасной привязки.

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

Логический анализ рекурсивного решения

Как и во многих математических головоломках, найти решение можно проще, если решить немного более общую задачу: как переместить башню из дисков h (высоты) с начальной точки f = A (от) на конечную точку t = C (к ), B является оставшейся третьей привязкой и предполагается, что t ≠ f . Во-первых, заметим, что задача симметрична для перестановок имен колышков ( симметричная группа S ₃ ). Если известно решение, перемещающееся от привязки A к привязке C , то, переименовывая привязки, одно и то же решение можно использовать для любого другого выбора начальной и целевой привязки. Если диск всего один (а то и вообще нет), проблема тривиальна. Если h = 1, переместите диск с колышка A на C. колышек Если h то в последовательности ходов самый большой диск должен быть перенесен с колышка A на другой колышек, предпочтительно на колышек C. > 1, то где - Единственная ситуация, которая допускает этот ход, — это когда все меньшие − 1 диски находятся на привязке B. h Следовательно, сначала все диски h − 1 меньшего размера должны перейти из A в B . Затем переместите самый большой диск и, наконец, переместите h - 1 меньший диск с прищепки. B к C. привязке Наличие самого большого диска не препятствует перемещению h − 1 меньших дисков и его можно временно игнорировать. Теперь задача сводится к перемещению h − 1 дисков с одного колышка на другой, сначала из A в B , а затем из B в C , но оба раза можно использовать один и тот же метод, переименовывая колышки. Ту же стратегию можно использовать, чтобы свести задачу h - 1 к h - 2, h - 3 и так далее, пока не останется только один диск. Это называется рекурсией. Схематически этот алгоритм можно представить следующим образом.

Определите диски в порядке увеличения размера натуральными числами от 0 до h , не включая его . Следовательно, диск 0 — самый маленький, а диск h − 1 — самый большой.

Ниже приведена процедура перемещения башни из h дисков с стержня A на стержень C , где B является оставшимся третьим стержнем:

1. Если h > 1, то сначала используйте эту процедуру, чтобы переместить h - 1 с привязки A на привязку B. диски меньшего размера на
2. Теперь самый большой диск, т.е. диск h, переместить с привязки A на привязку C. можно
3. Если h > 1, снова используйте эту процедуру, чтобы переместить h - 1 с привязки B на привязку C. диски меньшего размера на

С помощью математической индукции легко доказать, что описанная выше процедура требует минимально возможного количества ходов и что полученное решение является единственным с этим минимальным количеством ходов. Используя рекуррентные соотношения , точное количество ходов, необходимое для этого решения, можно рассчитать по формуле: $2^{h}-1$. Этот результат получен, если отметить, что шаги 1 и 3 занимают $T_{h-1}$ ходов, а шаг 2 занимает один ход, давая $T_{h}=2T_{h-1}+1$.

Нерекурсивное решение

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

В попеременных ходах:

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

При самом первом ходе наименьший диск переходит в точку t, если h нечетное, и в точку r, если h четное.

Также обратите внимание, что:

• Диски, чьи порядковые номера имеют четную четность, движутся в том же направлении, что и самый маленький диск.
• Диски, порядковые номера которых имеют нечетную четность, движутся в противоположном направлении.
• Если h четно, оставшийся третий колышек во время последовательных ходов равен t , r , f , t , r , f и т. д.
• Если h нечетно, оставшаяся третья привязка во время последовательных ходов равна r , t , f , r , t , f и т. д.

Обладая этими знаниями, набор дисков в середине оптимального решения можно восстановить, используя только информацию о состоянии, кроме позиций каждого диска:

• Назовите ходы, описанные выше, «естественным» ходом диска.
• Исследуйте самый маленький верхний диск, который не является диском 0, и обратите внимание, каким будет его единственный (допустимый) ход: если такого диска нет, то мы находимся либо на первом, либо на последнем ходе.
• Если этот ход является «естественным» ходом диска, то диск не перемещался с момента последнего перемещения диска 0, и этот ход следует предпринять.
• Если этот ход не является «естественным» ходом диска, переместите диск 0.

Бинарное решение

Позиции диска могут быть определены более непосредственно из двоичного (по основанию 2) представления номера хода (начальное состояние — ход № 0, со всеми цифрами 0, а конечное состояние — со всеми цифрами 1), используя следующие правила:

• Для каждого диска имеется одна двоичная цифра ( бит ).
• Самый старший (крайний левый) бит представляет самый большой диск. Значение 0 указывает, что самый большой диск находится на начальной привязке, а 1 указывает, что он находится на последней привязке (правая привязка, если количество дисков нечетное, и средняя привязка в противном случае).
• Битовая строка считывается слева направо, и каждый бит можно использовать для определения местоположения соответствующего диска.
• Бит с тем же значением, что и предыдущий, означает, что соответствующий диск уложен поверх предыдущего диска на том же колышке.

  (То есть: прямая последовательность единиц или нулей означает, что все соответствующие диски находятся на одной привязке.)

• Бит, значение которого отличается от предыдущего, означает, что соответствующий диск находится на одну позицию левее или правее предыдущего. Левый он или правый определяется следующим правилом:
  • Предположим, что начальная привязка находится слева.
  • Также предположим «обертку» — поэтому правая привязка считается одной привязкой «слева» от левой, и наоборот.
  • Пусть n — количество дисков большего размера, расположенных на той же привязке, что и их первый больший диск, и прибавьте 1, если самый большой диск находится на левой привязке. Если n четное, диск расположен на один колышек вправо, если n нечетное, то диск расположен на один колышек влево (в случае четного количества дисков и наоборот).

Например, в 8-дисковом Ханое:

• Переместить 0 = 00000000.
  • Самый большой диск равен 0, поэтому он находится на левом (начальном) колышке.
  • Все остальные диски также имеют номер 0, поэтому они располагаются поверх него. Следовательно, все диски находятся на начальной привязке.
• Ход 2 ⁸ − 1 = 11111111.
  • Самый большой диск — 1, поэтому он находится на среднем (последнем) колышке.
  • Все остальные диски также имеют номер 1, поэтому они располагаются поверх него. Следовательно, все диски находятся на последнем колышке, и головоломка завершена.
• Переместить 216 ₁₀ = 11011000.
  • Самый большой диск — 1, поэтому он находится на среднем (последнем) колышке.
  • Второй диск тоже равен 1, поэтому он укладывается поверх него, на средний колышек.
  • Третий диск равен 0, поэтому он находится на другой привязке. Поскольку n нечетно ( n = 1), оно находится на одну привязку влево, т. е. на левой привязке.
  • Четвертый диск равен 1, поэтому он находится на другом колышке. Поскольку n нечетно ( n = 1), оно находится на одну привязку влево, т. е. на правой привязке.
  • Пятый диск тоже равен 1, поэтому он сложен поверх него, на правом колышке.
  • Шестой диск равен 0, поэтому он находится на другом колышке. Поскольку n четное ( n = 2), диск находится на одну колышку вправо, т. е. на левую колышек.
  • Диски семь и восемь также равны 0, поэтому они сложены поверх него, на левом колышке.

Привязки источника и назначения для m -го хода также можно элегантно найти из двоичного представления m с помощью побитовых операций . Чтобы использовать синтаксис языка программирования C , переместите m из привязки (m & m - 1) % 3 привязывать ((m | m - 1) + 1) % 3, где диски начинаются с привязки 0 и заканчиваются на привязке 1 или 2 в зависимости от того, четное или нечетное количество дисков. Другая формулировка взята из колышка (m - (m & -m)) % 3 привязывать (m + (m & -m)) % 3.

Кроме того, диск, который нужно переместить, определяется тем, сколько раз счетчик ходов ( m ) можно разделить на 2 (т. е. количество нулевых битов справа), считая первый ход за 1 и идентифицируя диски по числам. 0, 1, 2 и т. д. в порядке увеличения размера. Это позволяет очень быструю нерекурсивную компьютерную реализацию находить положения дисков после m перемещений без привязки к любому предыдущему перемещению или распределению дисков.

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

Решение с кодом Грея

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

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

Считая ходы с 1 и обозначая диски числами, начиная с 0, в порядке возрастания размера, порядковый номер диска, который нужно переместить во время хода m , равен числу раз, которое m можно разделить на 2.

Этот метод определяет, какой диск следует переместить, но не определяет, куда его переместить. Для самого маленького диска всегда есть две возможности. Для остальных дисков всегда есть одна возможность, за исключением случаев, когда все диски находятся на одной привязке, но в этом случае либо нужно переместить самый маленький диск, либо цель уже достигнута. К счастью, существует правило, которое указывает, куда переместить самый маленький диск. Пусть f — начальная привязка, t — конечная привязка, а r — оставшаяся третья привязка. Если количество дисков нечетное, наименьший диск перемещается по колышкам в порядке f → t → r → f → t → r и т. д. Если количество дисков четное, порядок действий должен быть обратным: f → r → t. → ж → р → т и т. д.

Положение изменения бита в решении кода Грея дает размер диска, перемещаемого на каждом шаге: 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, ... (последовательность A001511 в OEIS ), последовательность, также известная как функция линейки , или на единицу больше степени 2 в номере хода. В языке Вольфрам , IntegerExponent[Range[2^8 - 1], 2] + 1 дает ходы для головоломки с 8 дисками.

Графическое представление

Основная статья: график Ханоя

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

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

Добавляется вторая буква для обозначения большего диска. Понятно, что изначально его нельзя переместить.

Самый верхний маленький треугольник теперь представляет возможности одного хода с двумя дисками:

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

Для h + 1 дисков возьмите граф h дисков и замените каждый маленький треугольник графом для двух дисков.

Для трех дисков график такой:

Игровой график 7 уровня показывает связь с треугольником Серпинского .

• назовите колышки a, b и c
• перечислить позиции дисков слева направо в порядке увеличения размера

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

В общем, для головоломки с n дисками есть 3 ^н узлы в графе; каждый узел имеет три ребра с другими узлами, за исключением трех угловых узлов, у которых их два: всегда можно переместить наименьший диск на один из двух других привязок, и можно переместить один диск между этими двумя привязками, за исключением ситуация, когда все диски уложены на один колышек. Угловые узлы представляют собой три случая, когда все диски сложены на одном колышке. Диаграмма для n + 1 дисков получается путем взятия трех копий диаграммы n -дисков, каждая из которых представляет все состояния и перемещения меньших дисков для одной конкретной позиции нового самого большого диска, и соединения их по углам с тремя новые ребра, представляющие единственные три возможности переместить самый большой диск. Таким образом, полученная цифра имеет 3 ^{п +1} узлов и по-прежнему имеет три угла и только два ребра.

По мере добавления новых дисков графическое представление игры будет напоминать фрактальную фигуру — треугольник Серпинского . Ясно, что подавляющее большинство позиций головоломки никогда не будет достигнуто при использовании кратчайшего возможного решения; действительно, если жрецы легенды используют максимально долгое решение (без повторного посещения какой-либо позиции), им потребуется 3 ⁶⁴ − 1 ход или более 10 ²³ годы.

Самый длинный неповторяющийся путь для трех дисков можно визуализировать, стирая неиспользуемые края:

Кстати, этот самый длинный неповторяющийся путь можно получить, запретив все ходы из a в c .

для Гамильтонов цикл трех дисков:

На графиках ясно видно, что:

• Из каждого произвольного распределения дисков существует ровно один кратчайший способ переместить все диски на одну из трех привязок.
• Между каждой парой произвольных распределений дисков существует один или два различных кратчайших пути.
• Из каждого произвольного распределения дисков существует один или два разных самых длинных несамопересекающихся пути для перемещения всех дисков к одной из трех привязок.
• Между каждой парой произвольных распределений дисков существует один или два различных самых длинных несамопересекающихся пути.
• Пусть N _h — количество несамопересекающихся путей перемещения башни из h дисков с одного колышка на другой. Затем:
  • Н ₁ = 2
  • Н _{час +1} знак равно ( Н _час ) ² + ( Н _ч ) ³

Это дает N _h равное 2, 12, 1872, 6563711232,... (последовательность A125295 в OEIS )

Вариации

Линейное Ханой

Если все ходы должны осуществляться между соседними колышками (т.е. при наличии колышков A, B, C невозможно перемещаться непосредственно между колышками A и C), то перемещение стопки из n дисков с колышка A на колышек C занимает 3 ^н − 1 ход. Решение использует все 3 ^н действительные позиции, всегда делая уникальный ход, который не отменяет предыдущий ход. Положение со всеми дисками на колышке B достигается на полпути, т.е. после (3 ^н − 1)/2 хода.

Циклический Ханой

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

Чтобы переместить n дисков против часовой стрелки к соседней целевой привязке:

1. переместите n - 1 дисков против часовой стрелки к целевому колышку
2. переместить диск № n на один шаг по часовой стрелке
3. переместите n − 1 диск по часовой стрелке к стартовой колышке
4. переместить диск № n на один шаг по часовой стрелке
5. переместите n - 1 дисков против часовой стрелки к целевому колышку

Чтобы переместить n дисков по часовой стрелке к соседней целевой привязке:

1. переместите n − 1 дисков против часовой стрелки на запасной колышек
2. переместить диск № n на один шаг по часовой стрелке
3. переместите n - 1 дисков против часовой стрелки к целевому колышку

Пусть C(n) и A(n) представляют собой перемещение n дисков по и против часовой стрелки, тогда мы можем записать обе формулы:

	C(n) = A(n−1) n A(n−1)	и	А(п) = А(п-1) п С(п-1) п А(п-1).
Таким образом	С(1) = 1	и	А(1) = 1 1,
	С(2) = 1 1 2 1 1	и	А(2) = 1 1 2 1 2 1 1.

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

1. Схема перемещения башни из дисков с колышка на другой симметрична относительно центральных точек.
2. Самый маленький диск — это первый и последний диск, который перемещается.
3. Группы наименьших ходов диска чередуются с одиночными ходами других дисков.
4. Количество ходов дисков, заданное C(n) и A(n), минимально.

С четырьмя колышками и выше

Хотя версия с тремя колышками имеет простое рекурсивное решение, давно известное, оптимальное решение задачи Ханойской башни с четырьмя колышками (так называемая головоломка Рива) не было проверено Бушем до 2014 года.

Однако в случае четырех и более привязок алгоритм Фрейма – Стюарта известен без доказательства оптимальности с 1941 года.

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

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

Так называемые игровые конфигурации «Башни Бухареста» и «Башни Клагенфурта» дают троичные и пентарные коды Грея.

Алгоритм Фрейма – Стюарта

Алгоритм Фрейма – Стюарта описан ниже:

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

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

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

Весь процесс занимает $2T(k,r)+T(n-k,r-1)$ движется. Следовательно, счет $k$ следует выбирать те, для которых это количество минимально. В случае с четырьмя колышками оптимальным является $k$ равно $n-\left\lfloor {\sqrt {2n+1}}\right\rceil +1$, где $\left\lfloor \cdot \right\rceil$ — ближайшая целочисленная функция . Например, в курсе UPenn CIS 194 по Haskell первая страница заданий перечисляет оптимальное решение для случая с 15 дисками и 4 колышками как 129 шагов, что получается для вышеуказанного значения k .

Предполагается, что этот алгоритм оптимален для любого количества привязок; его количество ходов равно 2 ^{Θ ( н 1/( г −2) )} (при фиксированном r ).

Общие кратчайшие пути и число 466/885

Любопытное обобщение первоначальной цели головоломки состоит в том, чтобы начать с заданной конфигурации дисков, где все диски не обязательно находятся на одном и том же колышке, и за минимальное количество ходов прийти к другой заданной конфигурации. В общем, вычислить кратчайшую последовательность ходов для решения этой задачи может быть довольно сложно. Решение было предложено Андреасом Хинцем и основано на наблюдении, что в кратчайшей последовательности ходов самый большой диск, который необходимо переместить (очевидно, можно игнорировать все самые большие диски, которые будут занимать одну и ту же привязку как в начальном, так и в окончательные конфигурации) переместится либо ровно один раз, либо ровно два раза.

Математика, связанная с этой обобщенной проблемой, становится еще более интересной, если принять во внимание среднее количество ходов в кратчайшей последовательности ходов между двумя начальной и конечной конфигурациями диска, выбранными случайным образом. Хинц и Чан Тат-Хунг независимо друг от друга обнаружили (см. также ), что среднее количество ходов в n-дисковой Башне определяется следующей точной формулой:

${\frac {466}{885}}\cdot 2^{n}-{\frac {1}{3}}-{\frac {3}{5}}\cdot \left({\frac {1}{3}}\right)^{n}+\left({\frac {12}{59}}+{\frac {18}{1003}}{\sqrt {17}}\right)\left({\frac {5+{\sqrt {17}}}{18}}\right)^{n}+\left({\frac {12}{59}}-{\frac {18}{1003}}{\sqrt {17}}\right)\left({\frac {5-{\sqrt {17}}}{18}}\right)^{n}.$

При достаточно больших n к нулю не сходятся только первое и второе слагаемые, поэтому получаем асимптотическое выражение : $466/885\cdot 2^{n}-1/3+o(1)$, как $n\to \infty$. Таким образом, интуитивно мы могли интерпретировать долю $466/885\approx 52.6\%$ как соотношение труда, которое необходимо выполнить при переходе от случайно выбранной конфигурации к другой случайно выбранной конфигурации, относительно сложности пересечения «самого трудного» пути длины $2^{n}-1$ который предполагает перемещение всех дисков с одной привязки на другую. Альтернативное объяснение появлению константы 466/885, а также новый и несколько улучшенный алгоритм вычисления кратчайшего пути дал Ромик.

Магнитный Ханой

Основная статья: Магнитная башня Ханоя

В Магнитной башне Ханоя каждый диск имеет две отдельные стороны, северную и южную (обычно окрашенные в «красный» и «синий»).Диски нельзя располагать одинаковыми полюсами вместе — магниты в каждом диске предотвращают это незаконное перемещение.Кроме того, каждый диск необходимо переворачивать по мере его перемещения.

Начальная конфигурация двухцветных башен Ханоя (n=4)

Двухцветные башни Ханоя

Этот вариант знаменитой головоломки «Ханойская башня» был предложен ученикам 3–6 классов на 2-м чемпионате Франции по математическим и логическим играм, проходившем в июле 1988 года.

Окончательная конфигурация двухцветных башен Ханоя (n=4)

Правила головоломки по сути те же: диски перемещаются между колышками по одному. Ни в коем случае нельзя ставить диск большего размера поверх меньшего. Разница в том, что теперь для каждого размера есть два диска: черный и белый. Также теперь есть две башни из дисков чередующихся цветов. Цель головоломки — сделать башни монохромными (одного цвета). Предполагается, что самые большие диски в нижней части башен поменяются местами.

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

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

Приложения

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

Ханойскую башню часто используют в психологических исследованиях по решению проблем . Существует также вариант этой задачи под названием « Лондонский Тауэр» для нейропсихологической диагностики и лечения нарушений управляющих функций .

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

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

Как упоминалось выше, Ханойская башня популярна для обучения рекурсивным алгоритмам начинающих студентов-программистов. Графическая версия этой головоломки запрограммирована в редакторе emacs , доступ к которому можно получить, набрав Mx hanoi. Существует также пример алгоритма, написанный на Прологе .

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

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

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

В популярной культуре

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

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

В 2007 году концепция задачи «Ханойские башни» использовалась в «Профессоре Лейтоне и дьявольском ящике» в головоломках 6, 83 и 84, но диски были заменены на блины. Загадка была основана на дилемме, когда шеф-повар ресторана должен был переместить стопку блинов с одной тарелки на другую, используя основные принципы оригинальной головоломки (т.е. три тарелки, на которые можно было переместить блины, не имея возможности положить больший блин на меньший и т. д.)

В фильме 2011 года « Восстание планеты обезьян » эта головоломка, названная в фильме «Башня Лукаса», используется в качестве теста для изучения интеллекта обезьян .

Эта головоломка регулярно используется в приключенческих играх и играх- головоломках . Поскольку его легко реализовать и легко распознать, он хорошо подходит для использования в качестве головоломки в более крупных графических играх (например, Star Wars: Knights of the Old Republic и Mass Effect ). В некоторых реализациях используются прямые диски, а в других головоломка принимает иную форму. Существует аркадная версия от Sega .

Версия головоломки на 15 дисках появляется в игре Sunless Sea как замок на гробнице. У игрока есть возможность просмотреть каждый ход головоломки, чтобы решить ее, но игра отмечает, что для завершения потребуется 32 767 ходов. Если особо преданный игрок дойдет до конца головоломки, обнаружится, что завершение головоломки не открывает дверь.

Впервые это было использовано в качестве испытания в Survivor Thai в 2002 году, но вместо колец детали были сделаны так, чтобы напоминать храм. Сук Джай бросил вызов, чтобы избавиться от Джеда, хотя Шии-Энн прекрасно знала, как решить головоломку.Проблема показана как часть испытания с наградой в эпизоде ​​​​американской версии сериала 2011 Survivor года . Оба игрока ( Оззи Ласт и Бенджамин «Тренер» Уэйд ) изо всех сил пытались понять, как решить головоломку, и им помогали их соплеменники.

В Genshin Impact эта головоломка показана в квесте Фарузан «Механизм раннего обучения», где она упоминает, что видит в ней механизм и использует его для создания прототипа игрушки для детей. Она называет это стопками пагод .

См. также

• Узор АБАКАБА
• Схема ротации резервных копий , приложение TOH
• Багенодье
• Рекурсия (информатика)
• « Девять миллиардов имен Бога », рассказ Артура Кларка 1953 года, сюжет которого аналогичен сюжету игры.

Внешние ссылки

• Вайсштейн, Эрик В. «Ханойская башня» . Математический мир . ]]