基于拓?fù)涓兄腡SP快速求解算法
本文選題：拓?fù)?/strong> 切入點(diǎn)：TSP 出處：《東南大學(xué)學(xué)報(bào)(自然科學(xué)版)》2014年03期
【摘要】：為了適應(yīng)無(wú)線傳感器網(wǎng)絡(luò)環(huán)境的特點(diǎn),提出了一種基于拓?fù)涓兄穆眯猩虇?wèn)題(TSP)啟發(fā)式快速求解算法.通過(guò)分析無(wú)線傳感器網(wǎng)絡(luò)拓?fù)渑cTSP解之間的關(guān)系,提出了基于最大公共同構(gòu)子圖的拓?fù)渚嚯x,并用于度量拓?fù)渲g的相似度.然后,以拓?fù)渚嚯x為標(biāo)準(zhǔn),對(duì)輸入拓?fù)溥M(jìn)行聚類(lèi)分析,繼而映射得出該輸入拓?fù)涞腡SP解.該算法設(shè)置了合適的剪枝條件以提高運(yùn)行速度,通過(guò)加入閾值參數(shù)來(lái)平衡類(lèi)內(nèi)拓?fù)溟g的相似度和聚類(lèi)類(lèi)別數(shù)目.仿真結(jié)果表明,在節(jié)點(diǎn)數(shù)為90和70的TSP環(huán)境下,這種拓?fù)涓兄惴ǖ倪\(yùn)行時(shí)間分別為0.615和0.508 s,約為L(zhǎng)in-Kernighan算法和蟻群算法的3%~4%,且其精確度介于這兩種算法之間.
[Abstract]:In order to adapt to the characteristics of wireless sensor network (WSN) environment, a fast heuristic algorithm based on topology awareness for traveling salesman problem (TSP) is proposed. The relationship between topology and TSP solution of WSN is analyzed. The topological distance based on the maximum common isomorphism subgraph is proposed and used to measure the similarity between topologies. Then the TSP solution of the input topology is obtained by mapping. The algorithm sets appropriate pruning conditions to improve the running speed, and balances the similarity between the topologies and the number of clustering categories by adding threshold parameters. The simulation results show that, In the TSP environment with 90 and 70 nodes, the operation time of this algorithm is 0.615 s and 0.508 s respectively, which is about 3 / 4 of Lin-Kernighan algorithm and ant colony algorithm, and its accuracy is between these two algorithms.
【作者單位】： 東南大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院;東南大學(xué)網(wǎng)絡(luò)和信息集成教育部重點(diǎn)實(shí)驗(yàn)室;
【分類(lèi)號(hào)】：TP212.9;TN929.5
【共引文獻(xiàn)】
相關(guān)期刊論文 前10條
1 張森;;改進(jìn)蟻群算法求解最短路徑問(wèn)題[J];電子世界;2013年16期
2 廖翊丞;唐秋玲;岳岫峪;李賢;鄭莉莉;;一種基于能量受限的移動(dòng)sink數(shù)據(jù)收集策略[J];廣西大學(xué)學(xué)報(bào)(自然科學(xué)版);2013年05期
3 劉雙;陳國(guó)雄;劉天佑;;改進(jìn)的蟻群算法及其在南嶺地區(qū)花崗巖侵入體探測(cè)中的應(yīng)用[J];吉林大學(xué)學(xué)報(bào)(地球科學(xué)版);2013年06期
4 孫騫;張進(jìn);王宇翔;;蟻群算法優(yōu)化策略綜述[J];信息安全與技術(shù);2014年02期
5 劉釗;羅智德;張耀方;高培超;謝美慧;;基于GIS的時(shí)空節(jié)點(diǎn)規(guī)劃與優(yōu)化方法研究[J];地理與地理信息科學(xué);2014年01期
6 劉海濱;劉國(guó)華;黃立明;宋金玲;;以業(yè)務(wù)單據(jù)為中心的業(yè)務(wù)流程模型聚類(lèi)及相似性查詢(xún)方法[J];計(jì)算機(jī)集成制造系統(tǒng);2013年08期
7 史嵐;張義宏;呂建輝;;基于絕對(duì)貪心和預(yù)期效率的0-1背包問(wèn)題優(yōu)化[J];計(jì)算機(jī)應(yīng)用研究;2014年03期
8 伍尚昆;陳翠宜;祝勝林;;基于多種群蟻群算法的交叉路口信號(hào)配時(shí)優(yōu)化[J];計(jì)算機(jī)應(yīng)用與軟件;2014年05期
9 馮禹;;基于改進(jìn)蟻群算法的定向問(wèn)題研究[J];物流工程與管理;2013年09期
10 張家善;王志宏;;基于信息素的改進(jìn)蟻群算法及其在TSP中的應(yīng)用[J];數(shù)學(xué)的實(shí)踐與認(rèn)識(shí);2013年22期
相關(guān)會(huì)議論文 前1條
1 王晨;陳增強(qiáng);;基于連續(xù)蟻群算法融合的神經(jīng)網(wǎng)絡(luò)RFID信號(hào)分布模型[A];2013年中國(guó)智能自動(dòng)化學(xué)術(shù)會(huì)議論文集（第三分冊(cè)）[C];2013年
相關(guān)博士學(xué)位論文 前9條
1 劉偉;城鄉(xiāng)一體化交通網(wǎng)絡(luò)配置研究[D];西南交通大學(xué);2012年
2 張汝陽(yáng);高維數(shù)據(jù)交互作用分析的統(tǒng)計(jì)方法研究及其在肺癌全基因組關(guān)聯(lián)研究中的應(yīng)用[D];南京醫(yī)科大學(xué);2013年
3 寇嘉梁;基于分片網(wǎng)絡(luò)的體育場(chǎng)人員疏散多目標(biāo)優(yōu)化研究[D];武漢理工大學(xué);2013年
4 譚陽(yáng);求解廣義旅行商問(wèn)題的若干進(jìn)化算法研究[D];華南理工大學(xué);2013年
5 阮殿旭;井下工作面設(shè)備無(wú)線監(jiān)測(cè)網(wǎng)絡(luò)與故障診斷關(guān)鍵技術(shù)研究[D];中國(guó)礦業(yè)大學(xué);2011年
6 金浩;基于改進(jìn)蟻群算法梯式軌道及橡膠混凝土隔振基礎(chǔ)優(yōu)化研究[D];北京交通大學(xué);2013年
7 劉寧;高心墻堆石壩施工場(chǎng)內(nèi)交通仿真與實(shí)時(shí)控制研究[D];天津大學(xué);2013年
8 李晴;基于優(yōu)化機(jī)器學(xué)習(xí)算法的模擬電路故障診斷研究[D];湖南大學(xué);2013年
9 王s鮯，
本文編號(hào)：1666600
本文鏈接：http://sikaile.net/kejilunwen/wltx/1666600.html
