Re: [CAD_CAM_EDM_DRO] Re: Traveling Salesman algorithm ?

rab@... wrote:

> Don't suppose anyone can recommend a good algorithm for solving the
> Traveling Salesman problem ?

There may not be any. Now, for machining, things are different, because
any cutting motion is good. What you try to minimize is the non-cutting
movements. This makes the problem much easier. Also, the case where
there are hundreds or thousands of cutting movements, usually with exactly
one non-cutting movement between them, is a lot simpler problem.
You throw away all non-cutting movements, just keeping the cutting
movement strings as they were. Now, you pick one at random, do it,
mark it done and then search the endpoints of all other strings to see
which one is closest. When there are no more uncompleted movements
left, you're done. this is a very simple scheme, but it usually reduces
badly
planned toolpaths by up to 90% (Those would have to be REALLY bad,
but I've seen them.) Depending on how the toolpath is written, detecting
cutting from non-cutting movements may or may not be easy.

Jon