Wire Routing Subject to Constraints
Original Publication Date: 1984-Jul-01
Included in the Prior Art Database: 2005-Feb-04
A conventional maze router for wire placement in an array finds the path of lowest cost between two points or regions. If one is required to find a path of minimum cost C subject to the constraint that some other nonnegative function g (whose value depends on the path) not exceed the value g0, the conventional methods do not suffice. This is because one does not know, at an intermediate stage of the maze run, whether one needs to make the 'sacrifice' of accepting a higher-cost route to a given intermediate state, in order to insure reaching the target with an allowed g value. An improvement is provided by a modification of the usual mazerunner algorithm that optimizes a general cost function subject to one or more constraints of this type. Strategies for reducing run time and storage requirements are also provided.