The Algorithm Design Manual Second Edition

− or y-coordinate. This is something we call the L

∞

metric, but we can

capture it by changing the edge weights in the graph. Anything else funny about

your robots?” I asked.

“Well, it takes some time for the robot to come up to speed. We should probably

also factor in acceleration and deceleration of the arms.”

“Darn right. The more accurately you can model the time your arm takes to

move between two points, the better our solution will be. But now we have a very

clean formulation. Let’s code it up and let’s see how well it works!”

They were somewhat skeptical whether this approach would do any good, but

agreed to think about it. A few weeks later they called me back and reported

that the new algorithm reduced the distance traveled by about 30% over their

previous approach, at a cost of a little more computational preprocessing. However,

since their testing machine cost $200,000 a pop and a PC cost $2,000, this was an

excellent tradeoff. It is particularly advantageous since the preprocessing need only

be done once when testing multiple instances of a particular board design.

The key idea leading to the successful solution was modeling the job in terms

of classical algorithmic graph problems. I smelled TSP the instant they started

talking about minimizing robot motion. Once I realized that they were implicitly

forming a star-shaped spanning tree to ensure connectivity, it was natural to ask

whether the minimum spanning tree would perform any better. This idea led to

clustering, and thus partitioning each net into smaller nets. Finally, by carefully

designing our distance metric to accurately model the costs of the robot itself, we

could incorporate such complicated properties (as acceleration) without changing

our fundamental graph model or algorithm design.

Take-Home Lesson: Most applications of graphs can be reduced to standard

graph properties where well-known algorithms can be used. These include min-

imum spanning trees, shortest paths, and other problems presented in the

catalog.