宅學習 - Social Learning Space 社交學習空間@FJU CSIE

"

一.          前言

　　這次要選一個演算法做介紹，當然先在網路上找了些東西參考，赫然的找到一篇不錯的文章，為靜宜大學-林耀鈴所寫，文章標題是＂比爾蓋茲在大學裡所寫的論文＂。[@more@]

因為研究的題目很有趣，就拿他們研究的題目來介紹了。

一.          題目

　　一位餐廳侍者在送出一疊煎餅 (pancakes) 到顧客之前，發現廚師實在太混了，這些煎餅大小不一，混雜在一起堆成一疊，客人實在不會有太多好感。因此，在送出這些煎餅之前，這位侍者會使用一片鍋鏟將這些煎餅重新排成一疊由小而大排列的煎餅。不過，由於盤子太小，我們不能夠將煎餅平餔後再重新排一次，而只能用鍋鏟卡在某個煎餅的下方，將上頭全部的煎餅一起做翻面的動作。比如說，這裡有三塊煎餅，最大的一塊叫做3,中間大小的是2,最小的一塊就是1。如果1號在盤子的最下面，3號煎餅疊在它上面，最上面的煎餅就是2號；由上而下的排列就是：(2,3,1)。那麼，侍者就可以先用鍋鏟卡在第二個煎餅的下方，將前2個煎餅做翻面的動作，這三個煎餅順序就成了：(3,2,1)；然後，侍者就可以再用鍋鏟卡在第3個煎餅的下方，將全部煎餅做翻面的動作，這三個煎餅順序就成了：(1,2,3)。好了，我們這位高興的侍者就可以趕緊將這些排好的煎餅送出去給客人了。

　　　　　　　　圖一

　　在這樣的狀況下，我們討論的就是求得如何以最少的翻面數讓那些煎餅都排好。

二.          過程

　　題目有了，我就照著他的步驟，一步一步的去求答案了，上面的題目，是較易解的，現在要討論的是，當不只有三塊煎餅，煎餅數越來越多，排列很複雜時，該如何有效率的去求得答案。如果原來的是4個煎餅，順序是：(2, 4, 3, 1)，那麼……我們要用鍋鏟做多少個動作呢？有一個很簡單的想法是這樣子：我們可以先找到最大的那片煎餅所在的位置，在它下面用鍋鏟做翻面的動作；如此一來，最大的一塊餅就會跑到最上面來，接著我們用鍋鏟將整疊煎餅翻轉過來，於是最大的一塊餅就會跑到最下面。為了說明方便，我們用 [2] 這個符號代表我們想要將前2個煎餅翻面。所以，我們就用 [2] -> (4, 2, 3,1) 來表示這個動作與結果。然後，在第二個動作我們得到：[4]->(1,3,2,4)。再來，我們再用兩個動作：[2]->(3,1,2,4) ; [3]->(2,1,3,4) 就可以將 3 號煎餅丟到4號上面。再來，最後一個動作就是 [2]->(1,2,3,4)。

　　很明顯地，如果我們有 n 個煎餅，每次最多花 2 個動作就可以將最大號的煎餅丟到下面。因此，對於3號到 n 號煎餅（共 n-2 塊煎餅），我們可以在 2(n-2) 次動作將它們搞定，剩下來的 1 號 2 號煎餅，最多只要花1次翻面的動作就行了。也就是說，n 個煎餅，我們保證可以在 2n – 3次動作內，完成正確排序動作。

　　剛剛的4塊煎餅，我們用了5個動作。有沒有可能少於 5 個動作就能夠把它排完？答案是可以。例如：

　　　　　　　　2431 [3]　->  3421 [2]　-> 4321 [4]　-> 　1234

就可以只用3個動作就將它搞定。可是，問題還在，我們怎麼知道這樣做是一定是最好的方法呢？ 我們還是問，3次動作會不會太多次了？

　　為了回答這個問題，我們仔細看看原來的4個煎餅：(2, 4, 3, 1)。我們發現，前兩個煎餅2 與 4 連起來不是兩個連續數字。我們就把這種現象稱為一個「斷點」。一個斷點代表什麼意義？注意到：如果我們不用鍋鏟插入2, 4之間，那麼，這個斷點就永遠在這裡，最後的結果就不可能是一疊排好的煎餅了！所以一有一個斷點我們就必須翻面一次，才能達到去除斷點（因為最後的結果是 (1, 2, 3, 4) 上面完全沒有任何斷點。）因此，原來的排列 (2, 4, 3, 1) 就有： 2-4, 3-1, 再加上最後的 1 與 「鍋底」之間也算是一個斷點，這個排列就剛剛好有3 個斷點。結論是：要將 (2, 4, 3, 1) 排成 (1, 2, 3, 4)，我們最少最少也要用3次鍋鏟動作才能去掉所有的斷點。不過，我們剛才不是用了3個動作將它排好嗎？因此，我們可知：剛剛的3個動作算是最節省，最有效率的方法之一。

　　把最後一個煎餅與鍋底的斷點也算進去，那麼 n 個煎餅最多可能會造成 n 個斷點。這是不是說，如果我們能夠因此「解決」掉一個斷點，最後就能夠把這些煎餅排成正確順序呢？問題倒也沒有那麼容易，例如，6個煎餅可能排成：536142 這個排列有6個斷點，自行嘗試一下，非得要用7個動作才能排成 123456，只用6個動作是不可能的。我的方法為：536142 [2] -> 3561425[5] -> 416532[4] -> 561432[3] -> 165432[6] -> 234561[5] -> 654321[6] -> 123456[6] 盡量的把當中的斷點消掉，就可以

