Path: utzoo!attcan!uunet!husc6!ogccse!blake!uw-beaver!cornell!mailrus!ames!ig!bionet!agate!eris.berkeley.edu!mwm
From: mwm@eris.berkeley.edu (Mike (I'll think of something yet) Meyer)
Newsgroups: comp.sys.amiga.tech
Subject: NP complete pedantry (was: plotter optimizing algorithm)
Message-ID: <23711@agate.BERKELEY.EDU>
Date: 28 Apr 89 00:12:13 GMT
References: <8904242129.AA25480@postgres.Berkeley.EDU> <249@xdos.UUCP>
Sender: usenet@agate.BERKELEY.EDU
Reply-To: mwm@eris.berkeley.edu (Mike (I'll think of something yet) Meyer)
Organization: Missionaria Phonibalonica
Lines: 33

In article <249@xdos.UUCP> doug@xdos.UUCP (Doug Merritt) writes:
<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! 
<
<[The problem is the traveling salesman problem, which means it's NP-complete.]
<
<(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.)

Excuse me while I get pedantic. "unreasonably slow" should actually be
"unreasonably slow for large problems." It's possible to find an
optimal, general solution to NP complete problems that are
sufficiently fast for the problem sizes at hand, but won't be for
anything much larger.  For example, I've coded scheduling algorithms
(and yes, the result was an NP-time program) that was acceptable for
interactrive use with 10 people (we had 7), for batch with up to 15,
but forget anything beyond that.

The plotter problem mentioned here will almost certainly be
"unreasonably slow" for any interesting number of points to be
plotted.

	<mike
--
ICUROK2C, ICUROK2.				Mike Meyer
ICUROK2C, ICWR2.				mwm@berkeley.edu
URAQT, I WANT U2.				ucbvax!mwm
OO2EZ, I WANT U2.				mwm@ucbjade.BITNET