|
現實世界中, 計程車司機的載客過程可視為供需問題. 就意義上而言, 供
需問題與事物出現的機率有關, 譬如顧客出現的機率, 競爭對手之多寡,
同時, 時間的進行也是重要的考慮因素. 這樣的問題並不單純, 於是我們
先把它簡化成不考慮時間, 已知顧客去處的單向搜尋問題, 然後檢視其複
雜度, 藉此一窺當面臨真正的供需問題時可能會遭遇的時間複雜度. 不幸
地, 我們發現簡化後的載客問題其實是 NP-complete, 於是我們決定把重
點指向簡化的載客問題上面.簡化後的載客問題還不夠簡單去證明 NP-
complete, 因為``顧客能隨意指定去處''使得計程車的行跡較難追蹤, 於
是我們又將問題簡化成去掉顧客去處的取寶問題. 取寶問題指``有一個尋
寶者已經知道有某些地方埋著寶藏, 我們想問在同時考慮路途花費和寶藏
利益的情況下, 尋寶者該怎麼走才能賺到最多錢?''因為取寶問題為這些
問題單純化的原始模型, 比較易於著手, 於是我們正式以取寶問題作為本
篇論文的主題.取寶問題與 TSP (Traveling Salesperson Problem) 有點
相像,該皆描述在圖形上遊走的最佳化問題. 但 TSP 中限制了頂點只能被
經過一次, 而取寶問題則不設此限; TSP 要求每個頂點都要被經過,取寶
問題也不須如此. 在取寶問題中, 除了給定邊代價外, 還給定頂點附加利
益. 我們將證明取寶問題是 NP-complete.本篇論文中, 我們將介紹三種
演算法來解決取寶問題並說明取寶問題和 TSP 實施演算法的不同處, 另
外還要介紹另一些相關的 NP-complete 問題.
|