SoftCraft
разноликое программирование

Top.Mail.Ru

В лабиринтах Ханойских башен

Примеры программ к статье (6,5 кб)

© 2002 г. Александр Легалов

(опубликовано в журнале «Программист» № 11/2002)

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

Введение

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

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

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

  • Итеративные алгоритмы опираются на простое условие при выборе стержня, используемого для переноса любого диска. Оно зависит от четности дисков башни и номера текущего диска [2]. Простота действий ведет к вполне резонному вопросу: почему сложность и размер всех итерационных алгоритмов оказывается намного больше по сравнению с рекурсивным решением [3]?

Что показывает рекурсия

Приводимый практически во всех источниках рекурсивный алгоритм описывает лишь одно полезное действие: перекладывание диска с одной оси на другую. При этом отсутствует какая-либо манипуляция с дополнительной памятью кроме передачи параметров, однозначно переставляемых при каждом вызове. Это наводит на мысль, что основной задачей рекурсии является динамическое определение того, на какой стержень переложить самый верхний диск при выполнении первого шага. Остальные переносы дисков однозначно зависят от этого выбора. Рекурсивное порождение и автоматический обход позволяют не задумываться об общем количестве шагов, равном 2N-1, где N – количество дисков. Это позволяет без каких-либо проблем и дополнительных ухищрений запускать программу с исходным числом дисков, значительно, превышающим число, определяющее достижение результата за разумный интервал времени (на компьютере с 512 Мб памяти мне удалось запустить программу, осуществляющую перебор 32454 дисков). Следует отметить и то, что размер дисков является несущественным для решения задачи. Программа будет точно также работать при переносе с место на место столбиков из одинаковых монет.

О виде рекурсии

Одним из интересных моментов, рассмотренных в работе [2], для меня явилось сведение рекурсии к итерации без использования дополнительной памяти (во втором примере). Известно, что таким свойством обладают лишь «концевые» рекурсии. Поэтому вполне естественным является вопрос: как подобное могло случиться? Ответ можно найти, если дополнительно изучить специфику рекурсивного решения.

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


Построить башню  =
    Построить башню
    Перенести диск с одного стержня на другой
    Построить башню.

Таким образом, имеются две «концевые», а не «внутренние» рекурсии, которые легко сводятся к итерациям: 


Построить башню  =
    Заданное число раз, а именно: 2N-1
         Перенести диск с одного стержня на другой

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

Параметрическое решение

Для того чтобы реализовать рассмотренное выше итеративное решение, достаточно получить формулы, определяющие исходный и приемный стержни в зависимости от номера шага. Не сомневаюсь, что подобные формулы уже существуют в готовом виде. Самое близкое, что я сумел найти, представлено в источнике [5]. Однако предлагаемый в нем алгоритм ориентируется на анализ относительных размеров диска и не определяет прямую зависимость от итераций. Поэтому пришлось провести собственное небольшое расследование.

Достаточно легко получить связь между номером итерации i и перекладываемым диском k. Оно зависит от числа делений i на 2 без остатка. Поэтому без особых проблем можно выявить, что номер перекладываемого диска равен количеству нулей в двоичном представлении номера итерации i, предшествующих самой младшей единице, плюс один. Алгоритмически подобный подсчет можно осуществить операцией сдвига вправо до тех пор, пока результат сдвига станет нечетным.

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

  • диски перекладываются со стержня на стержень с разными шагами, но по модулю 3, что определяется использованием трех стержней;

  • если четность (нечетность) общего числа дисков в башне совпадает с четностью (нечетностью) перекладываемого диска, то используется шаг, равный минус 1 или его положительный эквивалент, равный 2. В противном случае шаг равен плюс 1.

Зная номер диска k и количество проделанных итераций i, без труда можно выяснить, в который раз перекладывается искомый диск. Умножив это и предшествующее ему числа на шаг t (не забывая «ужать» результат по модулю 3), получим номера принимающего и исходного стержней.

Ниже приведена программа соответствующая представленным рассуждениям. 


// Задача о ханойских башнях
// Стержни пронумерованы от 0 до 2, диски - от 1 до N.
// Требуется перенести башню со стержня 0 на стержень 2
// Вариант с непосредственным использованием формул, 
// определяющих выбор стержней в зависимости от номера шага

#include <iostream>

using namespace std;

// Определение номера перемещаемого диска по номеру итерации
// Используется зависимость от младшего переноса в двоичном 
// представлении. Т.е., подсчитывается число нулей справа.
inline unsigned DiskNumber(unsigned i)
{
    unsigned disk_number = 1;
    while(!(i & 1)) 
    {
        i >>= 1;
        ++disk_number;
    }
    return disk_number;
}


// Вычисление общего числа переносов текущего диска
inline unsigned Shifts(unsigned i, unsigned disk_number)
{
    return (i >> disk_number) + 1;
}

