最近在看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杆：
要求按下列規則將所有圓盤移至C杆：
- 每次只能移動一個圓盤；
- 大盤不能疊在小盤上面。
預言說當這些盤子移動完畢，世界就會滅亡。這個傳說叫做梵天寺之塔問題（Tower of Brahma puzzle）。
若傳說屬實，僧侶們需要264 − 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)去
// 把倒數第二片開始的盤子從A柱(from)移動到B柱(buffer)去
move((N-1), from, buffer, to);
// 把最底下的盤子N 從A柱(from)移動到C柱(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);
}
}
以上!
