基于图论的VLSI中最小斯坦纳树问题及其改进算法

摘要

超大规模集成电路(VLSI)中,对于多端线网的最佳布线结果是构造最小直角斯坦纳树,该问题是典型的NP组合优化问题.利用图论中直角斯坦纳树的性质,在采用斯坦纳点编码方案寻找优化点位置的基础上,增加粒子趋同性判定及惯性权重系数调整策略,提出改进的粒子群优化算法,对一些实例模型进行了仿真测试,表明该算法的效果良好.