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

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

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