Maze Router Applet - Hadlock's Algorithm
This applet demonstrates a variation on Maze Routing that
reduces the execution time compared to the Lee Algorithm. About Hadlock's
Algorithm Hadlock's Algorithm is a variation on the Lee Algorithm that reduces execution time during the expansion phase by biasing the search in the direction of the target. Unlike the Lee Algorithm, which uses the distance from the source as its cost function, Hadlock's algorithm uses a value known as the detour number. The detour number D(P) of a path P from the source to a gridpoint reflects the number of grids that this path has "detoured" away from the target. Since the expansion algorithm selects nodes with the lowest cost for expansion, this biases the search in the direction of the target. When an obstacle is reached, a detour is necessary and nodes labeled with higher values are expanded. The backtrace phase operates identically to the Lee Algorithm. Because it still does exhaustive search as a fallback, Hadlock's algorithm still guarantees that a minimum-cost connection will be found if it exists. References F. O. Hadlock, "A shortes path algorithm for grid graphs", Networks, Vol. 7, No. 4, Winter 1977, pp. 323-334. N. Sherwani, Algorithms for VLSI Design Automation, 3rd. edition, Springer, 2005. |

| CadApplets Home | Channel Router Applet | Maze Router Applet | Multilayer Maze Routing | Placement | Iterative Imp. | Annealing |

Last updated on February 23, 2007 by John A. Nestor