Ханойская башня: частые вопросы

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

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

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

Нет организации, которая утверждала бы рекорды скорости в Ханойской башне, как это есть для кубика Рубика, поэтому заявленные результаты несравнимы и обычно даже не называют число дисков — а только оно и имеет значение. Лучше посчитать: идеальная партия из n дисков — это 2ⁿ − 1 ходов, а опытный игрок держит темп около двух ходов в секунду. Получается примерно четыре секунды на три диска, около девяти минут на десять дисков с их 1023 ходами и около четырёх с половиной часов на 15 дисков с их 32 767. Поле на этом сайте запоминает в браузере ваше наименьшее число ходов для каждого количества дисков и показывает время на экране результата. Калькулятор назовёт время для любого размера.

2ⁿ − 1, и это доказанная нижняя граница, а не лучший известный результат. Трём дискам нужно 7 ходов, четырём — 15, пяти — 31, десяти — 1023, а 15 — 32 767. Доказательство состоит из двух половин: рекурсивный способ достигает этого числа, и ни одно решение не может его улучшить, потому что самый большой диск должен сдвинуться хотя бы раз, а все меньшие диски над ним сначала нужно убрать на свободную башню и потом вернуть обратно. Обе половины доказательства целиком.

T(n) = 2·T(n − 1) + 1, T(0) = 0. Она читается прямо из способа решения: чтобы перенести n дисков, вы убираете n − 1 дисков, переносите один диск и возвращаете те n − 1 дисков, — два меньших решения плюс один ход. Если её развернуть, получится T(n) = 2ⁿ − 1, что можно проверить по индукции: если T(n − 1) = 2ⁿ⁻¹ − 1, то T(n) = 2(2ⁿ⁻¹ − 1) + 1 = 2ⁿ − 1. Решение рекуррентного соотношения шаг за шагом.

Не в вычислительном смысле, несмотря на экспоненциальное число ходов. Алгоритм занимает несколько строк, выбор следующего хода требует постоянного времени, а решение экспоненциально длинное лишь потому, что таков сам ответ: вывести 2ⁿ − 1 ходов меньше чем за 2ⁿ − 1 шагов невозможно. Задача не NP-трудная, и поиск кратчайшего пути между двумя произвольными допустимыми позициями на трёх стержнях тоже решается эффективно. По-настоящему трудна версия с четырьмя стержнями: её оптимальное решение предположили в 1941 году, а доказал это Тьерри Буш лишь в 2014-м. Алгоритм и его стоимость.

Методом Фрейма — Стюарта. С четырьмя стержнями уже не переносят n − 1 дисков одним блоком: выбирают разбиение k, переносят верхние k дисков на свободный стержень, используя все четыре стержня, переносят оставшиеся n − k дисков на цель, используя только три (свободный стержень занят, так что эта часть — классическая головоломка), а затем кладут k дисков сверху. Перебрав все k и взяв лучшее, получают оптимальное число, и оно падает впечатляюще: для 15 дисков — с 32 767 ходов на трёх стержнях до 129 на четырёх. Сыграть в головоломку с четырьмя стержнями.

«Разделяй и властвуй», выраженный через рекурсию. Стандартное решение — одна функция: перенести n − 1 дисков с исходного стержня на свободный, перенести диск n с исходного на целевой, перенести те n − 1 дисков со свободного на целевой, — а базовый случай ничего не делает, когда n становится нулём. Есть равносильный итеративный алгоритм совсем без рекурсии: многократно переносить самый маленький диск на одну башню в постоянном направлении, а затем делать единственный другой допустимый ход. Оба дают в точности одну и ту же последовательность ходов, потому что оптимальное решение единственно. Алгоритм построчно.

Одна рекурсивная функция и три параметра: void hanoi(int n, char from, char to, char via) — если n равно нулю, return; иначе вызовите hanoi(n − 1, from, via, to), выведите ход from → to и вызовите hanoi(n − 1, via, to, from). Вызов — hanoi(3, 'A', 'C', 'B'). Если ходы нужны вызывающему коду, собирайте их в std::vector<std::pair<char, char>> вместо вывода, а n оставьте обычным int: с беззнаковым параметром случайно переданное отрицательное число молча превратится примерно в четыре миллиарда, и рекурсия будет идти до переполнения стека, вместо того чтобы остановиться на простой проверке n &lt; 0. Полная программа на C++ с построчным разбором.

Это два разных применения стека, и их полезно не смешивать. Стержни — это стеки: каждая башня работает по принципу «последним пришёл — первым ушёл», вы трогаете только верхний диск, а ход — это pop с одной башни и push на другую, поэтому проверка правила сводится к одному сравнению с вершиной цели. Отдельно от этого явный стек может заменить рекурсию: положите в него всю задачу (n, from, to, via), затем в цикле снимайте задачу и, если в ней ещё есть диски, кладите её три части в обратном порядке: второй перенос, одиночный ход диска n и первый перенос. Обратный порядок важен, потому что стек первым отдаёт то, что положено последним. Именно это делает за вас среда выполнения языка в рекурсивной версии. Решение совсем без рекурсии.

В ИИ головоломка — это задача поиска, а не формула. Каждое состояние — это распределение дисков по стержням, поэтому их 3ⁿ, а допустимые ходы — рёбра между ними; поиск — в ширину, A* или IDA* с эвристикой вроде числа дисков, ещё не лежащих на целевом стержне, — находит кратчайший путь от начального состояния к цели. Это стандартная тестовая задача со времён General Problem Solver Ньюэлла, Шоу и Саймона, потому что она наглядно показывает анализ средств и целей и разбиение цели на подцели: подцель «переложить самый большой диск» достижима только после выполнения подцели, которая как будто отменяет достигнутое. Заметьте: рекурсивный алгоритм — это не поиск, а известное решение, и он никогда не рассматривает состояние, которое не использует. Та же головоломка как психологическое задание.