跳去內容

運算問題

出自維基百科,自由嘅百科全書

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

圖靈機

[編輯]
内文:圖靈機

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

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

  1. 讀取讀取器下嗰格係乜符號;
  2. 編輯嗰格-寫一個新嘅符號落去或者刪除咗嗰格佢;
  3. 將條帶向左或者向右移一格,等個讀取器可以讀取打前嗰個格隔蘺嘅一個格。
一條圖靈機輸入帶嘅抽象圖解; 代表第 款符號。

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

例:圖靈機計加減法

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

  • $0010$00110010 喺二進制係 2,而 0011 喺二進制係 3)。

再想像部圖靈機跟以下嘅演算法行[4]

// 由 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$01010101 喺二進制入面係 5)-呢一部圖靈機曉做加減數[4]

複雜度

[編輯]

Info:旅行商問題

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

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

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

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

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

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

睇埋

[編輯]

[編輯]
  1. 引用錯誤 無效嘅<ref>標籤;無文字提供畀叫做hodges2012嘅參照
  2. Petzold, C. (2008). The annotated Turing: a guided tour through Alan Turing's historic paper on computability and the Turing machine. Wiley Publishing.
  3. 引用錯誤 無效嘅<ref>標籤;無文字提供畀叫做rabin2012嘅參照
  4. 4.0 4.1 4.2 引用錯誤 無效嘅<ref>標籤;無文字提供畀叫做turingmachineadd嘅參照
  5. Woeginger, G.J. (2003), "Exact Algorithms for NP-Hard Problems: A Survey", Combinatorial Optimization - Eureka, You Shrink! Lecture notes in computer science, vol. 2570, Springer, pp. 185-207.
  6. Ulyanov, M. V., & Fomichev, M. I. (2015). Resource characteristics of ways to organize a decision tree in the branch-and-bound method for the traveling salesmen problem. Бизнес-информатика, (4 (34)), 38-46.