旅行商問題

旅行商問題（參見英文：travelling salesman problem），又叫旅行推銷員問題，係運算理論上嘅難解問題。自從二十世紀起，旅行商問題就吸引咗好多電腦科學同商學工作者關注。例如一間企業想計劃自己送貨路線嗰陣，就要面對好似旅行商問題噉嘅情況－送貨路線設計得唔好，會令到燃料等嘅成本明顯上升^[1]。

基本問題

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

行勻晒咁多個城市，
每個城市淨係經過一次，兼且
起點同終點係同一笪地方

呢三點。

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

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

噉嘅問題。

喺現實，仲要考慮埋路線嘅成本，例如唔同路線距離唔同，上圖每條路線掕住嘅數－20、34、35 ...－表示咗佢個成本。

解決方法

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

O(n!)

咁多，當中 n 係指節點嘅數量。呢個情況極冇效率，個 n 大少少，部機已經唔能夠喺有限時間內出答案；而且依家只係諗緊最簡單嗰款旅行商問題－如果要响現實世界解旅行商問題，部機起碼仲要考慮埋好多問題，例如每條路線嘅成本（長度同塞車嘅機率）都唔同^[4]。

睇埋

引述

↑ 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.
↑ Jünger, M., Reinelt, G., & Rinaldi, G. (1995). The traveling salesman problem. Handbooks in operations research and management science, 7, 225-330.
↑ 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.
↑ 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.

[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.

[1]

[2]

[3]

[4]