Ханойские башни
Задача
Высоко в горах Тибета монахи перекладывают 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. Прямой подстановкой несложно проверить, что ему удовлетворяет следующее решение:
Если натренированные монахи тратят секунду на один диск, то конца света следует ждать не ранее чем через 584 миллиарда лет (M64 = 264 - 1 = 1.8·1019 секунд). Впрочем, когда они начали, нам неведомо.
Количество состояний системы (рассположений n дисков по t башням) вычисляется следующим образом. Первый диск может находиться на одной из t башень. Независимо от этого, второй диск, при каждой из t возможностей первого диска, также может находиться на t башнях, что даёт t·t возможностей и т.д.:
В таблице приведены значения функций 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