旅行商問題

又叫，係運算理論上一條好出名嘅難解問題。

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

問題

想像家陣有個 要去做推銷，佢攞住幅地圖，知自己要去勻香港、澳門、深圳、珠海、東莞、佛山、中山同廣州等多座喺珠江周圍嘅城市，然後佢自然想搵出一條最短可能路線，條路線要達到
行勻嗮咁多座城市、
每座城市淨係經過一次、兼且
起點同終點係同一笪地方
呢三點。

廣義化些少嘅話，旅行商問題可以當做任何
Input：攞幅有若干粒節點嘅圖，
Output：畀出一條最短可能嘅線，達致「去勻嗮啲節點、每粒節點淨係經過一次、起點同終點係同一點」。

解法

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

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

運算複雜度
滿足式決策

攷

運算理論