🚀 go-pugleaf

In article <8904242129.AA25480@postgres.Berkeley.EDU> dillon@POSTGRES.BERKELEY.EDU (Matt Dillon) writes:
>
>	Determining the most optimal plotter drawing sequence is almost the
>traveling salesman problem! 

Yes. In fact, "almost" understates it. As Bill Joy pointed out to me
in '77 (in connection with optimal sequencing of intelligent terminal
ops to redraw a screen [for the first version of vi], which maps one-to-one
with this problem), the optimal method is NP-complete, just the same as the
T.S. problem.

(In case anyone is wondering, that means there [almost certainly] aren't
any polynomial-time solutions, which means essentially that there is no
way to fully optimally solve the general case in a reasonable amount of
time...  you have to settle for heuristic and sub-optimal and/or
unreasonably slow solutions.)

Actually Bill fed the problem to me and let me stew on it for a few
days, and *then* explained NP-completeness to me when I'd discovered
it was a much harder problem than it at first sounded. Made for a
very intuitive introduction to the subject.
	Doug
-- 
Doug Merritt				Member, Crusaders for a Better Tomorrow
{sun!pyramid,apple}!xdos!doug		Professional Wildeyed Visionary

"Of course, I'm no rocket scientist" -- Randell Jesup, Capt. Boinger Corps