Re: Solution for the Traveling Salesman Problem

"H" <h_boutamani@xxxxxxxxxxx> wrote in message
news:edfb6c31-09f6-470c-8969-b0640025fc88@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
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.

Hello Haroun,

Here is the second line of your web page:

| "Given a number of cities and the costs of traveling from any
| city to any other city, what is the least-cost round-trip route
| that visits each city exactly once and then returns to the
| starting city?".

So by your own words, you are considering COSTS, not physical distances. So
there is nothing wrong with Chips example - stop grumbling and just admit
you got it wrong! :-)

Also, I don't see any proof on your web page that your algorithm selects the
shortest path. (This is not surprising, as the algorithm clearly doesn't
work, as pointed out by other posters!) Before anyone takes you seriously,
they would expect to see the workings of a proof, or at least some evidence
that your algorithm performs better than existing algorithms...

Regards,
Mike.



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


.

Relevant Pages

  • Re: Solution for the Traveling Salesman Problem
    ... >> What I think I found is the shortest way possible, ... > a node (city) cannot be on more than two edges. ... but the algorithm is flawed even if we ... > tour, then that is the shortest tour. ...
    (sci.math)
  • Re: Solution for the Traveling Salesman Problem
    ... remaining that are shortest, with the constraint that ... a node (city) cannot be on more than two edges. ... but the algorithm is flawed even if we ... then that is the shortest tour. ...
    (sci.math)
  • > I hereby challenge "Mensanator" to tell me why the below text is insuffic
    ... There exists a starting city and an ending ... Algorithm when Quick Sortis employed instead of BS turns out to ... They produce the same minimal cost, ... Sort it in the Ascending order.2. ...
    (sci.math)
  • Re: P=NP Proof Published at CERN
    ... Non Computational time Algorithm ... There exists a starting city and an ending ... They produce the same minimal cost, ... Sort it in the Ascending order.2. ...
    (sci.math)
  • Re: P=NP Proof Published at CERN
    ... JSH first attempted it by finding a polynomial algorithm to the ... There exists a starting city and an ending ... They produce the sameminimal cost, ... 3Bubble SortIn the example traverse of six-city TSP algorithm use Bubble Sort ...
    (sci.math)