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

Математическая игра-головоломка

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

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

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

Ханойская башня ( также называемая «Проблема храма Бенареса» ^[1] или «Башня Брахмы» или «Башня Лукаса» ^[2] и иногда во множественном числе как «Башни» или просто головоломка-пирамида ^[3] ) — это математическая игра или головоломка, состоящая из трех стержней. и несколько дисков разного диаметра , которые могут надвигаться на любой стержень. Головоломка начинается с того, что диски укладываются на один стержень в порядке убывания размера, самый маленький вверху, таким образом приближаясь к конической форме. Цель головоломки — переместить всю стопку на один из других стержней, соблюдая следующие правила: ^[4]

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

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

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

Головоломка была изобретена французским математиком Эдуардом Лукасом и впервые представлена ​​в 1883 году как игра, открытая «Н. Клаусом (де Сиамом)» (анаграмма «Лукаса д'Амьена»), ^{[5] [6] [7]} и позже опубликовано в виде буклета в 1889 году ^[8] и в посмертно опубликованном томе Лукаса « Récréations mathématiques» . ^[9] К игре прилагался буклет с инструкциями, в котором описывалось предполагаемое происхождение игры в Тонкине и утверждалось, что, согласно легенде, брахманы в храме в Бенаресе осуществляли движение «Священной Башни Брахмы », состоящей из шестидесяти четыре золотых диска по тем же правилам, что и в игре, и что завершение строительства башни приведет к концу света. ^[10] Почти сразу же появились многочисленные вариации этой легенды, касающиеся древней и мистической природы головоломки. ^[5]

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

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

Решение

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

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

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

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

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

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

• Переместите один диск с привязки 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 > 1, то где-то в последовательности ходов самый большой диск должен быть перенесен с колышка A на другой колышек, предпочтительно на колышек C. Единственная ситуация, которая допускает этот ход, — это когда все меньшие h − 1 диски находятся на привязке B. Следовательно, сначала все диски 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.

С помощью математической индукции легко доказать, что описанная выше процедура требует минимально возможного количества ходов и что полученное решение является единственным с этим минимальным количеством ходов. Используя рекуррентные соотношения , точное количество ходов, необходимое для этого решения, можно вычислить по формуле: . Этот результат получается, если учесть, что шаги 1 и 3 требуют ходов, а шаг 2 — один ход, что дает . ${\displaystyle 2^{h}-1}$ ${\displaystyle T_{h-1}}$ ${\displaystyle 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 is от привязки (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 число дисков с конечными нулями перемещается на минимально возможное расстояние до вправо (при необходимости возвращаясь влево). ^[14]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Вариации

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

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

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

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

Чтобы переместить 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 дисков по и против часовой стрелки, тогда мы можем записать обе формулы:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Математика, связанная с этой обобщенной проблемой, становится еще более интересной, если принять во внимание среднее количество ходов в кратчайшей последовательности ходов между двумя начальной и конечной конфигурациями диска, выбранными случайным образом. Хинц и Чан Тат-Хунг независимо друг от друга обнаружили ^{[27] [28]} (см. также ^{[29] : Глава 1, стр. 14} ), что среднее количество ходов в n-дисковой Башне определяется следующей точной формулой:

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

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

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

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

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

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

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

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

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

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

Приложения

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Смотрите также

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

Примечания

1. "A000225 - OEIS". oeis.org . Проверено 3 сентября 2021 г.
2. Хофштадтер, Дуглас Р. (1985). Метамагические темы: В поисках сущности разума и закономерностей . Нью-Йорк: Основные книги. ISBN 978-0-465-04540-2.
3. Кон, Эрнст М. (1963). «Устройство для демонстрации некоторых элементарных свойств целых чисел». Учитель математики . 56 (2). Национальный совет учителей математики: 84. doi :10.5951/MT.56.2.0084. ISSN  0025-5769 . Проверено 9 марта 2021 г.
4. Вайсштейн, Эрик В. «Ханойская башня». mathworld.wolfram.com . Проверено 20 октября 2023 г.
5. Хинц, Андреас М.; Клавжар, Санди; Милутинович, Урош; Петр, Кирилл (31 января 2013 г.). Ханойская башня – мифы и математика . Спрингер. ISBN 978-3034802369.
6. Стокмейер, Пол К. «Ханойская башня: Библиография» (PDF) . Проверено 21 февраля 2024 г.
7. де Парвиль, Анри (27 декабря 1883). «Ревю наук». Журнал дебатов . Проверено 21 февраля 2024 г.
8. Лукас, Эдуард (1889). Jeux scientifiques pour servir à l'histoire, à l'enseignement et à la pratique du Calcul et du Dessin (на французском языке). Париж: Шамбон и Бай . Проверено 27 января 2024 г.
9. Лукас, Эдуард (1892). Récréations mathématiques (на французском языке). Том. 3. Библиотека Альберта Бланшара, 1979. с. 58.
10. Стокмейер, Пол К. «Инструкции по Ханойской башне на английском языке, страница 1» . Проверено 21 февраля 2024 г.
11. Москович, Иван (2001). 1000 игровых мыслей: головоломки, парадоксы, иллюзии и игры . Рабочий. ISBN 978-0-7611-1826-8.
12. Петкович, Миодраг (2009). Знаменитые загадки великих математиков . Книжный магазин АМС. п. 197. ИСБН 978-0-8218-4814-2.
13. Трошкин, М. «Судный день наступает: нерекурсивный анализ рекурсивной проблемы Ханойских башен». Фокус (на русском языке). 95 (2): 10–14.
14. Уоррен, Генри С. (2003). «Раздел 5-4: Подсчет конечных нулей». Хакерское удовольствие (1-е изд.). Бостон, Массачусетс: Аддисон-Уэсли. ISBN 978-0-201-91465-8.
15. Миллер, Чарльз Д. (2000). «Глава 4: Двоичные числа и стандартный код Грея». Математические идеи (9-е изд.). Эддисон Уэсли Лонгман. ISBN 978-0-321-07607-6. Архивировано из оригинала 21 августа 2004 г.
16. Грос, Л. (1872). Теория дю Багенодье . Лион: Эме Вентринье.
17. «Уголок вопросов - Обобщение проблемы Ханойских башен» . math.toronto.edu . Проверено 28 июля 2023 г.
18. Хинц, Андреас М.; Клавзар, Санди; Милутинович, Урос; Петр, Кирилл; Стюарт, Ян (2013). Ханойская башня – мифы и математика (1-е изд.). Базель: Springer Science+Business Media . стр. 241–259. ISBN 9783034802369.
19. Гедеон, ТД (1996). «Циклические башни Ханоя: итеративное решение, созданное трансформацией». Компьютерный журнал . 39 (4): 353–356. дои : 10.1093/comjnl/39.4.353.
20. Буш, Т. (2014). «Кватриемный тур по Ханое» (PDF) . Бык. Бельг. Математика. Соц. Саймон Стевин . 21 (5): 895–912. дои : 10.36045/bbms/1420071861. S2CID  14243013. Архивировано из оригинала (PDF) 21 сентября 2017 г.
21. Стюарт, Б.М.; Фрейм, JS (март 1941 г.). «Решение сложной задачи 3819». Американский математический ежемесячник . 48 (3): 216–9. дои : 10.2307/2304268. JSTOR  2304268.
22. Клавзар, Санди; Милутинови, Уро; Петрб, Кирилл (2002). «Вариации на тему Ханойской башни с четырьмя столбами» (Постскриптум) . Конгресс Нумерантиум . 102 .
23. Стокмейер, Пол (1994). «Вариации на тему Ханойской башни с четырьмя столбами» (Постскриптум) . Конгресс Нумерантиум . 102 : 3–12.
24. Гертер, Феликс; Роте, Гюнтер (14 ноября 2018 г.) [09 августа 2018 г., 12 августа 2017 г., 09 августа 2017 г., 22 апреля 2016 г.]. «Бесконтурное перечисление кода Грея и Бухарестская башня» (PDF) . Теоретическая информатика . 748 . Берлин, Германия: 40–54. arXiv : 1604.06707 . дои : 10.1016/j.tcs.2017.11.017. ISSN  0304-3975. S2CID  4014870. Архивировано (PDF) из оригинала 16 декабря 2020 г. Проверено 16 декабря 2020 г.[1] (15/18/19/24 страниц)
25. "Слог CSC148 Университета Торонто" . 5 апреля 2014 года . Проверено 22 июля 2015 г.
26. «UPenn CIS 194 Введение в задание Haskell 1» (PDF) . Проверено 31 января 2016 г.
27. Хинц, А. (1989). «Ханойская башня». L'Enseignement Mathématique . 35 : 289–321. дои : 10.5169/уплотнения-57378.
28. Чан, Т. (1988). «Статистический анализ проблемы ханойских башен». Интерн. Дж. Компьютер. Математика . 28 (1–4): 57–65. дои : 10.1080/00207168908803728.
29. Стюарт, Ян (2004). Еще одна прекрасная математика, в которую вы меня втянули . Курьер Дувр. ISBN 978-0-7167-2342-4.
30. Ромик, Д. (2006). «Кратчайшие пути в графе Ханойской башни и конечные автоматы». SIAM Journal по дискретной математике . 20 (3): 610–622. arXiv : math/0310109 . дои : 10.1137/050628660. S2CID  8342396.
31. Прасад Витал Чаугул (2015). «Рекурсивное решение проблемы двухцветных башен Ханоя» (PDF) . Журнал развлекательной математики (4): 37–48. ISSN  2182-1976.
32. Арнольд, Питер (28 мая 2003 г.). Карточные игры для одного. Стерлинг Издательская компания. ISBN 978-0-600-60727-4.
33. Хеджес, Сид Г. (06 марта 2018 г.). Книга хобби для каждого. Read Books Ltd. ISBN 978-1-5287-8344-6.
34. "Башня Ханойского Терпения (также известная как Башня Ханойского Терпения)" . bbcmicro.co.uk . Проверено 17 октября 2020 г.
35. Инь, Си; Лю, Синьхун; Пан, Юнг-Тин; Уолш, Кэтлин А.; Ян, Хун (4 ноября 2014 г.). «Многослойные ультратонкие палладиевые нанолисты в форме ханойской башни». Нано-буквы . 14 (12): 7188–94. Бибкод : 2014NanoL..14.7188Y. дои : 10.1021/nl503879a. ПМИД  25369350.
36. Чжан, Дж (1994). «Представления в распределенных когнитивных задачах» (PDF) . Когнитивная наука . 18 : 87–122. дои : 10.1016/0364-0213(94)90021-3.
37. Чжан, Цзяцзе; Валджи, Мухаммад Ф. (2011). «TURF: На пути к единой системе удобства использования EHR». Журнал биомедицинской информатики . 44 (6): 1056–67. дои : 10.1016/j.jbi.2011.08.005 . ПМИД  21867774.
38. Бирс, СР; Розенберг, доктор медицинских наук; Дик, Эл.; Уильямс, Т.; О'Хирн, КМ; Бирмахер, Б.; Райан, CM (1999). «Нейропсихологическое исследование функции лобных долей у психотропно-наивных детей с обсессивно-компульсивным расстройством». Американский журнал психиатрии . 156 (5): 777–9. дои : 10.1176/ajp.156.5.777. PMID  10327915. S2CID  21359382.
39. Рид, ЧР; Самптер, диджей; Бикман, М. (январь 2011 г.). «Оптимизация в естественной системе: аргентинские муравьи решают задачу Ханойских башен». Дж. Эксп. Биол . 214 (Часть 1): 50–8. CiteSeerX 10.1.1.231.9201 . дои : 10.1242/jeb.048173. PMID  21147968. S2CID  18819977. 
40. Рассел, Эрик Франк (апрель 1959 г.). «А теперь вдохни». Новеллеты. Потрясающая научная фантастика . Том. 63, нет. 2. стр. 31–77.
    • Перепечатано: Рассел, Эрик Франк (2000). «А теперь вдохни». В Катце, Рик (ред.). Основные ингредиенты: Избранные рассказы Эрика Фрэнка Рассела . Фрамингем, Массачусетс: NESFA Press. стр. 399–417. ISBN 978-1-886778-10-8.
41. Bonanome, Марианна С.; Дин, Маргарет Х.; Дин, Джудит Патнэм (2018). «Самоподобные группы». Выборка замечательных групп: Томпсона, Самоподобная, Фонарщика и Баумслага-Солитара . Компактные учебники по математике. Чам, Швейцария: Springer. п. 96. дои : 10.1007/978-3-030-01978-5_3. ISBN 978-3-030-01976-1.
42. Бертвистл, Грэм (январь 1985 г.). «Сопрограммы Ханоя». Уведомления ACM SIGPLAN . 20 (1): 9–10. дои : 10.1145/988284.988286. S2CID  7310661.
43. «Четвертое измерение: Небесный производитель игрушек». Доктор Кто . BBC Один . Проверено 2 апреля 2021 г.
44. «Ханойская башня (концепция видеоигры)» . Giantbomb.com . Проверено 5 декабря 2010 г.
45. «Ханойская башня / Андамиро». Развлечения Сеги. Архивировано из оригинала 1 марта 2012 г. Проверено 26 февраля 2012 г.

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

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