Ханойские башни

Задача

Высоко в горах Тибета монахи перекладывают 64 золотых диска, нанизанных на 3 алмазные стержня. Когда их работа будет окончена, наступит конец света...

Есть 3 стержня. На первый надеты n дисков увеличивающегося сверху вниз диаметра. Эти диски необходимо по одному переложить с первого стержня на второй. Можно использовать все стержни, но диски большего диаметра должны всегда находиться ниже дисков меньшего диаметра (на картинку можно кликать, а также менять число дисков: и стержней: )

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

Рекурсивное решение

Пусть есть 3 башни (x, y, z) и, благодаря магическим способностям, мы умеем перекладывать n дисков с одной башни на другую. Применим эти способности, переложив n-1 дисков с x на z. Затем тривиальным образом перенесём оставшийся (самый большой) диск с x на y. Наконец, снова, применив магию, переложим n-1 дисков с z на y (поверх того, самого большого диска). Всё, задача по переносу n дисков с x на y решена, а её код на JavaScript имеет вид: 

function Hanoi1(n, x, y, z)                       // переложить n дисков с x на y, используя z
{
   if(n <= 0)                                     // (0) дисков нет - конец
      return;

   Hanoi1(n-1, x,z,y);                            //     перекладываем n-1 дисков с x на z
   document.write(x+'->'+y+", ");                 // (1) переносим     1 диск     c x на y
   Hanoi1(n-1, z,y,x);                            //     перекладываем n-1 дисков с z на y

   return;                                        // (2) конец (для наглядности листинга Hanoi3)
}
Несмотря на ощущение надувательства, всё работает и вызов функции Hanoi1(3, "0", "1", "2") (башни нумеруем с нуля) приведёт к следующему результату (который стоит проверить, перекладывая диски мышкой):
.

Аналогичен алгоритм, на вход которого подаётся номер (по размеру) перкладываемого диска (их также нумеруем с нуля: d=0...n-1) и направление его сдвига s=1 (вправо) или s=-1 (влево). Сдвиг предполагается цикличным и при переносе с 0-го стрержня влево (s=-1) диск попадает на 2-й стержень, а при переносе со второго вправо (s=1) - попадает на 0-й. Пусть необходимо сдвинуть самый большой (нижний) диск (d=n-1) вправо (s=1). Для этого мы должны сдвинуть чуть меньший диск d-1 влево -s, затем переложить большой диск вправо, и затем на него положить меньший, снова сдвигая его влево (цикл через 3 тоже что 2 раза вправо): 

function Hanoi2(d, s)                             // сдвинуть диск d на s стержней вправо (если s>0)
{
   if(d < 0)                                      // кончились диски
      return;

   Hanoi2(d-1, -s);                               // сдвигаем меньший диск d-1 влево
   document.write((s>0?" +":" -")+d);             // перекладываем диск d вправо (s=1)
   Hanoi2(d-1, -s);                               // сдвигаем меньший диск ещё раз влево
}
Hanoi2(2, 1);                                     // самый большой (d=2=3-1) вправо (s=1)
Этот, ещё более волшебный код, приводит к: , что означает: "перенести маленький диск под номером 0 вправо, затем следующий по размеру диск влево (окажется на последнем стержне), и т.д."

Разделяй и властвуй

Подсчитаем число ходов M(n,3)=Mn, которые необходимо сделать для решения задачи с n дисками и 3-мя башнями. Каждый вызов функции Hanoi1приводит к одному перекладыванию и двум выззовам с перекладыванием на единицу меньше. Поэтому справедливо рекурентное уравнение: Mn=1+2·Mn-1 с начальным условием M1=1. Прямой подстановкой несложно проверить, что ему удовлетворяет следующее решение:

Mn = 2n - 1.

Если натренированные монахи тратят секунду на один диск, то конца света следует ждать не ранее чем через 584 миллиарда лет (M64 = 264 - 1 = 1.8·1019 секунд). Впрочем, когда они начали, нам неведомо.

Количество состояний системы (рассположений n дисков по t башням) вычисляется следующим образом. Первый диск может находиться на одной из t башень. Независимо от этого, второй диск, при каждой из t возможностей первого диска, также может находиться на t башнях, что даёт t·t возможностей и т.д.:

N(n,t) = tn.

В таблице приведены значения функций Mn=M(n,3), Nn=N(n,3) и их отношение:

n 3 4 5 10 15 20
Mn 7 15 31 1023 32767 1048575
Nn 27 81 243 59049 14348907 3486784401
Mn/Nn 0.26 0.19 0.12 0.02 0.002 0.0003

