求解等圓packing問題的擬物擬人算法改進(jìn)策略研究.pdf

1、求解NP 難度問題是目前計(jì)算機(jī)科學(xué)技術(shù)的瓶頸任務(wù)，對于NP 難度問題的求解可能根本就不存在既完整又快速的算法。等圓packing 問題是一類典型的NP 難度問題，是當(dāng)今國際上公認(rèn)的研究NP 難度問題最天然最明了的試金石，設(shè)計(jì)高效的算法求解等圓packing 問題將為研究NP 難度問題提供重要的理論指導(dǎo)和實(shí)踐經(jīng)驗(yàn)。
　　 擬物擬人方法是黃文奇教授提出的求解NP 難問題的一個(gè)重要方法，其基本思想是到大自然和人類社會(huì)中去尋找解決困難數(shù)

2、學(xué)問題的智慧。
　　 擬物算法在求解等圓packing 問題時(shí)，存在計(jì)算后期的收斂速度相當(dāng)慢、盲目搜索等問題。針對擬物算法的不足，提出了以下幾點(diǎn)改進(jìn)策略：通過燒荒策略調(diào)整圓餅的移動(dòng)次序，充分利用圓餅每次移動(dòng)的信息，加快了算法的演化速度；通過橫向搜索策略解決在全局最小值附近可能出現(xiàn)勢能下降停滯不前的問題；通過“安樂死”策略預(yù)測擬物法中搜索過程的前景，在一定程度上避免了搜索的盲目性；通過減少計(jì)算過程中對得到的新格局是否為最優(yōu)格局的判