運算問題

喺理論電腦科學上，一條運算問題wan6 syun3 man6 tai4（英文：computational problem）係一嚿數學物體，代表一個或者一拃可以用電腦（運算機械）解決嘅問題。

圖靈機

内文：圖靈機

圖靈機（Turing machine）係廿世紀運算理論最常分析嘅運算模型。

一部圖靈機嘅運作如下：一部圖靈機會讀取一條分做若干個格嘅帶，條帶每個格裏面都會有個符號（可以係 1 同 0 等多個款）；喺每一個時間點，部圖靈機個讀取器都會位於條帶其中一格，而部機就會做以下三個基本作業當中是但一個：

1. 讀取讀取器下嗰格係乜符號；
2. 編輯嗰格－寫一個新嘅符號落去或者刪除咗嗰格佢；
3. 將條帶向左或者向右移一格，等個讀取器可以讀取打前嗰個格隔蘺嘅一個格。

一條圖靈機輸入帶嘅抽象圖解；$s_{i}$ 代表第 $i$ 款符號。

圖靈機呢部抽象機械就噉睇好似好簡單，但查實可以計到好多嘢。

例：圖靈機計加減法

想像以下嘅演算法，條帶上面有兩個數值，$x$ 同 $y$，兩個都用二進制表達，而兩個數之間同條帶嘅起始有個 $ 做標示，即係話部機會讀嘅輸入會類似噉嘅樣：

• $0010$0011（0010 喺二進制係 2，而 0011 喺二進制係 3）。

再想像部圖靈機跟以下嘅演算法行：

// 由 x 嗰度減 1，再加 1 落 y 嗰度，直至 x = 0 為止。
repeat until x == 0, then HALT {
 // 用 T2（睇下面）
 subtract 1 from x
 // 用 T1（睇下面）
 add 1 to y

 go back to the first $
}

T2（將個數減 1）如下：

1. 攞補充－將 1 冚唪唥變做 0，0 冚唪唥變做 1；
2. 將個數加 1（睇 T1）；
3. 再做一次補充。

T1（將個數加 1）如下：

1. 如果喺個數嘅左邊盡頭（$）起始，行去個數嘅右邊盡頭；
2. 由右邊開始行，將所有 1 變做 0，直至
3. 將第一個 0 變成 1。

例如如果輸入係 $0010$0011，部機行完一次段演算法之後，條帶嘅狀態就會變成 $0000$0101（0101 喺二進制入面係 5）－呢一部圖靈機曉做加減數。

複雜度

睇埋：運算複雜度理論

Info：旅行商問題

旅行商問題（travelling salesman problem）係一條好出名嘅難解問題。想像家陣有個 sell 士seu1 si2要去做推銷，佢攞住幅地圖，知自己要去勻香港、澳門、深圳、珠海、東莞、佛山、中山同廣州等多座喺珠江周圍嘅城市，然後佢自然想搵出一條最短可能路線，條路線要達到

1. 行勻嗮咁多座城市、
2. 每座城市淨係經過一次、兼且
3. 起點同終點係同一笪地方

呢三點。廣義化些少嘅話，旅行商問題可以當做任何

• Input：攞幅有若干粒節點嘅圖，
• Output：畀出一條最短可能嘅線，達致「去勻嗮啲節點、每粒節點淨係經過一次、起點同終點係同一點」。

呢條問題就噉望落好似好簡單，但事實表明佢係條難解問題：想像家陣用窮舉搜尋嚟解旅行商問題，將啲可能路線組合冚唪唥睇嗮佢－睇勻「香港-深圳-東莞-...」同「香港-深圳-珠海-...」... 如此類推等咁多個組合，噉做嘅時間複雜度會係

$O(n!)$

咁多，當中 $n$ 係指節點嘅數量。呢個情況極冇效率（可以睇返上面大 O 符號相關嘅圖表），個 $n$ 大些少已經會搞到部機做唔到「喺有限時間內出答案」；而且上面呢個情況只係最簡單嗰隻旅行商問題－如果要响現實世界解旅行商問題，部機仲起碼要考慮埋「每條路線成本都唔同」噉嘅問題，因為正常嚟講條條路嘅特性（長度同塞車嘅機率呀噉）都唔同。自從廿世紀起，旅行商問題就吸引咗好多電腦科學同商學工作者嘅關注，例如一間企業會想計劃自己送貨路線嗰陣，就要面對好似旅行商問題噉嘅情況－送貨路線設計得唔好，會搞到燃料等嘅成本明顯上升。

用德國做旅行商問題嘅例子。圖入面見到柏林。 用德國做旅行商問題嘅例子。圖入面見到柏林。  旅行商問題嘅抽象圖解 旅行商問題嘅抽象圖解   喺現實，仲要考慮埋路線嘅成本，例如唔同路線長度唔同，上圖每條路線掕住嘅數－20、34、35 ...－表示咗佢個成本。 喺現實，仲要考慮埋路線嘅成本，例如唔同路線長度唔同，上圖每條路線掕住嘅數－20、34、35 ...－表示咗佢個成本。

睇埋

• 難解問題