TSP的骨架算法綜述

　　1967年，blum教授在深入研究圖形學(xué)有關(guān)算法的基礎(chǔ)上提出了骨架的概念。他假設(shè)圖形邊界點同時著火，火源向圖形內(nèi)部各個方向等速燃燒直至熄滅，所有熄滅點就構(gòu)成了該圖形的骨架，這是骨架的最早定義。經(jīng)過將近半個世紀的發(fā)展，逐步形成了模擬燒草模型、基于距離變換以及voronoi圖等用于圖形檢索、路徑導(dǎo)航等圖形學(xué)難題的有效算法。

　　骨架算法在圖形學(xué)上的成功，引起學(xué)術(shù)界的廣泛關(guān)注。1995年Boese教授將骨架概念引入TSP研究領(lǐng)域，1998年Monasson等討論了可滿足性問題SAT的骨架算法；2005年Zou等提出了求解QAP問題的近似骨架導(dǎo)向蟻群算法ABFANT（approxlmate　backbone—guided fant）。其中，Boese教授的研究最為引人關(guān)注。他用隨機20pt、快速20pt、快速30pt、LK、LSMC等五種局部最優(yōu)算法對532點的TSP反復(fù)進行實驗，發(fā)現(xiàn)這些算法求得的局部最優(yōu)解與公布的最優(yōu)解竟有高達80%以上的共邊，Boese稱這一現(xiàn)象為大坑現(xiàn)象。

　　當TSP的哈密頓回路計算算法研究止步于局部最優(yōu)陷防時，1995年Boese教授發(fā)現(xiàn)了大坑現(xiàn)象，使骨架算法悄然進入了TSP研究領(lǐng)域。骨架算法在TSP邊識別方面正在取得進展。預(yù)言了骨架算法與脂肪算法相融合的必然趨勢。