开沟布线问题的模型及算法研究

• 作者: 林海旦 赵葆华
• 来源期刊: 杭州电子科技大学学报（自然科学版）
• 关键词: 开沟布线 最短路径树 最小生成树 邻域搜索
• 年，卷（期）: 2006,（2）
• 页码范围: 39-42
• 页数: 4页
• 分类号: TP301
• 语种: 中文
• DOI: 10.3969/j.issn.1001-9146.2006.02.011

摘要

开沟布线问题定义为由最短路径树和最小生成树这两个问题组合而成的组合优化问题,是一个新提出的、易于描述的却难于处理的NP完全问题.该文将图论、组合优化以及CNRP等技术相结合来对开沟布线问题进行了探索和研究,在指定一些约束的基础上建立的的数学模型较准确的描述了开沟布线问题的实质.给出了求解该问题的最直观简单的方法SP-MST求解法.并引入邻域搜索策略,在CTPHERUR1算法的基础上,提出了基于2-交换邻域搜索的改进算法,实验表明,该算法得到的近似解更接近最优解.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	林海旦	杭州电子科技大学计算机学院	31	258	9.0	15.0
2	赵葆华	杭州电子科技大学计算机学院	11	50	5.0	7.0