Performance comparison of conventional and backtracking algorithms in circuit routing

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.