求解等圓packing問題的高性能近似算法.pdf

1、等圓packing問題是一類非常典型的NP難度問題，它不僅在工程上有廣泛的應用，更具有特殊的理論意義。20世紀70年代至今的計算復雜性理論表明，對于NP 難度問題可能根本就不存在多項式時間復雜度的求解算法，于是人們使用各種啟發(fā)式算法求此類問題的近似解。
　　 擬物算法最早由黃文奇教授提出，其基本的思路是設(shè)計算法模擬自然界彈性物體的擠壓運動。實踐證明擬物算法在求解一些NP難度問題是非常有效的，這里使用擬物算法求解等圓packing

2、問題就是一個很好的例子。
　　 在建立物理模型，并給出嚴格的數(shù)學定義后，設(shè)計出了模擬彈性實體相互擠壓運動過程的算法，即求解問題的原始擬物算法。在勢能函數(shù)的基礎(chǔ)上，結(jié)合眾所周知的最速下降法，得到了求解問題的擬物最速下降算法。
　　 在使用擬物算法求解問題時，計算經(jīng)常會落入局部最小值點。針對這個問題，提出了三種擬人策略：壓力解除策略，資源讓與策略，最痛苦者自救策略。在擬物算法的基礎(chǔ)上，分別結(jié)合這三種擬人策略，得到了幾個不同的