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

редактировать

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

Модельный набор Ханойской башни (с 8 дисками)

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

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

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

Задача головоломки - переместить всю стопку на другой стержень, соблюдая следующие простые правила:

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

С 3 дисками головоломка решается за 7 ходов. Минимальное количество ходов, необходимых для решения загадки Ханойской башни, составляет 2-1, где n - количество дисков.

Содержание

1 Истоки
2 Решение
- 2.1 Итерационное решение
  - 2.1.1 Более простая формулировка итерационного решения
  - 2.1.2 Эквивалентное итерационное решение
- 2.2 Рекурсивное решение
  - 2.2.1 Логический анализ рекурсивного решения
  - 2.2.2 Рекурсивная реализация
- 2.3 Нерекурсивное решение
- 2.4 Бинарное решение
- 2.5 Решение кода Грея
3 Графическое представление
4 Варианты
- 4.1 Смежные колышки
- 4.2 Циклический Ханой
- 4.3 С четырьмя колышками и более
  - 4.3.1 Алгоритм Фрейма – Стюарта
- 4.4 Общие кратчайшие пути и число 466/885
- 4.5 Магнитный Ханой
- 4.6 Двухцветные башни Ханоя
- 4.7 Ханойская башня
5 Приложения
6 В популярной культуре
7 См. Также
8 Примечания
9 Внешние ссылки

Истоки

Головоломка была изобретена французским математиком Эдуардом Лукасом в 1883 году. Многочисленные мифы о древней и мистической природе головоломки возникли почти сразу. Существует история об индийском храме в Каши Вишванатх, в котором есть большая комната с тремя изношенными столбами в ней, окруженная 64 золотыми дисками. Брамины жрецы, выполняя приказ древнего пророчества, с тех пор перемещают эти диски в соответствии с неизменными правилами Брахмы. Поэтому загадка также известна как загадка Башня Брахмы. Согласно легенде, когда завершится последний ход головоломки, мир погибнет.

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

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

Решение

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

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

Анимация итеративного алгоритма, решающего задачу с шестью дисками

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

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

Для четного числа дисков:

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

Для нечетного количества дисков:

сделать допустимое перемещение между стержнями A и C (в любом направлении),
выполнить допустимое перемещение между стержнями A и B (в в любом направлении),
совершает допустимое перемещение между колышками B и C (в любом направлении),
повторяется до завершения.

В каждом случае в общей сложности выполняется 2–1 ход сделал.

Эквивалентное итерационное решение

Другой способ создания уникального оптимального итерационного решения:

Пронумеруйте диски от 1 до n (от наибольшего к наименьшему).

Если n нечетное, первое движение от привязки A к привязке C.
Если n четное, первое перемещение от привязки A к привязке B.

Теперь добавьте эти ограничения:

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

Учитывая эти ограничения после первого хода, на каждом последующем ходу есть только одно допустимое перемещение.

Последовательность этих уникальных ходов является оптимальным решением проблемы, эквивалентным итеративному решению, описанному выше.

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

Иллюстрация рекурсивного решения для загадки Ханойские башни с 4 диска

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

пометьте колышки A, B, C,
пусть n будет общим количеством дисков,
пронумеруйте диски от 1 (наименьший, самый верхний) до n (наибольший, самый нижний).

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

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

Полное решение Tower of Hanoi состоит из перемещения n дисков с исходной привязки A на целевую привязку C, используя B в качестве запасной привязки.

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

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

Как и во многих математических головоломках, поиск решения упрощается путем решения немного более общей проблемы: как переместить башню из h (высотой) дисков из начальная привязка f = A (от) к целевой привязке t = C (до), B является оставшейся третьей привязкой и предполагается, что t ≠ f. Во-первых, обратите внимание, что проблема является симметричной для перестановок имен штифтов (симметрическая группа S 3 ). Если известно решение перехода от привязки 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, но не включая h. Следовательно, диск 0 - самый маленький, а диск h - 1 - самый большой.

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

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

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

Рекурсивная реализация

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

A = [3, 2, 1] B = C = def move (n, source, target, a secondary): if n>0: # Переместить n - 1 диск из источника во вспомогательный, чтобы они были вне way move (n - 1, source, a secondary, target) # Переместите n-й диск из источника в целевой target.append (source.pop ()) # Отобразите наш прогресс print (A, B, C, '##### ######### ', sep =' \ n ') # Переместите n - 1 дисков, которые мы оставили на вспомогательном перемещении, на целевое перемещение (n - 1, вспомогательное, целевое, исходное) # Инициируйте вызов от источника A для целевой C с помощью вспомогательного перемещения B (3, A, C, B)

Следующий код реализует больше рекурсивных функций для текстовой анимации:

