Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Модельный набор Ханойской башни (с 8 дисками)
Анимированное решение головоломки Ханойская башня для T (4, 3)
Интерактивный дисплей Ханойской башни в музее Универсум в Мехико

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

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

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

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

Истоки [ править ]

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

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

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

Решение [ править ]

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

Итерационное решение [ править ]

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

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

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

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

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

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

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

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

Эквивалентное итеративное решение [ править ]

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

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

  • Если n нечетное, первое движение - от привязки A к привязке C.
  • Если n четное, первый шаг - от привязки A к привязке B.

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

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

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

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

Рекурсивное решение [ править ]

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

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

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

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

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

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

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

Логический анализ рекурсивного решения [ править ]

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

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

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

Рекурсивная реализация [ править ]

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

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

Бинарное решение [ править ]

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

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

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

  • Переместите 0 = 00000000.
    • Самый большой диск равен 0, поэтому он находится на левом (начальном) колышке.
    • Все остальные диски тоже равны 0, поэтому они кладутся на него сверху. Следовательно, все диски находятся на начальном штифте.
  • Переместите 2 8 - 1 = 11111111.
    • Самый большой диск - 1, поэтому он находится на среднем (последнем) стержне.
    • Все остальные диски тоже по 1, поэтому они ставятся на него стопкой. Таким образом, все диски находятся на последнем штифте, и головоломка завершена.
  • Переместите 216 10 = 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 конечные нули счетчика номеров дисков перемещаются на минимально возможное расстояние до вправо (при необходимости повернув влево). [9]

Решение с кодом Грея [ править ]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Варианты [ править ]

Смежные колышки [ править ]

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

Циклический Ханой [ править ]

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

Чтобы переместить 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) и 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.

Решение для Cyclic Hanoi имеет несколько интересных свойств:

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

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

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

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

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

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

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

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

По поводу других вариантов задачи о Ханойской башне с четырьмя колышками см. Обзорную статью Пола Стокмейера. [16]

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

Алгоритм Фрейма – Стюарта [ править ]

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

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

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

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

Весь процесс требует ходов. Следовательно, следует выбирать количество, для которого это количество минимально. В случае с четырьмя стержнями оптимальное равенство , где - ближайшая целочисленная функция . [18] Например, в курсе UPenn CIS 194 по Haskell на первой странице назначения [19] указано оптимальное решение для случая с 15 дисками и 4 привязками как 129 шагов, которое получается для указанного выше значения k .

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

Общие кратчайшие пути и числа 466/885 [ править ]

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

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

При достаточно большом n только первый и второй члены не сходятся к нулю, поэтому мы получаем асимптотическое выражение :, as . Таким образом, интуитивно мы могли бы интерпретировать долю как отношение трудозатрат, которые нужно выполнить при переходе от случайно выбранной конфигурации к другой случайно выбранной конфигурации, относительно сложности пересечения «наиболее трудного» пути длины, который включает перемещение всех дисков с одного стержня на другой. Альтернативное объяснение появления константы 466/885, а также новый и несколько улучшенный алгоритм вычисления кратчайшего пути дал Ромик. [23]

Магнитный Ханой [ править ]

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

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

Двухцветные башни Ханоя [ править ]

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

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

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

Ханойская башня [ править ]

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

Приложения [ править ]

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

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

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

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

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

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

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

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

В популярной культуре [ править ]

В научно - фантастическом рассказе «Теперь Inhale», по Эрик Фрэнк Рассел , [33] человек находится в плену на планете , где местный обычай , чтобы заключенный играть в игру , пока он не выиграл или проиграл до его исполнения. Главный герой знает, что прибытие спасательного корабля может занять год или больше, поэтому он предпочитает играть в Towers of Hanoi с 64 дисками. (Эта история отсылает к легенде о буддийских монахах, играющих в эту игру до конца света.)

В 1966 Докторе Кто история небесного игрушечника , то эпонимы злодей сила врач играть десять части 1,023-ход башня игры Ханой под названием Trilogic Игра с кусочками , образуя форму пирамиды при штабелировании.

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

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

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

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

В Yu-Gi-Oh! VRAINS , хакерская группа под названием «Рыцарь Ханоя» создает структуру под названием «Ханойская башня» в одноименной сети виртуальной реальности VRAINS.

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

