求解等圓packing問題的擬物擬人算法.pdf

1、等圓Packing問題是一類典型的NP-Hard問題。擬物擬人算法源自客觀世界和人類社會所蘊含的高度智慧，是求解等圓Packing問題的高效率啟發(fā)式算法。
　　 擬物算法的思路與傳統(tǒng)的數(shù)學(xué)模型恰恰相反：首先將待解決的純粹數(shù)學(xué)問題轉(zhuǎn)換成等價的物理模型，然后在客觀規(guī)律的啟發(fā)下求解該物理模型，最后將所得解轉(zhuǎn)換成原數(shù)學(xué)問題的解。對于等圓Packing問題，擬物算法在體系中引入彈性力的概念，讓體系在其作用下天然地向著更優(yōu)的方向演化，最終找

2、到問題的解。
　　 為提高效率，可在執(zhí)行擬物算法的過程中引入“安樂死”策略。該策略不斷估算當(dāng)前搜索路徑的希望大小，如果希望渺茫，則提前結(jié)束對當(dāng)前路徑的搜索，從而節(jié)省計算時間。
　　 當(dāng)求解的問題較困難時，僅采用擬物算法往往會陷入“局部陷阱”。為此，可借鑒人類社會的經(jīng)驗，設(shè)計出一系列跳離“局部陷阱”的擬人算法，包括“調(diào)走最痛苦者”、“解救最痛苦者”、“全局調(diào)整法”等。其中，“解救最痛苦者”方法是對“調(diào)走最痛苦者”方法的有效