旅行商問題leoi5 hang4 soeng1 man6 tai4英文travelling salesman problem),又叫旅行推銷員問題leoi5 hang4 teoi1 siu1 jyun4 man6 tai4,係運算理論上一條好出名嘅難解問題

自從廿世紀起,旅行商問題就吸引咗好多電腦科學商學工作者嘅關注。例如一間企業會想計劃自己送貨路線嗰陣,就要面對好似旅行商問題噉嘅情況-送貨路線設計得唔好,會搞到燃料等嘅成本明顯上升[1]

問題 編輯

睇埋:難解問題圖論

想像家陣有個 sell 士seu1 si2要去做推銷,佢攞住幅地圖,知自己要去勻香港澳門深圳珠海東莞佛山中山廣州等多座喺珠江周圍嘅城市,然後佢自然想搵出一條最短可能路線,條路線要達到[2][3]

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

呢三點。

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

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

解法 編輯

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

 

咁多,當中   係指節點嘅數量。呢個情況極冇效率(可以睇吓大 O 符號相關嘅圖表),個   大些少已經會搞到部機做唔到「喺有限時間內出答案」;而且上面呢個情況只係最簡單嗰隻旅行商問題-如果要响現實世界解旅行商問題,部機仲起碼要考慮埋「每條路線成本都唔同」噉嘅問題,因為正常嚟講條條路嘅特性(長度塞車嘅機率呀噉)都唔同[4]

睇埋 編輯

編輯

  1. 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.
  2. Jünger, M., Reinelt, G., & Rinaldi, G. (1995). The traveling salesman problem. Handbooks in operations research and management science, 7, 225-330.
  3. Applegate, D. L., Bixby, R. E., Chvátal, V., & Cook, W. J. (2011). The traveling salesman problem. In The Traveling Salesman Problem. Princeton university press.
  4. 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.