首页   按字顺浏览 期刊浏览 卷期浏览 Performance comparison of conventional and backtracking algorithms in circuit routing
Performance comparison of conventional and backtracking algorithms in circuit routing

 

作者: D.J.Kinniment,  

 

期刊: IEE Proceedings G (Electronic Circuits and Systems)  (IET Available online 1980)
卷期: Volume 127, issue 6  

页码: 309-312

 

年代: 1980

 

DOI:10.1049/ip-g-1.1980.0051

 

出版商: IEE

 

数据来源: IET

 

摘要:

Backtracking allows a routing program to erase a track if it is blocking other connections; the erased track can then be rerouted at a later stage. This technique is investigated in the paper and compared with conventional methods. Backtracking can lead to program looping, which in this case is avoided by using two types of track, ‘permanent’ and ‘provisional’. Provisional nodes and edges may be erased at later stages but not permanent.Routing programs using backtracking are likely to be more complex and time consuming in execution, but to have a higher success rate in finding connections.A comparison is made in the paper between a router using an algorithm adapted to backtracking and a more conventional method using two passes. In the conventional router, the first pass is a simple heuristic and the second a full search using the Moore-Lee algorithm. Results from a selected set of printed-circuit board layouts show that a significant improvement in connection yield was obtained by the backtracking router, but at a cost of approximately four times the computer time.

 

点击下载:  PDF (541KB)



返 回