旅行中的商人與負世界

Posted By Mr. Thursday

 在《從尋找質數談談搜尋演算法》一篇文章裡面提到質數搜尋演算法,約略提到了一點演算法 (Algorithm) 以及 搜尋(search) 演算法。簡單地說,搜尋演算法就是要在一堆可能是答案的輸入資料 (input data) 當中,找出符合條件的答案。之前在《排程問題與CPU Scheduling》裡面提到了Job-Shop Problem是一個很難的排程問題 (Scheduling Problem),是NP-complete。本篇就簡單介紹一下搜尋演算法、「旅行中的商人」這個問題如何使用搜尋演算法、NP-complete的定義、以及最後提一下對偶問題(Dual Problem)。

algorithm

首先,演算法就是一堆步驟 (step),包含了循序漸進,第一步到最後一步逐次執行,以及依照情況分支,當某個情況成立的時候執行走一條路,不成立的時候走另外一條路,也就是If-then-else的流程。最後還包括反覆執行某一些步驟,一直到某個情況成立或不成立才離開這個迴圈,也就是 loop 的流程。在一般WORD或是POWERPOINT裡面化流程圖的時候,也都包含這幾個大項目!搜尋演算法也不外乎是上面這三種方法的組合,在不同的情況下執行不同的步驟。那麼「旅行中的商人」是甚麼樣子的問題,搜尋演算法要如何找到這個問題的解答呢? 

 旅行中的商人         旅行中的商人          旅行中的商人  

旅行中的商人 (Travelling Salesman Problem) 這個問題,是說一個商人要拜訪 N 個城市,並且知道城市和城市之間旅行的費用,要怎樣子依序拜訪各個城市,才能夠用最少的旅費,拜訪到每個城市,而且每個城市剛好拜訪一次。

接著我們就來看看,這個問題需要的解答是:花費最少的旅費拜訪每一個城市剛好一次。這個問題的輸入資料 (input data) 是:城市和城市之間所需要的旅費。可能的解答以及搜尋演算法需要尋找的可能組合是:各種拜訪城市的順序,譬如說先拜訪城市1、城市2、…、一直到城市n,或是先拜訪城市1、接著城市3、然後城市4、…、城市n、最後才拜訪城市2。每一種拜訪的順序,需要花費的旅費都不相同,搜尋演算法就要在這些組合裡面,找到一種拜訪順序,旅費最便宜,就是答案了!

至於這麼多種組合,要怎樣子列出來呢?假設今天有4個城市要拜訪,分別是台北、高雄、北京、上海。然後我們在地圖上面把這4個城市標記起來,用直線連起來,在上面寫上旅途所需要的花費。在這邊還有一步是解決問題的時候滿重要的,就是「抽象化」。

 抽象化         抽象化         抽象化 

抽象化,就是再解決問題的時候,只注意到問題相關的部分,不相關的部分可以先剔除掉,讓我們專注在解決問題相關的地方。像剛才的例子裡面,我們不用注意每個城市的大小,因此每個城市在地圖上,用一個「」來代表就可以。我們也不用注意每個城市之間有沒有經過海、經過山脈、經過河流,我們只要知道城市之間旅費要多少,因此用一個「」來代表城市之間的連線,然後在上面寫上旅費就可以了!因此一張地圖,就抽象化成「」和「」(verteces and edges, nodes and links),我們只要在這個由點和邊所組成的簡化的 (graph) ,就可以解決問題,原來有各種地形細節的地圖,就可以先暫時放在一邊了。下面就是一個範例的抽象過的 (graph)。

graph2 

各種組合         各種組合         各種組合 

 所以如果有N個城市,要照題目所說的每個城市剛好走訪一次,總共有幾種走法呢?答案是 $latex \frac{1}{2} (N-1)!$ 。上面N=4的時候,就有 3 種走法。如果台北、高雄、北京、上海分別用T, K, B, S代表的話,這三種走法就是:TBSKT, TBKST,  TKBST。這些走法如果要設計一個演算法,也就是一堆步驟來完成的話,可以像是這樣子:

(1) 從第1個點開始

(2) 列出這個點還沒拜訪過的邊

(3) 沿著其中一個沒拜訪過的邊走

(4) 如果走回起點,而且每個城市都已經剛好走過一次,那麼就計算花費成本,留待最後比較。

(5) 否則,判斷是否還有其他沒拜訪的邊,有的話回到步驟2。

(6) 否則,先回到來到這個點之前走過的點,再重覆步驟2。

 演算法 演算法 演算法

我們可以看到,演算法的步驟就是三種方式:循序漸進、依照不同情況分支、以及重覆執行。有些問題可以用數學公式計算出來,也可以用演算法的方式,由電腦執行跑出結果,雖然兩者都會用到數學,但是使用的方式有一些不同。譬如說PCA (Principle Component Analysis) 可以用矩陣運算來求解答,也可以由一個SOM (self-organized Map) 類神經網路來求出,類神經網路裡面的每一個點都是執行固定的步驟,但是所有的神經元依照這些步驟一起運轉的時候,PCA的解答就能夠從這個類神經網路中計算出來了!

那麼這個問題又和NP-complete有甚麼關係呢?我們可以發現到,這個問題如果要求出正確的解答,非得要一個一個組合計算花費的成本,然後找出最便宜的一個走法。NP其實是Non-deterministic Polynomial的縮寫,意思是只在一個Non-deterministic的Turing Machine上面,花費polynomial的時間複雜度,可以解決這個問題。看到這邊不知道會不會被嚇到,沒聽過Turing Machine,Non-deterministic是甚麼呢?這個也是說來話長,讓我嚐試著用白話文來解釋一下好了。

