摘要：电路划分是超大规模集成电路（VLSI）设计自动化中的一个关键阶段,是NP困难的组合优化问题.本文把基于顶点移动的Fiduccia-Mattheyses（FM）算法结合到分散搜索算法框架中,提出了电路划分的分散搜索算法.算法利用FM算法进行局部搜索,利用分散搜索的策略进行全局搜索.为满足该方法对初始解的质量和多样性的要求,采用贪心随机自适应搜索过程（GRASP）和聚类相结合的方法产生初始解.实验结果表明,算法可以求解较大规模的电路划分实例,且与基于多级框架的划分算法hMetis相比,划分的质量有明显的提高.

关键词：分散搜索 grasp fm算法 电路划分 

单位：福州大学数学与计算机科学学院; 福建福州350108