Re: [CAD_CAM_EDM_DRO] Re: Traveling Salesman algorithm ?

frenner@... wrote:

> --- In CAD_CAM_EDM_DRO@y..., rab@r... wrote:
> > Don't suppose anyone can recommend a good algorithm for solving the
> > Traveling Salesman problem ?
> >
> > Rab
> >
> > Rainnea Graphics
>
> Rab,
> The Traveling Salesman problem is famously non-polynomial complete,
> meaning that it provably can not be solved (best answer) by a formal
> algorithm. To find a "good enough" approximate answer you can use a
> search method such as branch-and-bound and stop looking when the pain
> level of the seach exceeds the pain of the best answer found so far.

Actually, it CAN be solved, by exhaustive search, only for a very small
number
of nodes (think cities for the salesman to visit). The number of possible
results rises as the factorial of the number of nodes. It gets intractable
at about 9 nodes, and even a hot Pentium will grind for hours to solve
the problem when there are, maybe, 12 nodes.

I wrote a wire-wrap program that took a netlist and generated a nice
list for manual wire wrapping in an organized manner. (It had you do
all level-1 wraps first, then you put on the 2nd level.) It attempted to
optimize the net 'tree' to use a minimum length of wire, and then told
you what length of wire to use between each pair of nodes.

I used a brute force algorithm up to 6 nodes, then switched on a
genetic algorithm that fiddled around for a while, took the best result
and then fiddled with that one for a while, etc. The idea was to avoid
getting stuck in a false minimum while making small changes and miss
a major improvement by stringing the wire a different way. this wasn't
perfect, but it was mostly usable.

I wanted to add some rule-based methods to quickly recognize organized
patterns and use zig-zag or some row and column schemes, but I haven't
had need for massive wire wrapping jobs lately. (I was building a 32-bit
bit slice computer in the early 80's, it probably has 5000 wire wrap wires
on each board!)

Jon