跳過去        跳過去        跳過去

首先,Turing Machine是一種「計算」的架構,由Alan A. Turing在1936年所提出。這個機器有個紀錄的空間,有個讀寫頭,機器可以辨認的符號表格狀態紀錄表格,還有一個行動準則對應表,這個對應表負責檢查目前機器處在甚麼狀態,讀寫頭現在讀到甚麼符號,然後決定下一個時間,讀寫頭要往左還是往右移機器的狀態要改變成哪一個狀態。因為這個機器能夠模擬現在每一台電腦的基本架構,以及評估每一個演算法的複雜度,因此電腦科學裡面,把各種可以計算的問題做分類的時候,就是依據Turing Machine。

和Non-deterministic對應的就是deterministic了。Deterministic在這邊是指Turing Machine裡面的行為準則對應表,每一次改變狀態的時候,只要前一步的狀態確定,下一步的狀態是確定可預測的。Non-deterministic的行為準則表,則是前一步的狀態即使都一樣,下一步的狀態是不可預測的,有兩種以上的可能。因此non-deterministic Turing Machine的計算能力會比Deterministic Turing Machine的計算能力多。也因此同樣是polynomial的時間複雜度,NP的問題會比P來的難。至於NP是否等於P,目前是仍未解決的問題。講到這邊覺得還是不夠白話,也許不懂的讀者可以先跳過這兩段,待日後另外一篇文章再詳細解說。

知道了NP怎麼來以後,NP-complete的定義就簡單了。一個問題如果是NP,而且又是NP-hard,那麼這個問題就是NP-complete。之前提到的Job-Shop Problem和今天提到的Travelling Salesman Problem,都是NP-complete的問題。不過可能會問,NP-hard是甚麼呢?NP-hard是指某個問題可以化約成另外一個NP-complete的問題,就是NP-hard了。也就是說,如果A問題可以化約成B問題,就代表說,如果B問題解決了,A問題就跟著解決,也就是A問題比B問題難一點的意思。(有學過計算理論的話,補充一下化約過程是要polynomial-reducible) 經由這個化約的過程,我們可以一直化約,把各個問題組織成一個化約關係的樹。如下圖

TSP就是今天提到的Travelling Salesman Problem,在圖中我們可以看到這個問題可以化約成Hamilton Cycle的問題,然後Hamilton Cycle問題又可以化約成Vertex Cover的問題,到最後化約成CNF-SAT問題(Conjunctive Normal Form – SATisfiability)。今天可能沒辦法一個一個問題慢慢講,然而這張圖代表的就是說,只要CNF-SAT這個問題解決,Vertex Cover就跟著解決,Hamilton Cycle就跟著解決,然後今天的問題TSP (旅行中的商人) 也就跟著解決了!

 對偶問題        對偶問題        對偶問題

最後提一下對偶問題 (Dual Problem)。所謂對偶問題,就是兩個問題其實是一體兩面,解決其中一個問題,另外一個問題就跟著解決,即使兩個問題表面上看起來不大一樣。舉剛才旅行中的商人的例子來說,我們已經把城市和路線,抽象化成了。如果今天要解決的問題,是一隻螞蟻想要爬一個有稜角的石膏像,要走完每一個切面,然後不同切面之間有不同的成本。這個時候我們可以把每個切面,對應到剛才抽象圖裡面的,兩個相鄰的切面,變成剛才相鄰的城市。這兩個問題就互相變成是Dual Problem了!

對偶問題有些像是文學裡面的對聯,或是巴哈的螃蟹卡農曲(Crab Canon)是前面彈過來、後面彈過去,都是相同旋律的歌曲(由前往後WAV, 由後往前WAV, 網頁)。細胞裡面的RNA也有Palindrome,就是頭尾兩個方向讀起來都是一樣的序列。對聯、對偶、對仗,都是有一樣的地方,也有不一樣的地方,才顯現出美感。一樣的地方是因為詞性 (part-of-speech) 要相同,不一樣的地方是因為要不一樣。這個台語版對穿腸,裡面的對聯段落算是詼諧有趣,有興趣的人不妨觀賞一下對聯之美!

因此對偶問題就好像是「負世界」一般,有點像是鏡子裡面另外一個世界,有點像是影子的世界,和我們生活的世界有一樣的地方,卻又有不一樣的地方。但最重要的是,解決其中一個問題,另外一個問題就跟著解決。所以對偶問題這個方法也常常用在,轉換後的對偶問題比較容易解答的情況,這時候就先把原來的問題轉換成對偶問題,解出答案以後,再把答案用同樣的方法轉換回原來的問題,就變成原來問題的答案了。

今天我們的機率理論有兩個重要的規定是:(1) 所有事件機率加起來要等於1。(2) 每一個事件的機率大於等於0。如果哪一天有個人發明了一套新的機率理論,讓機率可以是的,甚至有虛數的機率,那也許又是人類文明的新的一個里程碑 (Negative Probability)。從這篇文章的最前面到現在,我們了解到,至少在電腦科學領域,有這麼多等待解決的問題,也有這麼多方法。每個解答的出現,都讓人類的文明往前一步。對研究有興趣的人們,就讓我們繼續努力不懈,人類就能不斷地進步了!

Wikipedia參考資料

喜歡這篇文章嗎? 分享出去給作者一點鼓勵吧!