Re: Travelling salesman problem in C

No , this would be a huge waste of memory.
For every permutation you calculate the distance.
If it is smaller than the minimum distance you have
so far then you store the new minimum plus the
permutation which produced it. Continue like this
until you've examined all permutations.

But what if there is more tha one solution. 3 paths having the smae
distance.

I was thinking of storing all the possibilities and traverssing it in
an inteligent way.

Say i have
ABCDE 45
ABCED 72
ABDEC 55
ACBDE 102
ACBDE 135

I see that the combination ACB > ABC therefore i skip the whole ACB
series...
Its like if i have a tree or a graph, the branch that gives the longest
distance can be skiped... am i right?
If so how do i go about it... is it a simple string compare?

Please enlighten me......
Thanx once again

.

Relevant Pages

  • Re: Travelling salesman problem in C
    ... For every permutation you calculate the distance. ... If it is smaller than the minimum distance you have ... I see that the combination ACB> ABC therefore i skip the whole ACB ...
    (comp.lang.c)
  • Re: Info about a particular permutation distance
    ... > permutation distance definitions, and didn't find ... > transposition: in fact, a transposition involves two ... proved that the distance from permutation f to permutation g in S_n is ... W. Edwin Clark, Math Dept, University of South Florida ...
    (sci.math)
  • Re: Challenae question for mathematician
    ... a sequence of number ... is the identity permutation; ... cancellations making the distance from x to z smaller. ... relatively straighforward to find the S-length of any given element, ...
    (sci.math)
  • Re: permutations and inner products
    ... A well-known definition of distance between permutations in permutation ... Given a set X that is at most countably infinite, ... There is a natural analogue of this topological space that does not ...
    (sci.math)
  • Re: Help in Classification with k Nearest Neighbor
    ... >> What formulas do you use for Euclidean and L2? ... This is SQUARED EUCLIDEAN DISTANCE ... I want to take the first K minimum distance ... % find the second norm for each row ...
    (comp.soft-sys.matlab)