旅行商問題travelingsalesmanproblem(tsp)(編輯修改稿)
2025-08-15 18:43 本頁面
【文章內(nèi)容簡介】 工作 ? 運輸問題是 TSP 最自然的應(yīng)用。由于其模型的簡單性，TSP 在其它一些領(lǐng)域有著有趣的應(yīng)用。一個經(jīng)典的例子是如何安排機器在一塊電路板或其他物體上鉆孔，其中需要鉆的孔可以看成是各個城市，而旅行的費用就是鉆頭從一個孔移到下一個孔所花的時間。雖然鉆孔的技術(shù)不斷發(fā)展，但無論何時，只要鉆機設(shè)備的移動時間在所有制造業(yè)的過程中占據(jù)顯著的地位， TSP 在減少費用上就扮演了一個非常重要的角色。 ? 許多實際中出現(xiàn)的問題都可以轉(zhuǎn)化成旅行商問題的模型而解決。例如還有結(jié)晶學中的結(jié)構(gòu)分析問題，車輛調(diào)度問題，計算機布線問題，單個機器上的工序調(diào)度問題等等。 旅行商問題的計算復(fù)雜性 ? 時間復(fù)雜性，即隨著輸入問題規(guī)模的增長，算法所需計算步數(shù)的增長速度。 ? 計算機科學家們有一個共識：即當輸入規(guī)模 n表示的算法復(fù)雜性函數(shù) f (n)是以多項式為界的，算法才被認為是有效的。 ? 從本質(zhì)上講，所有的計算問題又可以歸結(jié)為判定問題，如果說：一個算法解決了某一判定問題，則算法輸出“是”，否則輸出“非”。而從輸入到輸出，算法所需要運行的步驟即為算法的時間復(fù)雜性。 ? 很多優(yōu)化問題，諸如旅行商問題、最小覆蓋問題、多處理器任務(wù)調(diào)度問題、背包問題等都被發(fā)現(xiàn)可以多項式約化為 NP 中最難的問題，即 NP 完全問題。 ? 普遍認為多項式時間的算法是“好的算法”、“有效的算法”，而所有的 NP 完全問題目前都還沒有找到多項式時間的算法，它們需要耗費時間復(fù)雜性函數(shù)的數(shù)量級往往是指數(shù)級的，所以單單依靠提高計算機的速度對問題的解決是非常有限的 TSP的時間復(fù)雜度 ? TSP 搜索空間隨著城市數(shù) n 的增大而增大，所有的旅程路線組合數(shù)為 ( n 1)!/2。 ? 5 個城市的情形對應(yīng) 120/10=12 條路線； ? 10 個城市的情景對應(yīng) 3628800/20=181440 條路線； ? 100 個城市的情景對應(yīng)有 10155 條路線。 ? 所以對于輸入規(guī)模為 n個城市的 TSP 找到最優(yōu)解的時間復(fù)雜性函數(shù)的數(shù)量級是 O( n!)，當 n 比較大時，耗費的時間已經(jīng)是個天文數(shù)字。 ? 表 是在假定所用計算機每秒可以執(zhí)行 10 億次運算的前提下，對不同的時間復(fù)雜性函數(shù)所耗費時間的比較。 求解旅行商問題的已有算法 ? 多年來對 TSP 的研究，人們提出了許多求解方法，其中有 精確算法 如線性規(guī)劃方法、動態(tài)規(guī)劃方法、分支定界方法； ? 近似算法 如插入法、最近鄰算法、 Clarkamp。Wright 算法、生成樹法、 Christofides 算法、 ropt 算法、混合算法、概率算法等。 ?
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1