貪心算法求解TSP旅行商問(wèn)題

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

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

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