Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!cs.utexas.edu!uunet!ncrlnk!ncr-sd!hp-sdd!hplabs!hpda!motcsd!xdos!doug
From: doug@xdos.UUCP (Doug Merritt)
Newsgroups: comp.sys.amiga.tech
Subject: Re: plotter optimizing algorithm
Summary: NP complete
Message-ID: <249@xdos.UUCP>
Date: 25 Apr 89 18:24:29 GMT
References: <8904242129.AA25480@postgres.Berkeley.EDU>
Reply-To: doug@xdos.UUCP (Doug Merritt)
Organization: Hunter Systems, Mountain View CA (Silicon Valley)
Lines: 27

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