Browse Prior Art Database

Depth First Predictor Search

IP.com Disclosure Number: IPCOM000077162D
Original Publication Date: 1972-Jun-01
Included in the Prior Art Database: 2005-Feb-24
Document File: 2 page(s) / 48K

Publishing Venue

IBM

Related People

Rubin, F: AUTHOR

Abstract

The Lee algorithm is a well-known algorithm for finding a least-cost path through a grid, and hence for finding wire paths on circuit boards. Essentially the technique consists of examining the neighbors of the origin or start cell, then examining their neighbors, and so forth, expanding in waves until the goal cell is reached. Thus expansion proceeds in all directions at once, both towards and away from the goal.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 55% of the total text.

Page 1 of 2

Depth First Predictor Search

The Lee algorithm is a well-known algorithm for finding a least-cost path through a grid, and hence for finding wire paths on circuit boards. Essentially the technique consists of examining the neighbors of the origin or start cell, then examining their neighbors, and so forth, expanding in waves until the goal cell is reached. Thus expansion proceeds in all directions at once, both towards and away from the goal.

Two methods have been found which will reduce the size of the search and hence its cost in terms of computer time. These methods are called predictor search and depth-first search, and when used together are found to reduce the cost of searching by 75% on the test boards tried.

Predictor search consists of adding a predictor term to the path cost function which is being minimized. Let the path cost function have the following form: f(i) = g(i) + a c(oi) and make the following definitions: 0 is the origin of the path. x is the goal of the path. f is the path cost function. g is a monotone path function. That is, g increases with path length. c is the distance function along a path. d is Manhattan distance. a is a positive constant. Then adding the predictor term a- d(ix) to the path cost function leaves it as a monotone path function. h(i) = f(i) + a-d(ix) = g(i) + a(c(oi)+d(ix)) The new path cost function may be minimized by applying the Lee algorithm, producing a path for which h(x) = f(x) + a-d(xx) = f(x) is minimum.

To se...