An algorithm for minimizing backboard wiring functions

A partially exhaustive algorithm is presented for solving 1the following problem arising from automatic layout of a computer. Given an ordered set E~, E~, , E.v of N computer components, for each permutation of the elements El, E~, "" , E v, there is attached a value of an integer function F. The algorithm finds a local minimum of F by evaluating the set ~F} of the increments corresponding to o certain set of exchanges of two elements. Then the exchange corresponding 'to the least negative increment of IAF} 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.