// Определение шага переноса. 
// При совпадении четностей равен 2. Иначе, равен 1
inline unsigned Delta(unsigned disks, unsigned disk_number)
{
    unsigned odd = disks & 1; // Формирование флага нечетности
    return 2 - (odd ^ (disk_number & 1));
}

// Определение исходящего стержня
inline unsigned Src(unsigned shifts, unsigned delta)
{
    return (delta * (shifts - 1)) % 3;
}

// Определение принимающего стержня
inline unsigned Rec(unsigned shifts, unsigned delta)
{
    return (delta * shifts) % 3;
}

// Печать результатов по проделанному шагу
inline void out(unsigned count, unsigned src, unsigned rec)
{
    cout << count 
         << ":\t " << src << " -> " << rec 
         << "\t Disk = " 
         << DiskNumber(count)
         << endl;
}

// Алгоритм, обеспечивающий моделирование ханойской башни
void hanoy(unsigned disks)
{
    unsigned steps = (1 << (disks)) - 1;

    for(unsigned i = 1; i <= steps; i++)
    {
        // Определение номера перекладываемого диска
        unsigned disk_number = DiskNumber(i);
        // Вычисление общего числа переносов текущего диска
        unsigned shifts = Shifts(i, disk_number);
        // Определение шага переноса. 
        unsigned delta = Delta(disks, disk_number);
        out(i, Src(shifts, delta), Rec(shifts, delta));
    }

    cout << endl << "Used " << disks << " disks. " 
         << endl << "Make " << steps << " steps." 
         << endl;
}

// Выполнение разработанного алгоритма
void main(void)
{
    unsigned disks;
    cout << "Input disk\'s number: ";
    cin >> disks;
    cout << "Hanoy with " << disks <<" disks:" << endl;
    hanoy(disks);
}

Несмотря на то, что данная программа превосходит по размеру рекурсивную версию, вряд ли стоит утверждать, что она концептуально сложнее.

Повышение эффективности

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

Анализ показывает, что существенное торможение происходит при работе цикла, определяющего номер диска по номеру итерации. Сократить время выполнения данного фрагмента можно только за счет дополнительной рабочей памяти, позволяющей заменить итерации другими метафорами, например использованием относительных размеров дисков. Самый простой (но, возможно, не самый эффективный) способ заключается в непосредственном моделировании стержней и перемещаемых дисков матрицей размерностью 3*N, что позволяет легко получить информацию об их текущем положении и относительном размере. От представления дисков на стержнях в виде отдельных непрерывных диапазонов я отказался, из-за необходимости вводить дополнительные проверки.

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

  1. Разборка двухэтажной башни: первый диск снимается с вершины и переносится на требуемый стержень.

  2. Построение основания двухэтажной башни: второй диск переносится на соответствующий стержень.

  3. Завершение строительства двухэтажной башни: первый диск переносится на второй диск.

  4. Укладка нового фундамента: более крупный диск перекладывается на освободившееся место, или переносится диск, ранее находившийся под первым диском (именно это действие и является основным источником дополнительного анализа).

Постоянное чередование осей ведет к тому, что через 2N-2-1 полных четырех шаговых итераций (их, естественно, в 4 раза меньше числа шагов) останется выполнить только три последних шага (укладка нового фундамента невозможна в связи с отсутствием диска с номером N+1).

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


// Задача о ханойских башнях
// Стержни пронумерованы от 0 до 2, диски - от 1 до N.
// Требуется перенести башню со стержня 0 на стержень 2
// Вариант с четырехшаговыми итерациями

#include <iostream>

using namespace std;

// Сложение по модулю 3
// Используется для cмещения как с шагом = +1: AddMod3(op1, 1)
// так и с шагом = -1:   AddMod3(op1, 2)
inline unsigned AddMod3(unsigned op1, unsigned op2) 
{
    return  ((op1 + op2) % 3);
}

// Описание одного стержня
struct Pivot {
    unsigned disk_number; // Текущее количество дисков на стержне
    unsigned *disk_list;  // Список дисков, размещенных на стержне
};

// Набор из трех стержней
struct Pivots {
    Pivot pivot[3];
    Pivots(unsigned disks); // Начальная конфигурация стержней
    ~Pivots(); // "Разрушение" стержней по завершению вычислений
};

// Начальная конфигурация стержней
Pivots::Pivots(unsigned disks)
{
    // Создается муляж для хранения дисков
    for(int i = 0; i < 3; i++) {
        pivot[i].disk_list = new unsigned[disks+1];
        pivot[i].disk_number = 0;
        // Заглушка, срабатывающая при нулевом числе дисков
        pivot[i].disk_list[0] = disks + 1;
    }

    // Нулевой стержень заполняется дисками таким образом,
    // чтобы номер диска совпадал с индексом
    for(i = 1; i <= disks; i++) {
        pivot[0].disk_list[i] = disks - i + 1;
    }
    pivot[0].disk_number = disks;
}

// "Разрушение" стержней по завершению вычислений
Pivots::~Pivots() 
{
    for(int i = 0; i < 3; i++)
        delete[] pivot[i].disk_list;
}

