TSP的骨架算法綜述
推薦 + 挑錯(cuò) + 收藏(0) + 用戶評(píng)論（0）
1967年，blum教授在深入研究圖形學(xué)有關(guān)算法的基礎(chǔ)上提出了骨架的概念。他假設(shè)圖形邊界點(diǎn)同時(shí)著火，火源向圖形內(nèi)部各個(gè)方向等速燃燒直至熄滅，所有熄滅點(diǎn)就構(gòu)成了該圖形的骨架，這是骨架的最早定義。經(jīng)過(guò)將近半個(gè)世紀(jì)的發(fā)展，逐步形成了模擬燒草模型、基于距離變換以及voronoi圖等用于圖形檢索、路徑導(dǎo)航等圖形學(xué)難題的有效算法。
骨架算法在圖形學(xué)上的成功，引起學(xué)術(shù)界的廣泛關(guān)注。1995年Boese教授將骨架概念引入TSP研究領(lǐng)域，1998年Monasson等討論了可滿足性問(wèn)題SAT的骨架算法；2005年Zou等提出了求解QAP問(wèn)題的近似骨架導(dǎo)向蟻群算法ABFANT（approxlmate backbone—guided fant）。其中，Boese教授的研究最為引人關(guān)注。他用隨機(jī)20pt、快速20pt、快速30pt、LK、LSMC等五種局部最優(yōu)算法對(duì)532點(diǎn)的TSP反復(fù)進(jìn)行實(shí)驗(yàn)，發(fā)現(xiàn)這些算法求得的局部最優(yōu)解與公布的最優(yōu)解竟有高達(dá)80%以上的共邊，Boese稱這一現(xiàn)象為大坑現(xiàn)象。
當(dāng)TSP的哈密頓回路計(jì)算算法研究止步于局部最優(yōu)陷防時(shí)，1995年Boese教授發(fā)現(xiàn)了大坑現(xiàn)象，使骨架算法悄然進(jìn)入了TSP研究領(lǐng)域。骨架算法在TSP邊識(shí)別方面正在取得進(jìn)展。預(yù)言了骨架算法與脂肪算法相融合的必然趨勢(shì)。
非常好我支持^.^
(0) 0%
不好我反對(duì)
(0) 0%
下載地址
TSP的骨架算法綜述下載
相關(guān)電子資料下載
- 三大法寶PSpice、LTspice、Multisim噪聲分析誰(shuí)更準(zhǔn)？怎么查看噪聲功率有效值？ 59
- macOS版LightSpy監(jiān)控系統(tǒng)利用WebKit漏洞竊取用戶數(shù)據(jù) 274
- OpenHarmony鴻蒙南向開發(fā)案例：【智能貓眼（基于3516開發(fā)板）】 255
- 使用LTspice搞定工程電源和MEMS信號(hào)鏈模擬 261
- 中軟國(guó)際CTSP云服務(wù)加速企業(yè)數(shù)智再造，創(chuàng)新升級(jí) 468
- 如何利用LTspice輕松模擬工程電源與MEMS信號(hào)鏈設(shè)計(jì) 375
- 電路仿真軟件哪個(gè)用的最多 449
- 電路仿真軟件哪個(gè)更實(shí)用 684
- 開拓大模型新邊界，蘋芯展示存算一體“芯”方向 436
- Groq推出大模型推理芯片 超越了傳統(tǒng)GPU和谷歌TPU 617