См. Также [ править ]

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

Заметки [ править ]

  1. Перейти ↑ Hofstadter, Douglas R. (1985). Метамагические темы: поиск сущности разума и образца . Нью-Йорк: Основные книги. ISBN 978-0-465-04540-2.
  2. ^ Учитель математики . Национальный совет учителей математики. 56 : 84. 1963. ISSN 0025-5769 https://www.google.com/books/edition/The_Mat Mathematics_Teacher/edoVAAAAIAAJ?gbpv=1&bsq=tower+hanoi+pyramid+puzzle . Проверено 9 марта 2021 года .  Отсутствует или пусто |title=( справка )
  3. ^ Hinz, Андреас М .; Клавжар, Санди; Милутинович, Урош; Петр, Цирил (31.01.2013). Ханойская башня - мифы и математика . ISBN 978-3034802369.
  4. ^ Шпицнагель, Эдвард Л. (1971). Избранные темы по математике . Холт, Райнхарт и Уинстон. п. 137 . ISBN 978-0-03-084693-9.
  5. ^ Moscovich, Иван (2001). 1000 игровых идей: головоломки, парадоксы, иллюзии и игры . Рабочий. ISBN 978-0-7611-1826-8.
  6. ^ Петкович, Миодраг (2009). Известные загадки великих математиков . Книжный магазин AMS. п. 197. ISBN 978-0-8218-4814-2.
  7. ^ Трошкин, М. "Судный день наступает: нерекурсивный анализ рекурсивной проблемы Ханойских башен". Фокус . 95 (2): 10–14.
  8. ^ Майер, Герберт; Перкинс, Дон (1984). "Возвращение в башни Ханоя". Уведомления SIGPLAN . 19 (2): 80–84. DOI : 10.1145 / 948566.948573 . S2CID 2304761 . 
  9. ^ Уоррен, Генри С. (2003). «Раздел 5-4: Подсчет конечных нулей.». Восторг хакера (1-е изд.). Бостон Массачусетс: Эддисон-Уэсли. ISBN 978-0-201-91465-8.
  10. ^ Миллер, Чарльз Д. (2000). «Глава 4: Двоичные числа и стандартный код Грея» . Математические идеи (9-е изд.). Эддисон Уэсли Лонгман. ISBN 978-0-321-07607-6. Архивировано 21 августа 2004 года.CS1 maint: bot: original URL status unknown (link)
  11. Перейти ↑ Gros, L. (1872). Теори дю Багенодье . Лион: Эме Вингтринье.
  12. Перейти ↑ Gedeon, TD (1996). «Циклические башни Ханоя: итеративное решение, порожденное преобразованием» . Компьютерный журнал . 39 (4): 353–356. DOI : 10.1093 / comjnl / 39.4.353 .
  13. ^ Bousch, Т. (2014). "La quatrieme tour de Hanoi" (PDF) . Бык. Бельг. Математика. Soc. Саймон Стевин . 21 : 895–912. DOI : 10.36045 / BBMS / 1420071861 . S2CID 14243013 .  
  14. ^ Стюарт, BM; Кадр, ИС (март 1941 г.). «Решение сложной задачи 3819». Американский математический ежемесячник . 48 (3): 216–9. DOI : 10.2307 / 2304268 . JSTOR 2304268 . 
  15. ^ Клавзар, Санди; Милутинови, Уро; Петрб, Цирил (2002). "Вариации на тему" Ханойская башня с четырьмя столбами " (Постскриптум) . Congressus Numerantium . 102 .
  16. ^ Stockmeyer, Пол (1994). "Вариации на тему" Ханойская башня с четырьмя столбами " (Постскриптум) . Congressus Numerantium . 102 : 3–12.
  17. ^ Гертер, Феликс; Роте, Гюнтер (2018-11-14) [2018-08-09, 2017-12, 2017-08-09, 2016-04-22]. "Перечисление кода Грея без петель и Башня Бухареста" (PDF) . Теоретическая информатика . Берлин, Германия. 748 : 40–54. arXiv : 1604.06707 . DOI : 10.1016 / j.tcs.2017.11.017 . ISSN 0304-3975 . S2CID 4014870 . Архивировано (PDF) из оригинала на 2020-12-16 . Проверено 16 декабря 2020 .    [1] (15/18/19/24 страниц)
  18. ^ "Университет Торонто CSC148 Slog" . 5 апреля 2014 . Проверено 22 июля 2015 года .
  19. ^ "UPenn CIS 194 Введение в Haskell Assignment 1" (PDF) . Проверено 31 января 2016 года .
  20. ^ Hinz, A. (1989). «Ханойская башня». L'Enseignement Mathématique . 35 : 289–321. DOI : 10.5169 / уплотнения-57378 .
  21. ^ Чан, Т. (1988). «Статистический анализ башни Ханойской проблемы». Междунар. J. Comput. Математика . 28 (1–4): 57–65. DOI : 10.1080 / 00207168908803728 .
  22. ^ Стюарт, Ян (2004). Другой Fine Math Вы меня Into .. . Курьер Дувр. ISBN 978-0-7167-2342-4.
  23. ^ Ромик, D. (2006). «Кратчайшие пути в графе Ханойской башни и конечных автоматах». Журнал СИАМ по дискретной математике . 20 (3): 610–622. arXiv : математика / 0310109 . DOI : 10.1137 / 050628660 . S2CID 8342396 . 
  24. ^ Прасад Vithal Chaugule (2015). "Рекурсивное решение двухцветной башни Ханойской проблемы" (PDF) . Журнал развлекательной математики (4): 37–48. ISSN 2182-1976 .  
  25. ^ Арнольд, Питер (2003-05-28). Карточные игры для одного . Издательская компания "Стерлинг". ISBN 978-0-600-60727-4.
  26. ^ Хеджес, Сид Г. (2018-03-06). Всеобщая книга увлечений . ISBN компании Read Books Ltd. 978-1-5287-8344-6.
  27. ^ "Ханойская башня терпения (также известная как Ханойская башня терпения)" . bbcmicro.co.uk . Проверено 17 октября 2020 .
  28. ^ а б Инь, Си; Лю, Синьхун; Пан, Юнг-Тин; Уолш, Кэтлин А .; Ян, Хун (4 ноября 2014 г.). «Многослойные ультратонкие палладиевые нанолистовые материалы, похожие на Ханойскую башню». Нано-буквы . 14 (12): 7188–94. Bibcode : 2014NanoL..14.7188Y . DOI : 10.1021 / nl503879a . PMID 25369350 . 
  29. Перейти ↑ Zhang, J (1994). «Представления в распределенных познавательных задачах» (PDF) . Когнитивная наука . 18 : 87–122. DOI : 10.1016 / 0364-0213 (94) 90021-3 .
  30. ^ Чжан, Цзяцзе; Вальджи, Мухаммад Ф. (2011). «TURF: На пути к единой структуре удобства использования EHR» . Журнал биомедицинской информатики . 44 (6): 1056–67. DOI : 10.1016 / j.jbi.2011.08.005 . PMID 21867774 . 
  31. ^ Пиво, SR; Розенберг, Д.Р .; Дик, Э.Л .; Уильямс, Т .; О'Хирн, КМ; Birmaher, B .; Райан, CM (1999). «Нейропсихологическое исследование функции лобной доли у наивных психотропных детей с обсессивно-компульсивным расстройством» . Американский журнал психиатрии . 156 (5): 777–9. doi : 10.1176 / ajp.156.5.777 (неактивен 2021-01-19). PMID 10327915 . CS1 maint: DOI inactive as of January 2021 (link)
  32. ^ Рид, CR; Самптер, диджей; Бикман, М. (январь 2011 г.). «Оптимизация в естественной системе: аргентинские муравьи решают башни Ханоя». J. Exp. Биол . 214 (Pt 1): 50–8. CiteSeerX 10.1.1.231.9201 . DOI : 10,1242 / jeb.048173 . PMID 21147968 . S2CID 18819977 .   
  33. ^ Рассел, Эрик Франк (апрель 1959). «Теперь вдохни». Поразительная научная фантастика .
  34. ^ «Ханойская башня (концепция видеоигры)» . Giantbomb.com . Проверено 5 декабря 2010 .
  35. ^ "Башня Ханоя / Андамиро" . Sega Amusements. Архивировано из оригинала на 2012-03-01 . Проверено 26 февраля 2012 .

Внешние ссылки [ править ]

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