Решение ханойской головоломки является примером подхода "разделяй и властвуй", в котором два рекурсивных вызова работают с приблизительно половиной входных данных. Такое постоянное деление на 2 быстро уменьшает размерность задачи (приводя, в нашем случае, к тривиальному переносу единственного диска).

Структура данных

В задачах поиска решений, часто приходится сохранять в памяти различные состояния решаемой задачи. Поэтому необходимо обеспечить максимально компактное описание состояния системы. Введём массив disks[i] размерности n, в котором будем хранить номер (начиная с 0) башни, где находится i-тый диск (также отсчет ведем с нуля): 

function Hanoi(nDisks, nTowers)
{
   if(!nTowers) nTowers = 3;                      // три башни по умолчанию

   this.nDisks  = nDisks;                         // число дисков
   this.nTowers = nTowers;                        // число башен

   this.disks = new Array(nDisks);                // номер башни i-того диска

   for(var i=0; i < nDisks; i++)
      this.disks[i] = 0;                          // все диски на нулевой башне
}
Эта функция объявляет класс Hanoi, экземпляры которого будут хранить число дисков nDisks, башен nTowers и массив disks принадлежностей каждого диска к конкретной башне. При помощи директивы prototype определим два метода класса Hanoi. Первый устанавливает диск под номерм disk на башню под номером tower, а второй выводит массив disks как строку: 
Hanoi.prototype.set = function (disk, tower)
{
   this.disks[disk] = tower;
}

Hanoi.prototype.toString = function ()
{
   var res = "";
   for(var i=0; i < this.nDisks; i++)
      res += this.disks[i];
   return res;
}
Теперь для 5 стержней и 3-х башен можно написать следующий код, который, при помощи оператора new, создаёт экземпляр han класса Hanoi, перемещает 0-й диск на 3-ю башню, а 4-й диск на 1-ю башню и затем результат выводится на страницу: 
var han = new Hanoi(5);   han.set(0,3);   han.set(4,1);   document.write(han);
что приведёт к появлению строки: .

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

Hanoi.prototype.top = function (tower)
{
   for(var i=0; i < this.nDisks; i++)
      if(this.disks[i]===tower)                   // сверху самый маленький
         return i;
   return -1;                                     // башня пустая
}
Аналогично выгдядит функция, возвращающая номер диска в стопке на башне (считая снизу от нуля): 
Hanoi.prototype.pos = function (disk)
{
   var tower = this.disks[disk], id=0;            // башня, где лежит диск
   for(var i=this.nDisks-1; i > disk ; i--)       // начинаем с более толстых (снизу)
      if(this.disks[i]===tower)
         id++;
   return id;
}

Рисуем башни

Перейдём теперь к художествам при помощи библиотеки draw.js, которая позволяет рисовать как на канвасе, так и в создавать файлы векторной графики (svg-формат). Зададим внутри конструктора Hanoi геометрические параметры системы, добавив туда следующий код: 

function Hanoi(nDisks, nTowers)
{
   ...

   this.h     = 120;                              // высота стержня
   this.w     = 10;                               // толщина стержня
   this.dx    = 190;                              // шаг по x с которым идут стержни
   this.baseW = 170;                              // ширина основания (подставка)
   this.diskH = 10;                               // высота диска
   this.diskW = this.baseW*0.9/nDisks;            // ширина единичного диска
   if(this.diskW  < this.w) this.diskW=1.5*this.w;

   this.fly  = this.flyDes =-1;                   // номер летящего диска и целевой башни
   this.flyV = 0.5;                               // скорость летящего диска в px/ms
}
(номер fly переносимого диска, его назначение flyDesи скорость flyV будут обсуждаться в следующем разделе). Теперь код метода рисования башен на объекте draw имеет вид: 
Hanoi.prototype.show = function(draw)
{
   if(!draw) draw = this.draw;

   draw.clear();                                  // очитска области рисования

   var x0 = this.baseW/2;                         // координаты основания первого стержня
   var y0 = this.h + 2*this.diskH;

   for(var i=0; i < this.nTowers; i++){           // рисуем nTowers башeнь
      draw.colorFill("#555");                     // рисуем стержень и подставку серым:
      draw.box(x0+i*this.dx, y0-this.h/2,        this.w,  this.h, 3);
      draw.box(x0+i*this.dx, y0+this.diskH/4-1,  this.baseW,  0.5*this.diskH, 3);
   }

   draw.colorFill("#069");                        // рисуем диски синим:
   for(var k=0; k < this.nDisks; k++){
      var twr = this.disks[k];
      if(twr >= 0)
         draw.box(x0+twr*this.dx, y0-this.diskH*(this.pos(k)+0.5)-2,
                  this.diskW*(k+1), this.diskH, 3);
   }

   if(this.fly >= 0)                              // анимируем летящий диск (если он есть)
      draw.box(this.flyX, this.flyY, (this.fly+1)*this.diskW, this.diskH, 3);
}
В библиотеке draw.js координаты ящиков - это их центр, а последний параметр функции box - радиус скругления углов.

