貪心算法求解TSP旅行商問題

1、貪心算法求解貪心算法求解(TSP)(TSP) 旅行商問題旅行商問題- 問題描述旅行商問題（Traveling Salesman Problem, TSP）：有一個推銷員，要到n個城市推銷商品，他要找出一個包含所有n個城市的具有最短路程的環(huán)路。例如給定一個城市和城市間的距離集合，求經(jīng)過所有城市恰好一次的最短回路，即；給定圖G=(V，E，W)，其中V為頂點集合，|V|=n，E為邊集合，W為邊權(quán)函數(shù)，求集合1,2，n的一個排列使得下式最小。解決思路：借助矩陣把問題轉(zhuǎn)化為矩陣中點的求解：首先構(gòu)造距離矩陣，任意節(jié)點到自身節(jié)點的距離為無窮大(在這里我用100來表示無窮大)，在第一行找到最小項a1j，從而跳

2、到第j行；再找到最小值ajk，從而跳到第k行進行查找然后構(gòu)造各行允許數(shù)組rown=1,1，各列允許數(shù)組colablen=0,1,1，其中1表示允許訪問，即該節(jié)點未被訪問；0表示不允許訪問，即該節(jié)點已被訪問。如果該行或該列不允許訪問，則跳過該點訪問下一節(jié)點。核心算法說明：1）輸入節(jié)點數(shù)n和連接矩陣a2）定義行、列允許矩陣rown=1,1、rown=1,13）賦初值：s=0,i=04）While rowi=15） j=0,m=ai0,k=06） 找到第一個允許訪問的節(jié)點aij7） 尋找aijn-1中的最小元素8）End while特殊說明：程序在訪問最后一個節(jié)點錢，所訪問的行中至少有1個允許訪問的

3、節(jié)點，依次訪問這些節(jié)點找到最小即可：在訪問最后一個節(jié)點后，再次訪問，會返回k=0，即實現(xiàn)了訪問源節(jié)點。所以，各個節(jié)點都被訪問，且訪問路徑為一簡單回路。實例演示：例題：以4個節(jié)點為例，演示算法運行過程（以100表示無大）：輸入連接矩陣：100 3 9 23 100 1 49 1 100 72 4 7 100實例演示：運算過程：(1)(2)(3)(4)實例演示：對應連線圖：運行結(jié)果：貪心選擇性質(zhì)(n=2)：因為旅行商問題是一個典型的NP問題，找不到一個算法能保證在多項式時間內(nèi)得到最優(yōu)解。所以無需證明其貪心選擇性質(zhì)，而本算法只要求找到近似解，而在多項式時間內(nèi)結(jié)束。最優(yōu)子結(jié)構(gòu)性質(zhì)(n=2)：設(shè)sn是此問題的最優(yōu)解，那么可以把它分解為sn=s2+sn-1;假設(shè)存在sn-1為n-1規(guī)模是的最優(yōu)解，則sns2+sn-1,而這與假設(shè)矛盾，所以可以得出旅行商問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。程序?qū)崿F(xiàn)：定義數(shù)組，節(jié)點，函數(shù)代碼：程序?qū)崿F(xiàn)：主函數(shù)代碼：程序?qū)崿F(xiàn)：程序?qū)崿F(xiàn)：求最短距離函數(shù)代碼：Than