Задача Ханойских башен — одна из самых первых задач, которые предлагаются начинающим программистам, в основном, чтобы проиллюстрировать концепцию рекурсивных решений. В этой статье приводится метод, который позволяет теоретическим путем, без рекурсии, указывать оптимальное решение для текущего хода.
"Ханойская башня" является одной из популярных головоломок XIX века. Даны три стержня, на один из которых нанизаны восемь колец, причем кольца отличаются размером и лежат меньшее на большем. Задача состоит в том, чтобы перенести пирамиду из восьми колец за наименьшее число ходов на другой стержень. За один раз разрешается переносить только одно кольцо, причём нельзя класть большее кольцо на меньшее.
Классическое решение данной задачи с тремя стержнями предполагает, что для заданного количества колец n количество перекладываний вычисляется по формуле
.
Дополнительную привлекательность данной задаче придаёт и сопровождающая её легенда:
В Великом храме города Бенарес, под собором, отмечающим середину мира, находится бронзовый диск, на котором укреплены 3 алмазных стержня, высотой в один локоть и толщиной с пчелу. Давным-давно, в самом начале времён, монахи этого монастыря провинились перед богом Брахмой. Разгневанный Брахма воздвиг три высоких стержня и на один из них возложил 64 диска, сделанных из чистого золота. Причем так, что каждый меньший диск лежит на большем. Как только все 64 диска будут переложены со стержня, на который Брахма сложил их при создании мира, на другой стержень, башня вместе с храмом обратятся в пыль и под громовые раскаты погибнет мир.
Между делом новичку предлагается оценить сложность данного решения, чтобы впечатлить результатом: число перемещений дисков, которые должны совершить монахи, равно 18 446 744 073 709 551 615. Если бы монахи, работая день и ночь, делали каждую секунду одно перемещение диска, их работа продолжалась бы 584 миллиарда лет.
Суть решения сводится к пониманию того, что для перемещения текущего диска необходимо решить задачу по переносу всех предыдущих дисков на свободный стержень, перемещению требуемого диска и последующему обратному перемещению всех предыдущих дисков меньшего размера на нужный стержень. Таким образом, решение задачи сводится к предыдущим решениям, что и иллюстрирует механизм рекурсии.
Александр Бусаров MrShoor написал очень информативный пост, отлично дополняющий соответствующую статью в Википедии, с очень подробным программным кодом, рекомендую ознакомиться с его реализацией рекурсии.
В том же посте имеется описание фрактальной природы алгоритма. Я попытаюсь продолжить это направление, раскрыв применение кода Грея для данной конкретной задачи.
Приведу цитату из соответствующей статьи в Википедии:
Коды Грея применяются в решении задачи о Ханойских башнях. Пусть N — количество дисков. Начнём с кода Грея длины N, состоящего из одних нулей (то есть G(0)), и будем двигаться по кодам Грея (от G(i) переходить к G(i+1)). Поставим в соответствие каждому I-ому биту текущего кода Грея I-ый диск (причём самому младшему биту соответствует наименьший по размеру диск, а самому старшему биту — наибольший). Поскольку на каждом шаге изменяется ровно один бит, то мы можем понимать изменение бита I как перемещение I-го диска. Заметим, что для всех дисков, кроме наименьшего, на каждом шаге имеется ровно один вариант хода (за исключением стартовой и финальной позиций). Для наименьшего диска всегда имеется два варианта хода, однако имеется стратегия выбора хода, всегда приводящая к ответу: если N нечётно, то последовательность перемещений наименьшего диска имеет вид f->t->r->f->t->r->… (где f-стартовый стержень, t-финальный стержень, r-оставшийся стержень), а если N чётно, то f->r->t->f->r->t->...
Оптимальное решение задачи сводится к определению положения дисков после очередного хода. В самом начале (при нулевом ходе) все диски находятся на одном и том же стартовом стержне f. Нумерация весов дисков осуществляется с номера 1 по возрастанию. Требуется описать положение дисков на ходе с номером m.
Очевидно, что при оптимальном решении после хода m количество перемещаемых дисков n будет не более
(1).
Остальные диски большего размера можно не брать в расчёт, что очень удобно при более общем предположении о бесконечном количестве дисков в начальной задаче с тремя стержнями.
Далее, определившись с количеством перемещенных дисков, определимся с их положением.
Ввиду фрактальности решения, которое описывалось в упомянутых выше источниках, становится очевидным, что благодаря "вложенности" решений друг в друга просматривается связь между двоичным кодом номера хода и номером перемещаемого диска.
В частности, во время данного хода перемещается тот диск, чей "вес" i коррелирует с максимальной степенью двойки в двоичном разложении номера m текущего хода минус единицу:
(2).
В той же нотации Pascal/Delphi, которую использует MrShoor в своем коде, это может быть записано следующим образом:
i:=0;
deg2value:=1;
while ((m mod deg2value) = 0)) do
begin
i:=i+1;
deg2value:=deg2value*2;
end;Таким образом, для каждого из дисков с весом i мы можем определить тот ход j, на котором диск данного веса был перемещен последний раз:
.
Код для определения номера хода num_move последнего перемещения диска с весом i может выглядеть подобным образом (с условием включения модуля Math):
deg2value:=Power(2,i-1);
q_move:=m div deg2value;
if (q_move mod 2) = 0 then q_move:=q_move-1;
num_move:=i_move * deg2value;
q_move=(q_move+1) div 2;Стоит обратить внимание на тот факт, что попутно в переменной q_move получено количество перемещений диска с весом i с начала игры.
Итак, в промежуточном итоге, мы знаем, сколько раз каждый диск был перемещен в течение игры после каждого хода. Теперь определимся с тем, куда перемещался каждый из дисков.
Как отмечено в Википедии, перемещение верхнего диска циклично и, при выборе определенного стержня назначения t, если N нечётно, то последовательность перемещений наименьшего диска имеет вид f->t->r->f->t->r->… (где f-стартовый стержень, t-финальный стержень, r-оставшийся стержень), а если N чётно, то f->r->t->f->r->t->…
Вспоминая о фрактальности, можно заметить, что если отбросить верхнюю часть предшествующих дисков, то текущий диск также совершает подобное циклическое движение во время своих собственных ходов. Учитывая этот факт, становится очевидным, что в зависимости от четности номера диска, цикл перемещения нечетного диска совпадает с циклом перемещения первого диска, а цикл перемещения четных дисков разнится очередностью стержней t и r.
В частности, зная количество перемещения q_move и четность номера текущего диска, можно простым делением на 3 по остатку определить последний стержень, куда был перемещен данный диск.
Следовательно, имея на входе общее количество дисков N, выбранный стержень назначения t и номер текущего хода m, можно восстановить положение всех дисков при оптимальном решении без обращения к рекурсивным алгоритмам.
Для тех, кому интересны вариации задачи Ханойских башен, в частности, случаи 4 и более стержней, предлагаю ознакомиться с опытом PapaBubaDiop, развивающего данное направление в виде игр, попутно пытаясь монетизировать некоторые версии на различных платформах.
Надеюсь, что тем из читателей, которым интересны теоретические решения, более оптимизированные для подобных задач с большим количеством входных данных и затрачиваемых вычислительных ресурсов, эта публикация пригодится в дальнейшем в качестве базиса для собственных результатов.
Стиль и язык немного суховаты и годятся скорее для академических работ, потому прошу не судить особо строго, особенно с учетом попытки выправить карму и выбраться из минуса. Всем всего наилучшего и светлого, с Новым 2017 Годом: успехов и удач во всем хорошем!
Автор: arsmagic