время импорта A = [i for i in range (5, 0, -1)] height = len (A) - 1 # Стабильное значение высоты для анимации B = C = def move (n, source, target, a вспомогательный): if n>0: # Перемещение n - 1 диска из исходного во вспомогательный, поэтому они не мешают move (n - 1, source, a secondary, target) # Переместите n-й диск из источника в целевой target.append (source.pop ()) # Отобразите наш прогресс, используя рекурсивную функцию для его отрисовки из розыгрыша _disks (A, B, C, height) print ("") # Задайте интервал time.sleep (0.3) # Сделайте паузу для анимации # Переместите n - 1 дисков, которые мы оставили на вспомогательном перемещении, на целевое перемещение (n - 1, a secondary, target, source) def draw_disks (A, B, C, position, width = 2 * int (max (A))): # параметр ширины по умолчанию равен удвоению самого большого размера диска в начальной башне. if position>= 0: # Если A имеет значение в списке в данной позиции, создать диск в его позиции (высоте) valueInA = "" if position>= len (A) else create_disk (A [position]) # То же самое для B и C valueInB = "" if position>= len (B) else create_disk (B [position]) valueInC = "" if position>= len (C) else create_disk (C [position]) # Распечатать каждую строку print ("{0: ^ {width}} {1: ^ {width}} {2: ^ {width}}". Format (valueInA, valueInB, valueInC, width = width)) # Рекурсивно вызывать этот метод снова для следующего position (height) draw_disks (A, B, C, position - 1, width) else: # После выполнения с рекурсивным методом распечатайте метки столбцов print ("{0: ^ {width}} {1: ^ {width}} {2 : ^ {width}} ". format (" A "," B "," C ", width = width)) def create_disk (size):" "" Простой рекурсивный метод создания наклонного диска. "" "if size == 1: return "/ \\" else: return "/" + create_disk (size - 1) + "\\" # Инициировать вызов от источника A к цели C с помощью вспомогательного перемещения B (len (A), A, C, B)

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

Список ходов для несущей башни Перемещение с одного стержня на другой, как результат рекурсивного алгоритма, имеет много закономерностей. При подсчете ходов, начиная с 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.

Bin обычное решение

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

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

Например, в 8-disk Hanoi:

Move 0 = 00000000.
- Самый большой диск равен 0, поэтому он находится на левой (начальной) привязке.
- Все остальные диски также равны 0, поэтому они уложены поверх него. Следовательно, все диски находятся на начальной привязке.
Переместить 2 - 1 = 11111111.
- Самый большой диск равен 1, поэтому он находится на средней (последней) привязке.
- Все остальные дисков тоже 1, так что они на него укладываются. Следовательно, все диски находятся на последнем штифте, и головоломка завершена.
Переместите 216 10 = 11011000.
- Самый большой диск равен 1, поэтому он находится в середине (последний) привязка.
- Второй диск также равен 1, поэтому он размещен поверх него, на среднем стержне.
- Диск 3 равен 0, поэтому он находится на другом стержне. Поскольку n нечетно (n = 1), это одна привязка слева, т.е. на левой привязке.
- Четвертый диск равен 1, поэтому он находится на другой привязке. Поскольку n нечетное (n = 1), он находится на один стерженьслева, то есть на правом стержне.
- Пятый диск также равен 1, поэтому он кладется поверх него, на правом стержне.
- Шестой диск равен 0, поэтому он находится на другой привязке. Поскольку n четное (n = 2), диск находится на один колышек вправо, то есть на левом колышке.
- Диски седьмой и восьмой также равны 0, поэтому они укладываются на него сверху, на левая привязка.

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

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

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

Решение кода Грея

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

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

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

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

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

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

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

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

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

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

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

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

Для трех дисков график выглядит следующим образом:

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

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

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

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

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

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

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

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

Графики ясно показывают, что:

Из любого произвольного распределения дисков существует ровно один кратчайший способ переместить все диски на один из трех колышков.
Между каждой парой произвольных распределений дисков есть один или два разных кратчайших пути.
Из каждого произвольного распределения дисков есть один или два разных самых длинных не самопересекающиеся пути для перемещения всех дисков на один из трех стержней.
Между каждой парой произвольных распределений дисков есть один или два разных самых длинных несамопересекающихся пути.
Пусть N h - количество несамопересекающихся путей для перемещения башни из h дисков с одного стержня на другой. Тогда:
- N1= 2
- Nh + 1 = (N h) + (N h)

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

Вариациях

Смежные колышки

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

Cyclic Hanoi

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

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

переместите n - 1 диск против часовой стрелки на целевую привязку
переместите диск # n на один шаг по часовой стрелке
переместить n - 1 дисков по часовой стрелке на начальную точку
переместить диск #n на один шаг по часовой стрелке
переместить n - 1 диск против часовой стрелки к целевой привязке

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

переместите n - 1 диск против часовой стрелки на запасную привязку
переместить диск №n на один шаг по часовой стрелке
переместить n - 1 диск против часовой стрелки к целевой привязке

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

C (n) = A (n-1) n A (n-1) и A (n) = A (n-1) n C (n-1) n A (n-1).

Таким образом, C (1) = 1 и A (1) = 1 1, C (2) = 1 1 2 1 1 и A (2) = 1 1 2 1 2 1 1.

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

1) Шаблоны перемещений при перемещении башни дисков с колышка на другой колышек симметричны относительно центральных точек.

2) Самый маленький диск - это первый и последний диск, который нужно переместить.

3) Группы наименьших перемещений диска чередуются с одиночными перемещениями других дисков.

4) Количество перемещений дисков, заданное C (n) и A (n), минимально.

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

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

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

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

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

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

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

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

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

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

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

Этот алгоритм (с указанным выше выбором для $k {\ displaystyle k}$ $k$ ) считается оптимальным для любого количества привязок; его количество ходов равно 2 (при фиксированном r).

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

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

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

466 885 ⋅ 2 n - 1 3 - 3 5 ⋅ (1 3) п + (12 59 + 18 1003 17) (5 + 17 18) п + (12 59-18 1003 17) (5-17 18) п. {\ 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}.}

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

Magnetic Hanoi

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

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

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

Этот вариант знаменитой головоломки Ханойская башня был предложен ученикам 3–6 классов в 2ème Championnat de France des Jeux Mathématiques et Logiques, состоявшаяся в июле 1988 года.

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

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

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

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

Применения

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

Чжан и