В качестве теста создадим 3 башни и выведем их на html-страницу в виде svg-картинки: 

var han  = new Hanoi(10);
han.draw = new Draw();
han.show();
document.write(han.draw.getSVG(600,200));

Таймер

Для анимирования полёта перекладываемого диска нам потребуется 3 функции, при помощи которых диск берётся, бросается в направлении целевой башни и кладётся на неё, когда туда долетает: 

/****************************************************************************************
* Убрать диск из башни tower, вернуть его номер
*/
Hanoi.prototype.get = function (tower)
{
   var f = this.top(tower);                       // верхний диск на башне src
   if(f < 0)
      return -1;                                  // нельзя взять, башня пустая

   this.flyX = this.baseW/2+this.disks[f]*this.dx;// диска поднимаем над башней
   this.flyY = this.h + 2*this.diskH - this.h - this.diskH;

   this.disks[f]   = -1;                          // "убираем" (висит в воздухе)
   return this.fly = f;                           // запоминаем координату взятого
}
/****************************************************************************************
* Задать назначение полёта
*/
Hanoi.prototype.throw = function(des)
{
   this.flyDes = des;                             // башня назначения
   this.flyD = this.baseW/2+des*this.dx-this.flyX;// это расстояние надо пролетель
   this.flyV = this.flyD>0? Math.abs(this.flyV):  // направление скорости полёта
                           -Math.abs(this.flyV);
   this.flyD = Math.abs(this.flyD);               // расстояние всегда положительно
}
/****************************************************************************************
* Положить диск с номером disk на башню tower
*/
Hanoi.prototype.put = function (disk, tower)
{
   if(disk >= 0){                                 // если башня не пустая
      this.disks[disk] = tower;                   // "переносим" с неё диск
      if(this.nMoves === undefined) this.nMoves = 0;
      this.nMoves++;
   }
   this.fly = this.flyDes = -1;
}
В этих функциях вводится переменная fly номера перекладываемого диска, его координаты, скорость, башня назначения и расстояние, которое он должен пролететь. Диск будет лететь, если в таймере вызывать функцию: 
Hanoi.prototype.timer = function()
{
   if(this.lastTime === undefined) this.lastTime = new Date();
   var dt = new Date() - this.lastTime;

   if(this.fly>=0 && this.flyDes >= 0){           // подняли диск и определили назначение
      var d = this.flyV *dt;
      this.flyX += d;
      this.flyD -= Math.abs(d);
      if(this.flyD < 0)                           // закончили лететь
         this.put(this.fly, this.flyDes);
   }
   else if(this.solve)                            // процесс размышлений (задаём извне)
      this.solve(dt);

   this.show(this.draw);                          // перерисовываем
   this.lastTime = new Date();
}
Делается это следующим образом. На html странице помещается канвас: 
<canvas id="canvasHanoiTimer" width="600" height="200"></canvas>
и пишется следующий скрипт: 
var hanRnd   = new Hanoi(5,3);                    // 5 дисков 3 башни
hanRnd.draw  = new Draw("canvasHanoiTimer");      // будем рисовать на канвасе с id=canvasHanoiTimer

hanRnd.solve = function()                         // функция принятия решения
{
   var src = Math.floor(Math.random()*this.nTowers), des = Math.floor(Math.random()*this.nTowers);
   if(this.src != src && this.canMove(src, des)){
      this.get(src);                              // берём, если этот случайны выбор разрешен
      this.throw(des);                            // и кидаем
      this.src = des;                             // запоминаем
   }
}

setInterval(function(){  hanRnd.timer(); }, 50)   // таймер через каждые 50 ms

Взаимодействие с мышкой

Для организации взаимодействия с мышкой напишем ещё одну функцию: 
Hanoi.prototype.mouseUp = function (x,y)
{
   var twr = Math.floor(2*x/(this.baseW+this.dx));// номер башни на которой был клик
   twr = twr<0? twr=0: (twr>=this.nTowers? this.nTowers-1: twr);

   if(this.fly < 0){                              // ещё не брали, попробуем:
      if(this.canGet(twr))
         this.get(twr);                           // берём
      else
         alert("Вы не можете взять диск с этой башни");
   }
   else if(this.flyDes < 0) {                     // можем указать куда
      if(this.canPut(twr, this.fly))              // если можно положить на башню twr
         this.throw(twr);                         // кидаем в неё
      else
         alert("Вы не можете положить диск на эту башню");
   }
   this.show();
}
Теперь необходимо подключть мышиное событие: 
var hanoiM = new Hanoi(3);
hanoiM.draw = new Draw("canvasHanoiM");
hanoiM.canvas  = document.getElementById('canvasHanoiM');
hanoiM.show();

