电路板布线问题的一种近似算法

• 作者: 姚如贵 徐娟 李战怀
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 电路板布线 贪婪算法 回溯法 NPC
• 年，卷（期）: 2005,（23）
• 所属期刊栏目: 工程与应用
• 页码范围: 227-229
• 页数: 3页
• 分类号: TP31
• 字数: 4071字
• 语种: 中文
• DOI: 10.3321/j.issn:1002-8331.2005.23.070

摘要

论文首先说明电路板布线问题是一个NPC问题.因此,当问题规模增大时,通常在多项式时间内算法不可解.鉴于此,提出一种"贪婪算法+回溯法"的近似算法,以期在多项式时间内找出次优解.经过程序验证,论文提出的近似算法,在一定精度要求下,解决电路板布线问题可行的.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李战怀	西北工业大学计算机学院	254	2139	21.0	35.0
2	姚如贵	西北工业大学电子信息学院	45	125	6.0	7.0
3	徐娟	西北工业大学计算机学院	15	52	5.0	6.0