Алгоритм «Ханойской башни»

procedure hanoi(n, source, target, spare)
    if n == 0 then
        return
    hanoi(n - 1, source, spare, target)
    move disk n from source to target
    hanoi(n - 1, spare, target, source)
end procedure

На что смотреть

• Роли меняются местами. Башня B — вспомогательная для первого вызова и целевая для того вызова, который он делает. Каждый уровень рекурсии переименовывает три башни, и это переименование и есть весь фокус.
• Стек никогда не становится глубоким. При трёх дисках одновременно выполняется не больше 4 вызовов — по одному на каждое число дисков от 3 до 0, — хотя всего программа делает 15 вызовов.
• Половина вызовов ничего не делает. Из этих 15 вызовов 8 приходятся на ноль дисков и возвращаются сразу. Это цена самого простого базового случая.
• Строка, которая переносит, выполняется ровно 2ⁿ − 1 раз. Семь раз для трёх дисков, на протяжении 43 шагов выполнения.

Первое заметить труднее всего, пока программа работает: когда это происходит, на поле ничего не движется — меняются только имена под башнями. Здесь оно остановлено: первый вызов, два вызова под ним по пути к ходу 1 и вызов, который возвращает стопку обратно.

1. hanoi(3, A, C, B)

   Первый вызов: перенести все диски (3) с A на C. Тогда B остаётся вспомогательной. Исходная A, целевая C, вспомогательная B.

2. hanoi(2, A, B, C)

   Его первый вызов. Диск 3 не сдвинуть, пока на нём лежат диски 1 и 2, а им нельзя на C, куда направляется диск 3. Поэтому B, только что бывшая вспомогательной, становится целевой, а C — вспомогательной. Исходная A, целевая B, вспомогательная C.

3. hanoi(1, A, C, B)

   Уровнем ниже — та же перемена мест. Чтобы освободить диск 2, диск 1 уходит на C, а B снова становится вспомогательной. Исходная A, целевая C, вспомогательная B.

4. hanoi(2, B, C, A)

   Диск 3 уже перешёл. Второй вызов корня возвращает диски 1 и 2 со B поверх него, так что теперь B — исходная башня, а A, где начинали все диски, — вспомогательная. Исходная B, целевая C, вспомогательная A.

Второе легче поставить под сомнение, чем проверить, — поэтому вот всё выполнение целиком, с высотой стека на каждом его шаге:

• Выполнение занимает 43 шагов и делает всего 15 вызовов.
• Число вызовов в стеке колеблется между 0 и 4 и достигает 4 на 8 шагах — каждый раз, когда вызов, которому нечего переносить, начинается и возвращается.
• Глубина 4 — это n + 1 при n = 3, и ни один шаг выполнения её не превышает.

Дерево рекурсии

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

1. Ход 1: вызов с n = 1, с A на C, переносит диск 1.
2. Ход 2: вызов с n = 2, с A на B, переносит диск 2 между двумя своими вызовами с n = 1.
3. Ход 3: вызов с n = 1, с C на B, переносит диск 1.
4. Ход 4: вызов с n = 3, с A на C, переносит диск 3 между двумя своими вызовами с n = 2.
5. Ход 5: вызов с n = 1, с B на A, переносит диск 1.
6. Ход 6: вызов с n = 2, с B на C, переносит диск 2 между двумя своими вызовами с n = 1.
7. Ход 7: вызов с n = 1, с A на C, переносит диск 1.

Эта симметрия сохраняется при любом размере. Ход 2ⁿ⁻¹ — это всегда переход самого большого диска, а ходы до и после — решение для (n − 1) дисков, сыгранное дважды, с переменой ролей двух башен. Поэтому список ходов любой длины читается с одного взгляда, и поэтому решение для пяти дисков — это решение для четырёх, один ход и снова решение для четырёх.

Почему он верен

Алгоритм никогда не нарушает правил и всегда завершается, а доказательство достаточно короткое, чтобы привести его целиком. Утверждение для каждого n такое:

Если верхние n дисков исходной башни — это диски с 1 по n, а любой диск в другом месте больше n, то hanoi(n, source, target, spare) переносит эти n дисков на целевую башню по правилам и не трогает ничего другого.

При n = 0 переносить нечего и ничего не затрагивается.

Пусть утверждение верно для n − 1. Тогда каждый из трёх шагов допустим:

1. Первый вызов переносит диски с 1 по n − 1 на вспомогательную башню. Он вправе это сделать: любой другой диск, включая диск n, больше, чем n − 1.
2. Диск n переходит на целевую башню. Сверху на нём теперь ничего нет, а на целевой лежат только диски, которые больше n.
3. Второй вызов переносит диски с 1 по n − 1 со вспомогательной башни на целевую. Он вправе по той же причине: диск n, оказавшийся под ними, больше.

