演算法筆記 - 經典河內塔

最近在看CNN的文章的時候, 提到了Hierarchy的概念

目的是以divide-and-conquer的概念來將大問題切割為小問題

以image recognition / computer vision來說, "直覺上"每個pixels只會跟鄰近的pixels有關聯性(correlated to local pixels)

也就是說在Machine Learning的領域上又回歸到了"自然的"、"直覺式"的算法 XD

有點扯遠了, 讓我們先回到第一個關鍵字 "divide-and-conquer"

這個詞被翻譯做分治法, 也就是分而治之

如果你熟悉於科技業, 一定在很多問題/系統上都已經看過了分治法解決問題的能力.

如果你是一個科技新鮮人, 那麽這個經典的河內塔也是你在人生的遞迴之路的重要基石.

河內塔 (Tower of Hanoi) 的故事

 - 引述自 Wiki 百科 <河內塔>

傳說印度某間寺院有三根柱子，上串64個金盤。寺院裡的僧侶依照一個古老的預言，以一定的規則移動這些盤子；

規則: 有三根杆子A，B，C。A杆上有N個(N>1)穿孔圓盤，盤的尺寸由下到上依次變小。
要求按下列規則將所有圓盤移至C杆：

1. 每次只能移動一個圓盤；
2. 大盤不能疊在小盤上面。

預言說當這些盤子移動完畢，世界就會滅亡。這個傳說叫做梵天寺之塔問題（Tower of Brahma puzzle）。

若傳說屬實，僧侶們需要2⁶⁴ − 1步才能完成這個任務；若他們每秒可完成一個盤子的移動，就需要5845億年才能完成。

(整個宇宙現在也不過137億年。)

這個傳說有若干變體：寺院換成修道院、僧侶換成修士等等。

寺院的地點眾說紛紜，其中一說是位於越南的河內，所以被命名為「河內塔」。

移動河內塔

那麼, 要怎移動河內塔呢?

我們先來推一次, 當瓦片數為 3 的時候,  流程如下

移動次數＼塔	A	B	C
1	2 3		1
2	3	2	1
3	3	1 2
4		1 2	3
5	1	2	3
6	1		2 3
7			1 2 3

* 最少需要移動 2^3 - 1 = 7步

接著, 讓我們簡化問題變成瓦片數為 2 的狀況:

移動次數＼塔	A	B	C
1	2	1
2		1	2
3			1 2

看一下, 瓦片數為 2 的狀況跟 3 的狀況, 對於前 3 動的移動順序是不是非常相似

他們最大的差異, 就是將1號跟2號瓦片, 移動到C柱或者是B柱的差別

當N = 2的時候, 直接移動到C柱即可

當N = 3的時候, 你需要先將(1, 2)移動到B柱, 接著將(3)移到C柱, 最後將再將(1, 2)移到C柱

到這一步, 其實已經分治完成了 ヽ(∀ﾟ)人(ﾟ∀ﾟ)人( ﾟ∀)人(∀ﾟ)人(ﾟ∀ﾟ)人( ﾟ∀)ﾉ

河內塔的關鍵就在於, 要適時的把這些柱子當作暫存的buffer來使用

接著我們試著寫出虛擬碼:

moveDisk(N, from, to, buffer) {

    if (N == 0) {
         // 中止條件! 沒得動啦

        return;

    } else {
        // 把倒數第二片開始的盤子從A柱(from)移動到B柱(buffer)去

        move((N-1), from, buffer, to);
        // 把最底下的盤子N 從A柱(from)移動到C柱(to)去

        print("Move Disk %d from %d to %d", N, from, to);

        // 把倒數第二片開始的盤子從B柱(buffer)移動到C柱(to)去

        move((N-1), buffer, to, from);

    }

}

以上!