# 演算法

## 演算法與啟發式解法

不論是不是用來處理數字,演算法(algorithm)是一種萬全的程序,保證能達成特定的目的.[演算法]一詞源自阿拉伯數學家花拉子密(al-Khwarizmi),它在9世紀時發明許多演算法.在英文中代數(algebra)這個字其實源自於調換(al jabr)之意.花拉子密的許多演算法至今仍被廣泛使用.

電腦演算法通常以程式描述,由於演算法一詞主要描述的是操作順序,因此相同的演算法可以用不同的電腦語言描述,甚至連接適當的暫存器及邏輯閘於硬體上,以建立另一種演算法.

通常,很多演算法都可以得到相同的結果,只是不同的演算法完成同一件工作的時間不同.某些演算法可能有其他的優點,也許它所需的記憶體較少,或是使用的的訊息模式特別簡單,因此很容易將線路連接於硬體中.好的演算法和壞的演算法對時間與記憶體的需求往往相差超過數千倍,甚至數百萬倍.有時發現新的演算法可以讓你解決一個困擾多時的問題.

由於演算法能以各種方式執行,而且能應用在不同難易度的問題上,因此無法只用解決某個問題所花的時間來評斷演算法的速度,因為解題時間是依執行方式及問題大小而異.通常我們會以解題時間與問題大小之間的關係來描述演算法的速度.撰寫電腦程式最大的樂趣再於找到一種更新更快更有效率的方式來處理問題.

## 最佳演算法

最佳演算法往往不是那麼顯而易見.現在我們想辦法將一疊依序編號的卡片,按遞增順序排列.有一種排列方式是先找出最小的卡片,將它取出後放到一邊.然後在剩下的卡片中再取出編號最小的卡片,將它放在剛才取出的第一張卡片上面.重複這過程直到所有的卡片抽完,會得到一疊依遞增順序排的卡片.以這種方式抽出每一張卡片時,都要先檢視剩下未排序的卡片,若剩下 n 張卡片,則每一次都要比較 n 張卡片上的數字,因此這個演算法執行時間的級數為n**2(n 張卡片 X 比較 n 次).

若我們知道卡片上的編號為 1~n,則可以用另一種方式排序.這方式是利用遞迴定義.要以遞迴檢視一疊卡片時,首先檢視全部的卡片,將所有小於平均值的卡片湊一堆,而大於平均值的卡片置於另一堆,再以同樣的方式處理這2堆卡片,則會得到4堆卡片,以此類推,每遞迴一次,每疊卡片的數量便會減半,最後當每疊卡都只剩一張時,排序工作就完成了.由於這個演算法會反覆將卡片對分,直到剩下一張卡為止,因此他所需要的時間與n張卡片可以對分的次數成正比,也就是以2為底,取 n 的對數(log n),所以這演算法的時間級數為 nlog n.除此之外還有一個更優雅的遞迴演算法,卡片的排列方式不必依序編號,它是將名片依英文字母順序排列時所用的演算法.這種演算法蠻有用的,稱為合併排序(merge sort).雖然不太容易理解.若有兩疊已排序的卡片,則我們只要不斷選取兩疊卡片中,頂端那張字母順序較前的卡片,便可以輕易得到一疊排序過的卡片,合併排序就是利用這個特性.這個合併過程只是合併排序的副程式,而整個演算法運作方式如下-若每疊只有一張卡片,則卡片已完成排序,否則將卡片分成兩半,再以遞迴的方式對這兩半作排序合併的動作,合併排序演算法式展現遞迴及簡潔的絕佳示範.

## 旅行推銷員問題