function hanoiM_mouseUp(event)
{
   var rct = hanoiM.canvas.getBoundingClientRect();
   var x = event.clientX - rct.left;              // координаты мыши
   var y = event.clientY - rct.top;
   hanoiM.mouseUp(x,y, hanoiM.canvas.width);
}

hanoiM.canvas.addEventListener("mouseup",  hanoiM_mouseUp, false);
setInterval(function(){ hanoiM.timer() }, 50);
Результат этих действий приведен в начале страницы.

Нерекурсивное решение

Чтобы анимировть перекладывание диска в процессе решения задачи компьютером, необходима нерекурсивная версия функций Hanoi1 или Hanoi2 Для её написания, понаблюдаем за действиями рекурсивной функции при различном числе дисков (компактная запись):

Hanoi2(2,1):
Hanoi2(3,1):
Hanoi2(4,1):
Hanoi2(5,1):

Видно, что через раз переносится самый маленький диск под номером 0 вправо (+0) для нечётного n или влево (-0) - для чётного. Несложно видеть, что после такой перестановки, существует только одна возможность переложить другой диск. Этим алгоритмом, как известно, и пользуются монахи: 
Hanoi.prototype.solveTXT = function(maxMoves)
{
   var s = this.disks.length%2? 1: -1;            // направление сдвига
   while(maxMoves-- > 0){
      var p = this.disks[0] + s;
      p = p < 0? 2: (p > 2? 0: p);                // проверка, попадания в границы [0...2]
      this.disks[0] = p;                          // перекладываем самый маленький
      document.write((s>0?" +":" -")+0);          // и выводим

      var p1 = p > 0? p-1: 2;                     // слева  по циклу от маленького
      var p2 = p < 2? p+1: 0;                     // справа по циклу от маленького
      var d1 = this.top(p1);                      // верхний на стержне p1
      var d2 = this.top(p2);                      // верхний на стержне p2

      if(p===1 && d1 < 0 && d2 < 0)               // маленький на месте, слева, справа - никого
         break;                                   // задача решена

      if(d2 < 0 || (d1 >= 0 && d1 < d2)){         // перекладывем c p1 на p2
         this.disks[d1] = p2;
         document.write(p1 < p1?" +":" -",d1);    // и выводим
      }
      if(d1 < 0 || (d2>=0 && d2 < d1)){           // перекладывем c p2 на p1
         this.disks[d2] = p1;
         document.write(p2 < p1?" +":" -",d2);    // и выводим
      }
   }
}

Запуск скрипта (new Hanoi(4)).solveTXT(100) даёт:

Стековое решение

При помощи стека (массива "вызовов функций"), напишем ещё один нерекурсивный код, логика которого тождественна функции Hanoi1. Перед каждым рекурсивным вызовом, в стеке будем сохранять текущее состояние аргументов функции. Затем в стек запихнём рекурсивно вызываемую функцию. Кроме этого аргументов функции будем сохранять индекс pos, нумерующий "участки кода", куда необходимо вернуться по окончанию работы функции (в листинге Hanoi1 они помечены круглыми скобками): 

function Hanoi3(n, x, y, z)
{
   var stack = [];                                // стек вызовов функций
   stack.push( {args:[n, x, y, z ], pos:0} );     // аргументы и точка вызова

   while(stack.length > 0){                       // пока стек не пустой
      var fun = stack.pop();                      // "заходим" в функцию

      switch(fun.pos){                            // переходим на точку сохранения
         case 0:                                  // первый вызов
            if(fun.args[0] <= 0)
               continue;                          // функция закончилась: "return"
            fun.pos = 1; stack.push(fun);         // перед рекурсией сохраняемся
            stack.push({ args:[fun.args[0]-1, fun.args[1], fun.args[3], fun.args[2]], pos:0});
            break;
         case 1:
            document.write(fun.args[1]+'->'+fun.args[2]+", ");

            fun.pos = 2; stack.push(fun);         // перед рекурсией сохраняемся
            stack.push( {args:[fun.args[0]-1, fun.args[3], fun.args[2], fun.args[1]], pos:0});
            break;
         case 2:                                  // функция закончилась: "return"
            break
     }
  }
}
Запуск этой функции даёт результат аналогичный Hanoi1: . Нечто подобное функции Hanoi3 делает компьютер, когда запускает на выполнение рекурсивную функцию Hanoi1.

Финальный результат

Для запуска решателя следует нажать на кнопку и насладиться перемещением дисков: time = 0:0:0 moves = 0