The two optimizations are aimed at providing fast solutions that fit
easily in memory.
- Small Memory Footprint - Small grid size: The data
structures used to represent the grid limit each grid to essentially
8-bit during wavefront expansion. Grid cells should be as small as
possible while still storing all necessary information for
mazerouting.
- Quick Solutions - Small wave front expansion: A majority of
the HORE running time is spent in wavefront expansion. Thus, the
speed with which HORE generates solutions is very sensitive to the
number of grids cells expanded during mazeroute. Several techniques
were used to minimize wavefront expansion: minimum spanning tree-esque multipoint
nets and depth first prediction.
|