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

摘要：

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

关键词：电路板布线、贪婪算法、回溯法、NPC

所属期刊栏目：41

分类号：TP31(计算技术、计算机技术)

在线出版日期：2005-11-03（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：227-229