TSP的骨架算法綜述

　　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稱(chēng)這一現(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ì)。