Все n дисков на целевой башне, и больше ничего не сдвинулось. По индукции утверждение верно для каждого n, а полная головоломка — это случай, когда на исходной башне лежат все диски.

1. Предполагаетсяутверждение для n − 1

   Предположение гласит, что вызов на n − 1 дисках переносит их туда, куда ему сказано, по правилам и не трогает ничего другого. Применённое здесь, оно уносит диски с 1 по n − 1 с исходной башни на вспомогательную. Оно вправе это сделать: любой диск, на который они могли бы лечь, — включая диск n — больше любого из переносимых.

2. Доказывается здесьодин допустимый ход

   Это единственный шаг, который доказательство должно обосновать само, и это один ход. Диск n открыт, потому что предыдущий шаг его освободил. На целевой башне нет ничего, кроме дисков больше n, потому что всё меньшее лежит на вспомогательной. Значит, ход допустим.

3. Предполагаетсяутверждение для n − 1, ещё раз

   То же предположение, использованное во второй раз, приводит диски с 1 по n − 1 со вспомогательной башни на целевую. Допустимо по той же причине, что и раньше: диск n, оказавшийся под ними, больше. Все n дисков на целевой башне, и больше ничего не сдвинулось — а это и есть утверждение для n.

Рекуррента, решённая как надо

Пусть T(n) — число ходов, которые алгоритм делает для n дисков. Функция делает два вызова на n − 1 дисках и один собственный ход, а при отсутствии дисков не делает ходов вовсе:

Чтобы её решить, подставьте рекурренту в саму себя и поищите закономерность. Это называется разворачиванием, или телескопированием:

Увидеть закономерность — не то же самое, что доказать её, так что подтвердите индукцией. T(0) = 0 = 2⁰ − 1. И если T(n − 1) = 2ⁿ⁻¹ − 1, то T(n) = 2(2ⁿ⁻¹ − 1) + 1 = 2ⁿ − 2 + 1 = 2ⁿ − 1. Замкнутая формула точна для каждого n.

Есть и третий путь, и это картинка, которую вы уже видели. Дерево рекурсии выше — полное двоичное дерево: корень переносит n дисков, два вызова под ним — по n − 1, четыре под ними — по n − 2, и так далее. Значит, на глубине k находится 2ᵏ вызовов, последний уровень — это глубина n − 1, и каждый из этих вызовов делает ровно один ход. Сложите уровни — и число выпадает как геометрическая прогрессия:

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

Та же арифметика считает и вызовы. Каждый вызов при n {">"} 0 делает ещё два, поэтому C(n) = 2C(n − 1) + 1 при C(0) = 1, что разворачивается в 2ⁿ⁺¹ − 1. Это 2ⁿ − 1 вызовов, переносящих диск, плюс 2ⁿ, которые сразу возвращаются.

Время и память

Каждый вызов, кроме двух своих рекурсивных вызовов, делает постоянный объём работы, так что время работы пропорционально числу вызовов: Θ(2ⁿ). Никакой более хитрый алгоритм этого не превзойдёт, потому что сам вывод имеет длину 2ⁿ − 1 ходов, а 2ⁿ − 1 — доказанный минимум, а не просто лучшее из найденного. Доказательству того, что короче не бывает, отведена отдельная страница: почему минимум равен 2ⁿ − 1.

С памятью всё иначе. Вызовы не существуют одновременно: один вызов заканчивается прежде, чем начинается его сосед, поэтому стек держит лишь по одному вызову на уровень, от n до 0. Используемое место — Θ(n): шестьдесят пять кадров стека для шестидесяти четырёх дисков легенды, что любой компьютер переносит, не заметив. Кончается именно время: 18 446 744 073 709 551 615 ходов при миллиарде ходов в секунду — это всё равно 584 года.

Это число из легенды, а легенда моложе, чем кажется. Храм, где жрецы перекладывают шестьдесят четыре золотых диска, и конец света по завершении работы впервые появляются в печати в 1884 году — в статье, рекламировавшей головоломку, поступившую в продажу в Париже годом раньше под именем профессора, которого не существовало. В темпе монахов, один ход в секунду, миру остаётся 585 миллиардов лет — примерно в сорок раз больше нынешнего возраста Вселенной. Математиком, стоявшим и за головоломкой, и за историей, был Эдуард Люка: он вручную доказал простоту 2¹²⁷ − 1 и умер в 49 лет от заражения после пореза осколком тарелки, которую официант уронил на банкете.

