基于直覺啟發(fā)的TSP求解方法及其在無線傳感器網(wǎng)絡(luò)中的應(yīng)用.pdf

1、旅行商問題(Traveling Salesman Problem，TSP)是一個經(jīng)典的組合優(yōu)化問題，有著眾多的應(yīng)用場景。隨著可移動節(jié)點在無線傳感器網(wǎng)絡(luò)(Wireless SensorNetwork, WSN)中的廣泛使用，在無線傳感器網(wǎng)絡(luò)領(lǐng)域出現(xiàn)了大量與移動節(jié)點相關(guān)的TSP應(yīng)用。在無線傳感器網(wǎng)絡(luò)環(huán)境下的TSP算法，既要解決旅行商問題時間復(fù)雜度的高的問題，又要考慮到無線傳感器網(wǎng)絡(luò)環(huán)境下資源的受限性、通信代價高等特點。論文針對無線傳感器網(wǎng)絡(luò)

2、中的旅行商問題算法展開研究，論文的主要工作和貢獻(xiàn)有:
　　(1)對現(xiàn)有TSP算法進(jìn)行分類整理，比較了現(xiàn)有TSP算法的性能和優(yōu)缺點。分析了在無線傳感器網(wǎng)絡(luò)環(huán)境下，TSP算法存在的通病?，F(xiàn)有TSP算法過于依賴距離位置信息，而在無線傳感器網(wǎng)絡(luò)環(huán)境下獲取準(zhǔn)確的位置信息過程困難，會增加傳感器節(jié)點的負(fù)擔(dān)。因此本文提出使用拓?fù)湫畔⑶蠼饴眯猩虇栴}。
　　(2)運用數(shù)學(xué)和圖論方法，使用無向無權(quán)圖描述無線傳感器網(wǎng)絡(luò)拓?fù)?。通過理論分析與數(shù)學(xué)推導(dǎo)，

3、分別構(gòu)建了直覺匹配模型和直覺聚類模型。直覺匹配模型強調(diào)了圖之間的相似度，直接對旅行商問題求解。直覺聚類模型強調(diào)了圖內(nèi)頂點的疏密關(guān)系，對旅行商問題進(jìn)行了分解。
　　(3)提出了直覺啟發(fā)框架用于求解TSP?？蚣馨?fù)涓兄惴ㄅc拓?fù)浞指钏惴▋蓚€步驟。并分別為拓?fù)涓兄惴ㄅc拓?fù)浞指钏惴ń⒘藬?shù)學(xué)模型。在直覺匹配模型的基礎(chǔ)上設(shè)計了拓?fù)涓兄惴?。拓?fù)涓兄惴ㄌ岢隽藞D之間相似度的計算方法，將輸入拓?fù)渑c拓?fù)涮卣鲙斓耐負(fù)溥M(jìn)行匹配。根據(jù)匹配結(jié)果映射