// Печать результатов по проделанному шагу
inline void out(unsigned count, unsigned src, unsigned rec, Pivots &p)
{
    cout << count << ":\t " << src << " -> " << rec 
         << "\t\t pivots: " 
         << p.pivot[0].disk_number << "\t" 
         << p.pivot[1].disk_number << "\t" 
         << p.pivot[2].disk_number << "\t"
         << " Disk = " 
         << p.pivot[rec].disk_list[p.pivot[rec].disk_number]
         << endl;
}

inline void move(unsigned src, unsigned rec, 
Pivots &p, unsigned &count)
{
    p.pivot[rec].disk_list[++p.pivot[rec].disk_number] = 
        p.pivot[src].disk_list[p.pivot[src].disk_number--]; 
    out(++count, src, rec, p);
}

// Алгоритм, обеспечивающий моделирование ханойской башни
void hanoy(unsigned disks)
{
    unsigned count = 0; // счетчик перекладывания дисков
    // Шаг, определяющий перемещение верхнего диска (1 или 2)
    // для проверки на четность используется маскирование
    unsigned step = 1 + (disks & 1);
    // Шаг перемещения альтернативного стержня, на который,
    // или с которого (новый фундамент) перемещается следующий диск 
    // Для определения этого шага достаточно вычесть основной шаг из 3
    unsigned alt_step = 3 - step; 
    // Стержни с дисками
    Pivots p(disks);

    // Проверка наличия дисков
    if(disks < 1) 
    {
        cout << "Disks are absent!" << endl;
        return;
    } 

    // Начата разборка первой двухэтажной башни
    unsigned src = 0;
    unsigned rec = step;
    move(src, rec, p, count);

    if(disks < 2) return; // Конец строительства башни из 1-го диска

    // Перенос второго блока в основание двухэтажной башни
    unsigned alt = AddMod3(src, alt_step);
    move(src, alt, p, count);

    // Завершение строительства двухэтажной башни
    src = rec;
    rec = AddMod3(src, step);
    move(src, rec, p, count);

    if(disks < 3) return; // Конец строительства башни из 2-х дисков

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

    // Старая версия цикла
    //unsigned iterations = (1 << (disks - 2)) - 1; // Число итераций
    //for(unsigned i = 0; i < iterations; ++i)
    // Новая проверка на окончание вычислений,
    // доводящая количество дисков до абсурда.
    while(p.pivot[2].disk_number < disks)
    {
        // Формирование нового фундамента 
        // Меньший диск перекладывается на больший
        // Участвуют исходный и альтернативный стержни
        // Новый альтернативный стержень не должен быть 
        // предыдущим приемником
        alt = AddMod3(src, alt_step); 
        if(    p.pivot[src].disk_list[p.pivot[src].disk_number] >
            p.pivot[alt].disk_list[p.pivot[alt].disk_number]
          )
        {
            // С альтернативного на исходный
            move(alt, src, p, count);
            //p.pivot[src].disk_list[++p.pivot[src].disk_number] = 
            //    p.pivot[alt].disk_list[p.pivot[alt].disk_number--]; 
            //out(++count, alt, src, p);
        }
        else 
        {   
            // С исходного на альтернативный
            move(src, alt, p, count);
        }
        // Начата разборка двухэтажной башни
        src = rec;    // Прежний приемник становится источником
        rec = AddMod3(src, step); // Новый приемник
        move(src, rec, p, count);

        // Перенос второго блока в основание двухэтажной башни
        alt = AddMod3(src, alt_step); // Новый альтернативный стержень
        move(src, alt, p, count);

        // Завершение строительства двухэтажной башни
        src = rec;    // Прежний приемник становится источником
        rec = AddMod3(src, step); // Новый приемник
        move(src, rec, p, count);
    }

    cout << endl
         << "Used " 
         << disks      << " disks. " 
         << endl
         << "Make " 
         << count << " steps." 
         << endl;
}

void main(void)
{
    unsigned disks;
    cout << "Input disk\'s number: ";
    cin >> disks;
    cout << "Hanoy with " << disks <<" disks:" << endl;
    hanoy(disks);
}

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

Заключение

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

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

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

Литература

  1. Арсак Ж. Программирование игр и головоломок: Пер. с франц. – М.: Наука. гл. ред. физ.-мат. лит., 1990. – 224 с.

  2. Шалыто А.А., Туккель Н.И., Шамгунов Н.Н. Ханойские башни и автоматы. Программист, 2002, №8, с. 82-90. (Статья также размещена на этом сайте)

  3. Ханойские башни. Статья, размещенная по адресу: http://doors.infor.ru/allsrs/alg/paper/hanoy.html.

  4. Легалов А.И. Основы разработки трансляторов. Курс лекций. Размещен по адресу: http://www.softcraft.ru/translat/lect/.

  5. Ханойские башни. Описание рекурсивного и итеративного методов. Размещено по адресу: http://algolist.manual.ru/maths/combinat/hanoi.php.