Задача Ханойских башен — одна из самых первых задач, предлагаемых начинающим программистам, главным образом для иллюстрации концепции рекурсивных решений.
В данной статье представлен метод, позволяющий теоретически, без рекурсии, указать оптимальное решение для текущего хода.
Ханойская башня – одна из популярных головоломок 19 века.
Даны три стержня, на один из которых нанизано восемь колец, причем кольца различаются по размеру и на большем лежат меньшего размера.
Задача — за наименьшее количество ходов перенести пирамиду из восьми колец на другой стержень.
Одновременно разрешается носить только одно кольцо, кольцо большего размера нельзя размещать на меньшем.
Классическое решение этой задачи с тремя стержнями предполагает, что для заданного числа колец н количество смен рассчитывается по формуле
.
Сопровождающая легенда делает эту проблему еще более привлекательной:
В Великом храме города Бенареса, под собором, обозначающим середину мира, находится бронзовый диск, на котором закреплены 3 алмазных стержня высотой в один локоть и толщиной с пчелу.Давным-давно, в самом начале времен, монахи этого монастыря совершили оскорбление перед богом Брахмой.
Разгневанный Брахма воздвиг три высоких стержня и поместил на один из них 64 диска из чистого золота.
При этом каждый меньший диск лежит на большем.
Как только все 64 диска будут перенесены с жезла, на который Брахма поместил их при создании мира, на другой жезл, башня вместе с храмом превратятся в пыль и мир погибнет под раскатами грома.
А пока новичку предлагается оценить сложность этого решения, чтобы впечатлиться результатом: число движений диска, которое должны совершить монахи, равно 18 446 744 073 709 551 615 .
Если бы монахи, работая день и ночь, совершали одно движение диска каждую секунду, их работа продолжалась бы.
584 миллиарда годы.
Суть решения сводится к пониманию того, что для перемещения текущего диска необходимо решить задачу о переводе всех предыдущих дисков на свободный стержень, перемещении необходимого диска, а затем перемещении обратно всех предыдущих дисков меньшего размера на свободный стержень.
нужный стержень.
Таким образом, решение задачи сводится к предыдущим решениям, что иллюстрирует рекурсивный механизм.
Александр Бусаров г-нШур написал очень информативно быстрый , прекрасно дополняющий соответствующий Статья в Википедии , с очень подробным программным кодом, рекомендую ознакомиться с его реализацией рекурсии.
В этом же посте есть описание фрактальной природы алгоритма.
Я постараюсь продолжить это направление, раскрыв применение кода Грея для этой конкретной проблемы.
Позволю себе процитировать соответствующую статью в Википедии:
Коды Грея используются для решения проблемы Ханойских башен.Оптимальное решение задачи сводится к определению положения дисков после очередного хода.Пусть 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. Веса дисков нумеруются с цифры 1 в порядке возрастания.
Требуется описать положение дисков на такте с номером м .
Очевидно, что при оптимальном решении после хода м количество дисков, которые нужно переместить н больше не будет
(1) .
Остальными более крупными дисками можно пренебречь, что очень удобно в более общем предположении о бесконечном числе дисков в исходной задаче с тремя стержнями.
Далее, определившись с количеством перемещаемых дисков, определим их положение.
Ввиду фрактальной природы решения, которая была описана в упомянутых выше источниках, становится очевидным, что за счет «вложенности» решений друг в друга видна связь между двоичным кодом номера хода и числом перемещаемого диска.
В частности, во время данного хода перемещается диск, «вес» которого я коррелирует с максимальной степенью двойки в двоичном представлении числа м текущий ход минус один:
(2) .
В тех же обозначениях Паскаль/Делфи использует г-нШур в вашем коде это можно было бы написать так:
Таким образом, для каждого из дисков весом я мы можем определить этот ход дж , на котором последний раз перемещался диск этого веса:i:=0; deg2value:=1; while ((m mod deg2value) = 0) do begin i:=i+1; deg2value:=deg2value*2; end;
.
Код для определения номера хода num_move последнее движение грузового диска я может выглядеть так (при условии, что включен модуль 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:=q_move * deg2value;
q_move=(q_move+1) div 2;
Стоит обратить внимание на то, что переменная q_move одновременно содержит количество движений диска с весом я с начала игры.
Итак, в промежуточном итоге мы знаем, сколько раз каждый диск был передвинут во время игры после каждого хода.
Теперь определим, куда переместился каждый из дисков.
Как отмечено в Википедии, движение верхнего диска циклично и при выборе конкретного назначения стержня t, если N нечетно, то последовательность движений наименьшего диска f-> t-> r-> f-> t-> r-> .
(где f-начальный стержень, t-конечный стержень, r-остальный стержень), а если N четное, то f-> r-> t-> f-> r-> t -> .
Вспоминая фрактальность, можно увидеть, что если отбросить вершину предыдущих дисков, то текущий диск также совершает аналогичное циклическое движение во время своих собственных ходов.
Учитывая этот факт, становится очевидным, что в зависимости от четности номера диска цикл движения нечетного диска совпадает с циклом движения первого диска, а цикл движения четных дисков отличается порядком стержни т и р.
В частности, зная величину перемещения q_move и четность номера текущего диска, можно просто разделить на 3 с остатком, чтобы определить последний стержень, куда этот диск был перемещен.
Следовательно, зная на входе общее количество дисков N, выбранный целевой стержень t и номер текущего хода m, можно восстановить положение всех дисков для оптимального решения, не прибегая к рекурсивным алгоритмам.
Тем, кого интересуют варианты задачи «Ханойские башни», в частности случаи с 4 и более стержнями, предлагаю ознакомиться с опытом.
ПапаБубаДиоп , развиваем это направление в виде игр, при этом пытаясь монетизировать некоторые версии на различных платформах.
Надеюсь, что те читатели, которых интересуют теоретические решения, более оптимизированные для аналогичных задач с большим количеством входных данных и затраченными вычислительными ресурсами, найдут эту публикацию полезной в будущем как основу для собственных результатов.
Стиль и язык немного суховаты и больше подходят для академической работы, поэтому прошу не судить слишком строго, особенно учитывая попытку исправить карму и выйти из минуса.
Всем всего самого доброго и светлого, с Новым 2017 годом: успехов и удачи во всем хорошем! UPD: Спасибо всем за комментарии, замечания и советы.
Пример скрипта, работающего по приведенному выше алгоритму, доступен по адресу эта ссылка .
Для обеспечения работы с большими числами использовалась библиотека GMP. Теги: #Ханойская башня #алгоритм #теория игр #теоретическое решение #теория #формулы #программирование #Алгоритмы #математика
-
Микротик Мап Лайт
19 Oct, 24 -
Офис Внутри Яйца
19 Oct, 24 -
Импакт-Инвестиции В Атомную Отрасль
19 Oct, 24 -
Позиционирование
19 Oct, 24 -
Поддержка Razor В Visual Studio Code
19 Oct, 24