Подставьте в эти формулы числа — и два вида затрат разойдутся. Каждый лишний диск чуть более чем удваивает ходы и вызовы и добавляет один-единственный кадр к наибольшей глубине стека:

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

Без рекурсии

Те же ходы можно получить обычным циклом с двумя правилами:

• Нечётные ходы: самый маленький диск перемещается на одну башню по неизменному кругу — A → C → B при нечётном числе дисков и A → B → C при чётном.
• Чётные ходы: делайте единственный допустимый ход, не затрагивающий самый маленький диск. Такой ход всегда ровно один.

Эти два правила воспроизводят рекурсивное решение ход в ход; страница итеративного решения показывает почему и проигрывает его на поле.

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

Из позиции, которая не является началом

Учебная функция предполагает, что все диски начинают на исходной башне. Дайте ей недоигранную головоломку — и ей нечего сказать. Ещё один случай это исправляет. Посмотрите на самый большой диск:

• Уже на той башне, куда ему нужно? Ему не нужен ни один ход. Решайте меньшие диски, отправляя их на ту же башню.
• Где-то ещё? Уберите меньшие диски на башню, которая не является ни его нынешней, ни целевой, переместите его и продолжайте как раньше.

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

Проверьте себя

Три вопроса, на которые страница уже ответила. Попробуйте решить их до того, как откроете ответ: если какой-то не даётся, названный в ответе раздел стоит перечитать.

1. Три диска — это семь ходов. Сколько ходов у 5 дисков и сколько из них двигают сам диск 5?

   Показать ответ

   31 ходов, то есть 2⁵ − 1, и ровно один из них двигает самый большой диск. Все диски, кроме самого большого, двигаются больше одного раза, потому что каждая из двух половин решения обязана их переносить. Рекуррента, решённая как надо.

2. hanoi(3, A, C, B) делает первым вызовом hanoi(2, A, B, C). Почему целевая башня этого вызова — B, а не C?

   Показать ответ

   Потому что диск 3 идёт на C и может лечь туда, только если C пуста. Значит, два диска над ним надо где-то пристроить, а это «где-то» только одно — B. Башня, на которую нацелен вызов, становится той башней, которую его первый вызов обязан держать свободной, — поэтому два из трёх аргументов при входе меняются местами. На что смотреть.

3. Решение для 20 дисков делает 2 097 151 вызовов. Сколько из них одновременно находятся в стеке, самое большее?

   Показать ответ

   21 — по одному на каждое число дисков от 20 до 0. Вызов заканчивается прежде, чем начинается его сосед, поэтому все вызовы никогда не существуют одновременно: работа экспоненциальна, а память линейна. Время и память.

Алгоритм на вашем языке

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

• «Ханойская башня» на PythonENRecursive and iterative programs, why Python's recursion limit never bites here, and integers that simply do not overflow.
• «Ханойская башня» на JavaScriptENWhy 2 ** 64 − 1 prints the wrong number, BigInt, and a generator that hands out one move at a time.
• «Ханойская башня» на JavaENWhy (1L << 64) − 1 is zero, counting with BigInteger, and the same solution driven by an explicit stack.
• «Ханойская башня» на CENUndefined shifts, uint64_t, and a loop that reads every move straight off the bits of the move number.
• «Ханойская башня» на C++ENCollecting the moves in a std::vector, the 64-disk count checked by the compiler, and three pairs of towers in a loop.
• «Ханойская башня» на C#ENTop-level statements, an iterator whose moves LINQ can query, and ulong, checked arithmetic and UInt128 for the move count.

Слова этой страницы

Базовый случай

Та версия задачи, на которую рекурсивная функция отвечает сразу, не вызывая себя. Именно он останавливает рекурсию. Здесь это n = 0: переносить нечего, значит, делать нечего, и вызов возвращается. Любая цепочка вызовов, какой бы глубокой она ни была, заканчивается на одном из них.

Рекурсивный случай

Всё, что не базовый случай: часть функции, которая решает меньшую версию той же задачи и строит из неё свой ответ. Здесь это три строки, которые убирают с дороги n − 1 дисков, переносят диск n и возвращают эти n − 1 обратно.

Стек вызовов

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

Кадр стека

Одна запись в стеке вызовов: аргументы и локальные переменные одного вызова. Каждая строка стека в панели — это кадр со своим n и своим представлением о том, какая башня исходная, какая целевая, а какая вспомогательная. Шестидесяти четырём дискам нужно шестьдесят пять кадров — это пустяк; проблема в числе ходов.

