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

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

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

3、分別構建了直覺匹配模型和直覺聚類模型。直覺匹配模型強調了圖之間的相似度，直接對旅行商問題求解。直覺聚類模型強調了圖內頂點的疏密關系，對旅行商問題進行了分解。
　　(3)提出了直覺啟發(fā)框架用于求解TSP?？蚣馨負涓兄惴ㄅc拓撲分割算法兩個步驟。并分別為拓撲感知算法與拓撲分割算法建立了數(shù)學模型。在直覺匹配模型的基礎上設計了拓撲感知算法。拓撲感知算法提出了圖之間相似度的計算方法，將輸入拓撲與拓撲特征庫的拓撲進行匹配。根據(jù)匹配結果映射