mwm@eris.berkeley.edu (Mike (I'll think of something yet) Meyer) (04/28/89)
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