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

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

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