计算机辅助设计与图形学学报
計算機輔助設計與圖形學學報
계산궤보조설계여도형학학보
JOURNAL OF COMPUTER-AIDED DESIGN & COMPUTER GRAPHICS
2012年
6期
808-815
,共8页
刘景发%张国建%刘文杰%高泽旭%周子铃
劉景髮%張國建%劉文傑%高澤旭%週子鈴
류경발%장국건%류문걸%고택욱%주자령
等圆Packing问题%模拟退火算法%启发式格局更新策略%梯度法%二分法
等圓Packing問題%模擬退火算法%啟髮式格跼更新策略%梯度法%二分法
등원Packing문제%모의퇴화산법%계발식격국경신책략%제도법%이분법
等圆Packing问题研究如何将n个单位半径的圆形物体互不嵌入地置入一个边长尽量小的正三角形容器内,作为一类经典的NP难度问题,其有着重要的理论价值和广泛的应用背景.模拟退火算法是一种随机的全局寻优算法,通过将启发式格局更新策略与基于梯度法的局部搜索策略融入模拟退火算法,并与二分搜索相结合,提出一种求解正三角形容器内等圆Packing问题的启发式算法.该算法将启发式格局更新策略用来产生新格局和跳坑,用梯度法搜索新产生格局附近能量更低的格局,并用二分搜索得到正三角形容器的最小边长.对41个算例进行测试的实验结果表明,文中算法改进了其中38个实例的目前最优结果,是求解正三角形容器内等圆Packing问题的一种有效算法.
等圓Packing問題研究如何將n箇單位半徑的圓形物體互不嵌入地置入一箇邊長儘量小的正三角形容器內,作為一類經典的NP難度問題,其有著重要的理論價值和廣汎的應用揹景.模擬退火算法是一種隨機的全跼尋優算法,通過將啟髮式格跼更新策略與基于梯度法的跼部搜索策略融入模擬退火算法,併與二分搜索相結閤,提齣一種求解正三角形容器內等圓Packing問題的啟髮式算法.該算法將啟髮式格跼更新策略用來產生新格跼和跳坑,用梯度法搜索新產生格跼附近能量更低的格跼,併用二分搜索得到正三角形容器的最小邊長.對41箇算例進行測試的實驗結果錶明,文中算法改進瞭其中38箇實例的目前最優結果,是求解正三角形容器內等圓Packing問題的一種有效算法.
등원Packing문제연구여하장n개단위반경적원형물체호불감입지치입일개변장진량소적정삼각형용기내,작위일류경전적NP난도문제,기유착중요적이론개치화엄범적응용배경.모의퇴화산법시일충수궤적전국심우산법,통과장계발식격국경신책략여기우제도법적국부수색책략융입모의퇴화산법,병여이분수색상결합,제출일충구해정삼각형용기내등원Packing문제적계발식산법.해산법장계발식격국경신책략용래산생신격국화도갱,용제도법수색신산생격국부근능량경저적격국,병용이분수색득도정삼각형용기적최소변장.대41개산례진행측시적실험결과표명,문중산법개진료기중38개실례적목전최우결과,시구해정삼각형용기내등원Packing문제적일충유효산법.
