Re: Solution for the Traveling Salesman Problem

On 30 nov, 18:52, Chip Eastham <hardmath@xxxxxxxxx> wrote:
On Nov 30, 10:54 am, H <h_boutam...@xxxxxxxxxxx> wrote:





On Nov 30, 4:40 pm, Chip Eastham <hardm...@xxxxxxxxx> wrote:

On Nov 30, 10:22 am, shrungr...@xxxxxxxxx wrote:

I don't understand what you mean by "greedy".

What I think I found is the shortest way possible, and that is the
wanted answer.

Your web page describes selecting edges (segments)
remaining that are shortest, with the constraint that
a node (city) cannot be on more than two edges. It
makes no provision for cases of ties between lengths
of segments, but the algorithm is flawed even if we
stipulate that all lengths are different.

Your procedure need not produce a tour (a closed
path visiting each node once). Consider for example

AB: 1
BC: 2
AC: 3
AD: 4
BD: 5
CD: 6

What happens when we apply your algorithm to these
data is that we form a closed loop ABC. Then it is
impossible to add any edge connecting node D since
the other nodes already have two edges apiece.

However if your approach does happen to produce a
tour, then that is the shortest tour. It simply
doesn't work in every case.

Note that you don't offer any proof of a claim
that the algorithm works. A little effort at
trying to construct such a proof might give you
a better appreciation for the difficulty of the
travelling salesman problem.

regards, chip

My approach produces a tour which I think is the shortest, please get
a "real" contrary example. Because the one you just posted can't even
be drawed on any paper.

I think it will be better to draw some points on a paper and then
measure the distance between every two points.

Thanx for trying at least.
Regards
H

If you wish to restrict attention to planar graphs using
the Euclidean distance between points to obtain edge
lengths, as other authors have done, it is fine so long
as you are careful to state such restrictions.

Even so it is easy to modify my counterexample to meet
these restrictions. Consider the points:

A = (3,0)
B = (0,0)
C = (0,4)
D = (7,7)

Since A,B,C are all closer to each other than to D, the
algorithm you outlined would connect a triangular loop
around ABC before considering any edge involving D. As
a result D cannot be added (because there will already
be two edges on each other vertex).

regards, chip- Masquer le texte des messages précédents -

- Afficher le texte des messages précédents -

Mr Chip,

Using the points you provided the distances will be like fellowing :

AB : 3
AC : 5
AD : 8.06
BC : 4
BD : 9.89
DC : 7.61

_____
Next step : ordering
BD : 9.89
AD : 8.06
DC : 7.61
AC : 5
BC : 4
AB : 3
____________
We take :
BD
AD
AC
BC

AND THAT IS YOUR ROAD !
and here we go the lines are AD, DC, AC, AB
.

Relevant Pages

  • Re: Solution for the Traveling Salesman Problem
    ... remaining that are shortest, with the constraint that ... but the algorithm is flawed even if we ... stipulate that all lengths are different. ... then that is the shortest tour. ...
    (sci.math)
  • Re: Solution for the Traveling Salesman Problem
    ... remaining that are shortest, with the constraint that ... but the algorithm is flawed even if we ... then that is the shortest tour. ... measure the distance between every two points. ...
    (sci.math)
  • Re: Dijkstras algorithm for shortest paths
    ... {Dijkstra computes the cost of the shortest paths ... for each vertex v in V-S do ... Before I did anything I'd try to make sure I understood the algorithm. ... I presume 'C' is a two-dimensional array that holds the distance between any ...
    (comp.programming)
  • Re: Dijkstras algorithm for shortest paths
    ... which is the implementation of Dijkstra's algorithm for finding ... {Dijkstra computes the cost of the shortest paths ... imagine any way to find a shorter distance after this. ...
    (comp.programming)
  • Re: Solution for the Traveling Salesman Problem
    ... remaining that are shortest, with the constraint that ... but the algorithm is flawed even if we ... tour, then that is the shortest tour. ...
    (sci.math)