有一個典型的難題叫旅行推銷員問題(traveling salesman problem).想象有個到處旅行的旅行員要拜訪n個城市,假使已知任兩個城市的距離,那旅行員應以什麼樣的順序走訪這n個城市,才能使總距離最短?沒人知道這問題應以多少級數的演算法才能解決,是 n2 還是 n 的任何次方?若已知的最佳演算法級數為 2n,這表示解題時間隨時間大小呈指數次方成長, Ex.若我們將推銷員拜訪的城市個數增加10個,則問題的難度就增加了1000倍(210=1024),若增加30個,則難度將變成10億倍(230約為10**9).指數演算法在問題變大時就沒什麼用處,但對旅行推銷旅行員問題而言,這是目前所知最佳的演算法.旅行推銷員問題看起來也許不重要,但它卻和許多問題是相當的,也就是所謂的N-P完全問題(N-P complete problem,N-P表示[nondeteministic polynomial],非決定性多項式),而這樣的演算法對這些問題都很有用.若能迅速解答旅行推銷員問題,也就能立刻得到這些問題的解答,果真如此的話,要破解機密資料的密碼就變得輕而易舉了.電腦科技在解決旅行推銷員問題仍然沒什麼突破,即使是運算速對非常快的電腦,也會因多加了幾個城市而變的遲緩.

像旅行推銷員這樣的難題,對電腦來說並不是最最困難的,有些問題的解題時間甚至超過指數級數.也有些無法用演算法解不可計算問題,即使某些問題有演算法可解,但也未必是最好的解法,但依定義來看,演算法是保證能夠完成所要執行的工作,但這樣的保證往往需要付出相當高的代價,在許多型況下,使用[幾乎]能夠得到正確答案的程序更切何實際.一般來說,[幾乎]就已經夠不錯了,若一個法則傾向於得到正解,卻不能保證得到正解,則我們稱之為啟發式解法(heuristic).使用啟發式解法往往比演算法來得實際. 啟發式解法在使用上,最間單的例子就是西洋棋遊戲程式.一個聰明的程式設計師,即使他只有普通的棋藝,卻可以寫出打敗自己的西洋棋程式.這種程式並非演算法,因為它不保證穩贏.啟發式解法是利用經驗及知識做各種猜測,而好的啟發式解法往往能做出正確的判斷.電腦的某些最令人印象深刻的行為都是啟發式解法,而非演算法.要寫出良好的下棋程式,則可以下列啟發式解法作為依據:

1 計算棋盤上所剩的棋子,以評估每位玩家相對的局勢. 2 將棋子下在往後幾步內所能預料的最佳位置. 3 假設對手採取與你相似的策略.

這些法則只是大概的策略,我們也可以想像它們失誤的情況.玩家的相對局勢除了要看所剩的棋子外,棋子所在的位置也很重要.好的位置往往比多一個子來得有利.

利用這些啟發式法則,可以寫出一個下棋程式,模擬往後幾步內所有看起來可行的棋路.最好能同時考慮所有看起來可行與不可行的棋路,並盡可能延長到遊戲結束.

對井字遊戲而言是很容易,但對西洋棋來說,這麼做是不切實際的,即使是用最快的電腦也是如此.在西洋棋遊戲中,玩家有36種移動方式,而每一種移動方式又導致對方有36種回應的可能,平均來說,玩西洋棋時至少都會持續80步以上,因此電腦必須在36**80種可能的狀態中搜尋,這種搜尋即使是最快的電腦也要花上百年的時間才能完成.假設(2)是正確的,並同意最佳路線即為未來幾步內使玩家處於最有利地位的棋路,再指定下棋程式檢視往後的六個步驟.根據(1),下棋程式會檢視六個步驟後雙方的局勢.有了這些假設,再接下來的六個步驟中,電腦不能只選它最想走的路,因為其中還參雜著對手所下的棋子.因此我們必須假設對手會選擇對他自己有利的棋路,這就是(3).因此電腦會沿著六個步驟的所有可能棋路,輪流扮演黑白雙方的棋子.程式在電腦記憶體中的虛擬棋盤上遊走,就像西洋棋大師在腦海中摹想它的棋路一樣.評估黑白棋形式的程式會遞迴的呼叫副程式.

