2000/6/9 中國時報浮世繪版  數位世界說法 專欄

　

數位天下有難事

　

趙坤茂
　

在數位計算世界裡，有個很有名的問題稱為旅行推銷員問題：有一個推銷員，要到各個城市去推銷產品，他希望能找到一個最短的旅遊途徑，訪問每一個城市，而且每個城市只拜訪一次，然後回到最初出發的城市。如果只有幾個城市要訪問，我們很快就可以找出一個最短的旅遊途徑，但如果有很多很多的城市要訪問時，那就會難倒目前所有的數位計算機了。這問題的關鍵在於，當我們要拜訪很多城市時，可能的拜訪順序組合是天文數字，而我們至今又沒有好的方法，可以快速決定最短的旅遊途徑。

還有一個問題，稱為小偷背包問題：有個小偷，光顧一家超級市場，他帶了一個背包來裝所偷的東西，假設他的背包最多只能裝三十公斤，而超市內的每樣東西有它的重量及價值，小偷背包問題是要找出最佳的偷法，使得背包內所裝的贓物總價值最高，且總重量又不超過三十公斤。這樣的一個問題居然也是難題！如果小偷用數位計算機來替他決定最好的偷法，在他得到答案前，可能早就被繩之以法了。

不僅如此，我們還可證明，小偷背包問題和旅行推銷員問題的精確解法，它們的難度是一樣的，也就是說，只要其中有一個存在有效率的精確解法，另一個也會存在有效率的精確解法。實際上，在數位計算世界裡，已有數以萬計的問題，被證明為和旅行推銷員問題同樣難度，真是不可思議吧！

如果您的老闆交代您一個數位計算問題，您苦思多日仍無有效率的解法，您可以試著證明它和旅行推銷員問題同樣難度，然後告訴您的老闆說，即使全世界最厲害的資訊學家，也沒有這個問題的有效解法，這樣就不會被炒魷魚喔！

面對這一類型難題，我們是否真的束手無策呢？

十幾年前，如果您證明某一個問題是屬於這一類型的問題，那可算是一篇精采的博士論文。可是現在如果您找到了新的難題，那還不夠，您還必須提出好的近似解法(在有效率的時間內，找到和最佳解答差不多的近似答案)，才稱得上是水準之作。

很有意思的是，雖然我們說小偷背包問題和旅行推銷員問題的精確解法一樣難，但它們的近似解法卻南轅北轍。我們可以證明，旅行推銷員問題不太可能存在好的近似解法；而小偷背包問題卻已有很好的近似解法， 怪不得很少有小偷在超市當場被抓包囉。

高難度的數位計算問題，是演算法專家最重要的食糧。各式各樣的難題，雖然令人費盡心思，但它的滋味就如同山珍海味。如果沒有問題傷腦筋，那才真是傷腦筋的問題呢！