摘要
布局问题属于ＮＰ－完全问题已被研究多年．模拟退火法是一种新的通用启发式优化算法，现已广泛用于解决大规模集成电路逻辑布线设计、图象处理等组合优化问题．本文通过对布局问题及模拟退火算法的分析，将它们综合起来构成了求解布局问题的模拟退火算法．计算结果表明，本文算法得到的解优于传统优化方法所得到的解；文章还通过实验对算法中各参数所起作用进行了论述．
Packing problems which belong to NP complete problems have been studied for many years. As a kind of new heuristic optimization method, simulated annealing algorithm has been applied to some combintorial optimization problems such as VLSI design and image processing. According to the analysis on packing problems and simulated annealing algorithm, this paper presents a simulated annealing packing algorithm which can be used to solve packing problems. The calculating results show the algorithm can obtain a better solution which cann′t be gotten by traditional optimizatoin algorithm. The paper also discusses some parameter′s roles in the algorithm by several examples.
出处
《计算机辅助设计与图形学学报》
EI
CSCD
北大核心
1998年第3期253-259,共7页
Journal of Computer-Aided Design & Computer Graphics
关键词
布局问题
模拟退火算法
NP-完全问题
packing problems, simulated annealing algorithm, hillclimbing, global optimum, NP complete problems