大部分的下棋程式會加入一些額外的啟發式法則,已停止搜尋工作,並對可能的棋路做更深度的搜尋,包括犧牲自己的棋子兌換對方的棋子.這些啟發式法則只是一些附加的揣測,在某些情況下可以改善搜尋品質,但同時可能會造成其他方面的失誤.精雕細琢之後,這個基本搜尋程式幾乎就是所有下棋程式的核心.由於電腦的速度足以考慮數百萬條可能的路線因此它非常有效率,而在這幾百萬條棋路中,總有一條出乎程式設計師意料之外的,甚至連西洋棋高手也無法預測,這就是為什麼在與電腦下棋時,程式設計師往往被電腦打敗. 在電腦程式中,利用啟發式法則在可能狀態中搜尋是相當普遍的,而且也有比玩遊戲更重要的應用,它通常也是電腦尋找[創造性]答案的一種方式,這類問題的解答通常落在一組非常龐大卻有限的可能狀態所成的集合中,我們稱這個集合為搜尋空間(search space).西洋棋的搜尋空間是由一組所有能的棋路所成的集合,而旅行推銷員問題的搜尋空間是連接每個城市的所有可能路徑.由於這些空間非常龐大,無法條列式一一搜索,因此必須靠啟發式法則縮小搜尋範圍,像井字遊戲這種搜尋空間很小的問題,條列式搜尋則是最佳的方式,因為它能保證得到正確答案.

搜尋空間之所以龐大,乃因那些可能狀態是產生於簡單元素的組合,這些元素導致了可能狀態的[組合爆炸],它隨著組合元素的增加呈指數倍爆炸性成長.由於可能狀態是由元素組合所產生的,因此在這個空間中會有距離的觀念,公有元素組合出來的距離比稀有元素組合出來更為接近.

可以想像這些可能狀態是落在一處二維風景中,有時也稱為適切度風景(fitness landscape).每個可能解答的適切度或分數以風景中某一點的高度來表示.若相似的可能解有相近的分數,則相鄰的點有相似的高度,因此可以明確的定義出山丘及溪谷,找尋最佳解就等於尋找最高峰.

要搜尋這樣的空間,最簡單的方式就是隨機挑選一些點加以比較,並紀錄其中最好的點.這種方式所能搜尋的點數只受限於時間,而且它可以應用在任一空間上,這就好像叫一群傘兵跳到這風景的不同位置上,然後叫他們回報所在位置的高度.這種搜尋方式並不是很有效率.

在旅行推銷員問題這樣的搜尋空間裡,鄰近的點可能有著相近的分數,通常較適合的搜尋方式是在相鄰的點跟點之間遊走,就如在丘陵地上只有往上攀爬才能找到頂峰一樣,所對應的啟發式法則就是在搜尋空間裡選擇相鄰的兩解中最佳者.

這方法稱為登山法則(hill climbing),弱點在於你即使登上了某座山的山頂也不保證是最高的山頂.登山法則是一種啟發式法則,並非演算法.還有其他類似登山法則的啟發式法則,而且比較部會困於某座山的頂端.Ex.可由一些隨機抽出的位置開始反覆以登山法則向上攀豋,或往下走,避免困於山頂.登山法則這類的啟發式方法在處理旅行者問題時非常有效,它可以再短時間內得到一組不錯的解,即使有數千個城市,由合理的猜測為出發點,並逐次改善,找出最佳解.利用啟發式法則,我們幾乎能得到幾乎是最佳途徑.要想出針對旅行推銷員問題的迅速啟發式解法並不難,困難的是如何找到最快的演算法.

在許多問題上,並不需要每次都得到最佳解,只要一個能被接受的次佳解即可,因為即使有最完美的解答,我們也未必做得到.對這類的問題電腦會根據知識經驗猜出一個深思熟慮的答案,由於電腦能考慮的組合及可能性極多,因此它所做的猜測常常讓程式設計師驚訝.當電腦使用啟發式法則時,它可能讓我們驚喜,但不免犯錯,因此使它變得有點像人類而不像機器.