An Algorithm for Minimizing Backboard Wiring Functions

A partially exhaustive algorithm is presented
for solving the following problem arising from 
automatic layout of a computer.  Given an ordered set
E1, E2,..., EN of N computer components, for each 
permutation of the elements E1, E2.., EN, there is attached
a value of an integer function F.  The algorithm 
finds a local minimum of F by evaluating the set {Delta
F} of the increments corresponding to a certain 
set of exchanges of two elementshen the exchange
corresponding to the least negative increment of 
{Delta F} is performed.  The process is iterated and stopped
when the set of the increments is a positive 
or empty set, which, it is proved, corresponds to a
minimum.  The procedure is similar to the Downhill 
Method for finding the minimum of a real function F(P),
and can be applied to other placement problems. 
 Experimental results are presented with backboards formed
by many elements and different initial placements.

CACM November, 1965

Pomentale, T.

CA651112 JB March 6, 1978  4:35 PM

1169	5	1169
1169	5	1169
1169	5	1169