得到最佳解。

　　經過比爾蓋茲（Bill Gates）與克里斯多‧帕伯狄米裘（Christos Papadimitriou）（一位在今日世界計算機理論界仍是大大有名的人物）對這個題目的研究，得到：對 n 個煎餅的任何排列，都能找出一組鍋鏟動作，並且保證可以在 (5n+5)/3 次動作之內得到由小而大的正確排列。透過人工求得最佳解，我們得到要盡量把斷點消掉，但他們又指出是去掉 n-2 個斷點；最後，再對剩下來的兩個斷點做處理，由此得到一組「還不錯的」解答。這種策略在演算法裡頭是叫做一種「經驗法則」(heuristics)。

為什麼會最多產生 (5n+5)/3 次動作呢？林耀鈴猜測是 比爾蓋茲 想到這個 經驗法則，而 Papadimitriou最後是用了線性規劃理論裡頭的 duality theorem 而推導出最後 (5n+5)/3 這個數據。

得到一個 heuristics 說明 (5n+5)/3 動作就一定可以將 n 個煎餅排好順序的確不錯。但是究竟「最佳解」需要多少次動作？我們就用函數 f(n) 來表示：給定 n 個煎餅的任何順序，對最難排好的排列而言，我們最少需要的鍋鏟動作數。也就是說，對於任何 n 個排列，我們用 f(n) 次鍋鏟動作保證可以將它排好，但是 f(n)+1 次就一定是太浪費了。很明顯地，利用剛剛提到 Gates 的 heuristics ，我們知道 f(n) 最多就是到 (5n+5)/3, 也就是說，f(n) ≦ (5n+5)/3. 同時，既然 n 個煎餅最多有可能有 n 個斷點，因為f(n)為最難排好的排列組合，而最困難的排列組合一定是斷點最多的。很明顯地 n ≦ f(n). 。Gates與 Papadimitriou 在這篇文章中的另一個貢獻就是提出 f(n) 在 n 夠大之後不會只有 n 那麼小。論文中，他們提出一些觀點，基本上，他們用的方法是利用這個反覆一段長度為16的基本序列：

        (1, 7, 5, 3, 6, 4, 2, 8, 16, 10, 12, 14, 11, 13, 15, 9)

反覆 k 次之後，他們論證：至少需要17k 以上的翻面動作才能將這些16k 個煎餅排好。因此證明了 (17/16) n ≦ f(n), 文章結論就是說：

(17/16) n ≦ f(n) ≦ (5n+5)/3。

知道 f(n) 最少是 (17/16)n ，而且也有一個 heuristics 說明(5n+5)/3 動作就一定可以將 n 個煎餅排好順序的確不錯。但是無論如何，人們還是會想知道「最佳解」f(n) 的確切答案。很明顯的， f(1) = 0, 一個煎餅本身就已經排好; f(2) = 1, 兩個煎餅最多翻一次就行。 f(3) = 3, 因為 132 怎麼翻都需要3次 （注意到它其實只有兩個斷點。）下面這個表格列出 f(n) 的前13個數值。

其實，這個表格得來不易：前7個數字，是由在計算機理論界鼎鼎大名的 Garey and Johson (以及 S. Lin) 在 1977 年算出來的。 f(8) 與 f(9) 則由 Robbins 在1979 年 算出。一直到18年後，f(10) 到 f(13)才由M. Heydari and I. H. Sudborough 在 1997 年算出來的。事實上，他們最後還改進了原來 Gates 他們所提出了原來 f(n) 的下限。他們提出類似的論證：利用這個反覆一段長度為14的基本序列：

        (1, 7, 5, 3, 6, 4, 2, 8, 14, 12, 10, 13, 11, 9)

反覆 k 次之後，他們論證：至少需要15k 以上的翻面動作才能將這些14k 個煎餅排好。因此證明了 (15/14)n ≦ f(n) 。比較有趣的是，20年都已經過去， f(n) 的下限只提升了一點點，而 Gates 的演算法， f(n) ≦ (5n+5)/3 的f(n) 上限到現在還是沒有任何改進。

　　下面的表為當n的煎餅，需要k次翻轉，會有多少種的排列：

"

Dynamic Programming跟Divide-and-Conquer解法的最大不同為：

Divide-and-Conquer用的方法是Top-down，

1.把問題切割成更小的問題

2.解決分割後的問題,除非分割後的問題有必要在分割成更小,用遞迴的概念去做

3.如果需要,把分割後的問題的solution結合起來,得到了原本問題的solution

而Dynamic Programming使用Bottom-up的方法，

從最基本的小問題解起，並將值紀錄下來，再逐步推到整個問題的解。

引用http://algorithm.weco.net/index.php?op=ViewArticle&articleId=1944&blogId=4"

"

雖然XML這門課修的不太好~"~

不甚了解XML的內容... 

但是這星期聽到其他組的Project報告後

XML的應用真是太重重重要了呀

像這禮拜的報告的-SAML、CDA

都是相當方便的東西

是應該極力去推廣的 

引用http://xml.weco.net/index.php?op=ViewArticle&articleId=6684&blogId=340"

"

一針見血的評論

寫出了SAX跟DOM的不同點

SAX︰

• 是基於事件的 API。
• 在一個比 DOM 低的層級上作業。
• 為您提供比 DOM 更多的控制。
• 幾乎總是比 DOM 更有效率。
• 但不幸的是，需要比 DOM 更多的工作。

引用http://xml.weco.net/index.php?op=ViewArticle&articleId=5970&blogId=340"

"推"