Телескопирование

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

Θsaid “большая тета”

Скорость роста, которая является одновременно верхней и нижней оценкой: Θ(2ⁿ) означает, что затраты растут как 2ⁿ, а не просто не быстрее, чем 2ⁿ. O(2ⁿ) обещало бы только потолок. Здесь честная запись — Θ, потому что этот алгоритм действительно делает 2ⁿ − 1 ходов: ему не может повезти закончить раньше.

Частые вопросы

Как работает рекурсивный алгоритм «Ханойской башни»?

Чтобы перенести n дисков с исходной башни на целевую, он сначала переносит верхние n − 1 дисков на вспомогательную башню, затем переносит самый большой диск на целевую, затем переносит n − 1 дисков со вспомогательной на целевую. Каждый из этих двух меньших переносов — та же задача с одним диском меньше, поэтому функция вызывает для них саму себя, а вызов, которому нечего переносить, просто возвращается.

«Ханойская башня» — это разделяй и властвуй или динамическое программирование?

Это разделяй и властвуй. Задача делится на две подзадачи по n − 1 дисков, каждая решается рекурсией, а шаг соединения — один-единственный ход самого большого диска. Это не динамическое программирование, и мемоизация не помогает — хотя подзадачи действительно повторяются. При трёх башнях есть всего шесть способов назвать исходную, целевую и вспомогательную, так что hanoi(1, A, C, B) при решении трёх дисков действительно вызывается дважды. Кэшировать это бессмысленно: ответ на подзадачу — список из 2ᵏ − 1 ходов, а проиграть сохранённый список такой длины стоит столько же, сколько его получить. Здесь работа и есть вывод, и никакая таблица вывод не укоротит.

Применима ли к рекурренте «Ханойской башни» основная теорема?

Нет. Основная теорема охватывает соотношения вида T(n) = aT(n/b) + f(n), где каждая подзадача — доля исходной. Рекуррента «Ханойской башни» — это T(n) = 2T(n − 1) + 1: подзадача меньше на один диск, а не в несколько раз. Разворачивание сразу даёт T(n) = 2ⁿ − 1, а индукция это подтверждает.

Насколько глубокой становится рекурсия?

При базовом случае n = 0 в стеке одновременно находится не более n + 1 вызовов: по одному на каждое число дисков от n до 0. При базовом случае n = 1 их n. И в том и в другом случае глубина растёт линейно — поэтому рекурсивному решению нужно лишь O(n) памяти, хотя ходов оно делает экспоненциально много.

Сколько вызовов функции делает рекурсивное решение?

2ⁿ⁺¹ − 1 вызовов, когда базовый случай — n = 0: 2ⁿ − 1 вызовов, переносящих диск, плюс 2ⁿ вызовов, которые ничего не находят и возвращаются. Три диска дают 15 вызовов. Если написать с базовым случаем n = 1, та же программа сделает ровно 2ⁿ − 1 вызовов — по одному на ход.

Итеративный алгоритм быстрее рекурсивного?

Не настолько, чтобы это имело значение. Оба обязаны выдать 2ⁿ − 1 ходов, так что оба тратят время, пропорциональное 2ⁿ. Итеративная версия избавляется от стоимости вызовов функций и не может исчерпать стек, но рекурсия здесь уходит вглубь всего на n уровней: исчерпание стека не является реальным риском ни при каком числе дисков, которого вы дождались бы.

Как выглядит алгоритм «Ханойской башни» в виде блок-схемы?

Почти никак — и это честный ответ. Блок-схема показывает, как управление один раз проходит по блокам, а второй блок этого алгоритма — это вся блок-схема заново: тремя уровнями ниже, с двумя переставленными башнями и одним диском меньше. У блок-схемы нет для этого обозначений, поэтому блок-схема рекурсивного решения либо неверна, либо это картинка одного вызова с двумя блоками «вызвать hanoi», которая не учит ничему сверх четырёх строк псевдокода. Схема, которая это выражает, — дерево рекурсии: каждый вызов нарисован под тем вызовом, который его сделал, и каждый прямоугольник стоит над ходом, который он делает. Оно есть на этой странице, и если читать его прямоугольники слева направо, получаются ходы по порядку.

Может ли алгоритм решить головоломку, начатую наполовину?

Учебная версия не может: она предполагает, что все диски начинают на одной башне. Она обобщается одним дополнительным случаем — если самый большой диск уже на своей целевой башне, пропустите его и решайте диски над ним, — и эта версия находит кратчайшее решение из любой допустимой позиции. Решатель этого сайта выполняет именно её. Открыть решатель →