iT邦幫忙

2021 iThome 鐵人賽

DAY 27
0
自我挑戰組

30天不怕演算法:白話文版系列 第 27

Day 27:碰到困難問題,演算法也救不了?

上一回我們說旅行推銷員問題(TSP)是一個NP困難問題,沒有快速的演算法可以解決。

那一個問題怎樣叫做「困難」,演算法又要多快才叫做快呢?

如果說所有運算問題有容易與困難之分,NP困難的理論用明確的方式作出分野。不深入NP困難的定義、用最最簡單粗淺的方式來說,容易是指可以以多項式時間的演算法解決,困難是指最壞情況需要指數時間。

我們之前討論過的諸多演算法,如二分搜尋、快速排序...執行時間有O(n),O(log n)、O(n²)、O(n log n)等等。雖然這些執行時間各有不同,n的大小也會依實際問題有所變化,但它們的共通點是都是n的多項式倍數,或者說可以表示為O(n^c),其中c為一常數。這樣的演算法可以被稱為快速,而能以快速演算法正確解決的問題可以想為是容易的問題。

TSP被認為是困難問題,除了目前沒有快速演算法可以解決,我們甚至還無法證明這樣的快速演算法究竟是 1.存在但尚未找到,還是2.根本不存在,雖然多數科學家更傾向主張第二種情況[註1]。既無從證明快速演算法存不存在,當我們說一個問題困難時,並不是「絕對沒有快速解」的意思,它比較像一種相對的表達,指這個問題至少與其他許多還沒有快速解的困難問題一樣困難。

分辨困難問題

其實現實生活中碰到困難問題的機率並不低,那我們怎麼分辨一個問題是否困難,進而調整策略呢?

一種方法是先熟悉一些已知是困難的問題,碰到新問題時,可以察覺出它們是同一類型問題。例如假設碰到的新問題是要以一個順序解決一系列任務,而且每個任務的成本都跟前一個任務相關,那麼很有可能這其實是個TSP類型的問題,只是問題的描述或對象不同。

另一種方法是運用歸約(reduction)的技巧,進行問題之間的轉換,例如將一個困難的問題化為新問題,可以知道新的問題也是困難的。

應對困難問題

當在現實生活中遇到困難問題,使用已知的快速演算法硬解很有可能是徒勞的,這時候該怎麼辦呢?除非剛好問題規模很小,可以直接解決,不然通常會需在在幾個方面作出取捨。

  1. 可能必須為個別問題設計出適用的演算法。例如利用動態規劃解背包問題的例子,即是找到解決特定問題的子問題的方式。
  2. 放棄百分之百的正確性,例如使用貪婪演算法,得到可接受的近似解,並節省很多時間。
  3. 如果必須追求正確解,只能盡可能地縮短執行時間。也就是雖然沒有快速演算法可用,至少盡量避免暴力解決法這類最慢的方式,像是利用動態規劃解決TSP就是一個例子。

[註1]有興趣想要了解這個難題可以參考P/NP問題


上一篇
Day 26:旅行推銷員問題(TSP)
下一篇
Day 28:Diffie–Hellman演算法
系列文
30天不怕演算法:白話文版30

尚未有邦友留言

立即登入留言