Re: Travelling salesman problem in C

<whitehatmiracle@xxxxxxxxx> wrote in message
news:1157971776.384042.25440@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
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.

Then there are three solutions. Returning one of them may be enough,
but in many cases you'll be expected to return all of the optimal (or
even near-optimal) solutions.

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?

There is no guarantee that if ACB > ABC then ACBxx > ABCxx.

The traveling salesman problem is NP-complete. There is no known
shortcut, period. The only known way to solve NPC problems is brute
force testing of every possibility.

This is probably why your instructor has assigned you this problem -- to
show you that some problems simply aren't solvable (for a large enough
N) and you can't rely on clever tricks or compiler optimizations to save
you if you pick the wrong algorithm.

S

--
Stephen Sprunk "God does not play dice." --Albert Einstein
CCIE #3723 "God is an inveterate gambler, and He throws the
K5SSS dice at every possible opportunity." --Stephen Hawking



--
Posted via a free Usenet account from http://www.teranews.com
Warning: Do not use Ultimate-Anonymity
They are worthless spammers that are running a scam.

.

Relevant Pages

  • 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: 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: 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)