旅行商問題

旅行商問題（粵音：leoi5 hang4 soeng1 man6 tai4 | 英文：travelling salesman problem），又叫旅行推銷員問題，係運算理論上一條好出名嘅難解問題。

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

問題

睇埋：難解問題同圖論

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

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

呢三點。

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

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

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

解法

睇埋：窮舉搜尋同最佳化

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

$O(n!)$

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

睇埋

• 運算複雜度
• 滿足式決策