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

Approximate Algorithm for Wiring

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

In this article,it is analyzed that wiring is a NPC problem.Therefore an approximate algorithm with Greedy and Back-trace is proposed.As the performance of the algorithm shown,this algorithm can work well for the wiring problem。