Traveling sales man problem


#1

I started the traveling sales man problem.
Here is my solution so far which unfortunately doesn’t work.
What I do : look for closest point to current point , once identified look for the closest point to the last visited city.
I don’t think that this is the way I am supposed to deal with the problem since I don’t pass any of the tests.
Hints?


#2

The puzzle describes precisely what algorithm should be used. If you introduce any variation, your result will most likely differ from what is expected.
The aim is not to find the best solution to the travelling salesman problem, just to follow the algorithm to the letter.


#3

The greedy algorithm starts at the first input given and always chooses the nearest point next to it. This continues until no points are left and the last point is connected to the first point.

Well, this is my interpretation of the description. What I think I misunderstood is the second sentence:

This continues until no points are left and the last point is connected to the first point.


#4

it just means you should process all the points.
At each step you eliminate one more point from the list by connecting it to the previous one.
The last point being connected to the first is just a logical consequence of that (and the whole point of the TSP :slight_smile: )
You might want to lookup the travelling salesman problem on wiki, it’s a classic and it is well documented. That might help you grasp the general idea.


#5

So basically, what it is required is for the actual i’th point, identify the i+1 point’s coordinates , compute the distance and add the result to the sum of the distances?


#6

Basically yes. Thus being said, I find the problem definition pretty vague. I’d add the following precisions so that people don’t waste time on insignificant details:

  • the expected distance includes the return leg (the segment from the last point to the first that closes the path)
  • rounding should occur only at the end, Cumulated distance should be computed as floating point and the final result rounded to the nearest integer.

#7

I tried what was suggest in the poste above. However I wasn’t even close, so I tried this approach:

Edit: Code removed


#8

Well I’m relatively new here, but I think posting your code is not the done thing. The point of these challenges is to learn by confronting problems. I’m all for explaining a problem definition or giving a few hints, but people are supposed to work out the solution by themselves.


#9

This really has me stumped. My code seems to follow the algorithm exactly but gets answers that are very slightly off. For example, on the 5 city test case my calculated distance was off by 2 from the “correct” solution. I did the math out by hand, and this agreed with my solution. Has anyone successfully completed this game?

For reference, here is my process:

  1. Take all the city coordinates in the order they are input.
    2 From the first on the list, find the closest city and calculate the distance.
  2. From the second city, find the next closest city (excluding all previously visited cities), find the distance and add it to the combined distance of previous legs.
  3. Repeat this process until the Nth city, then reconnect to city number 1.

#10

Sounds like maybe you’re rounding the distances at each step. I used the same algorithm but didn’t do any rounding until the very end, and it worked.


#11

Ahh I finally figured it out! I wasn’t rounding at each step, the issue was an indexing error. When connecting back to the first city on the list, my algorithm wasn’t using the proper start point. So instead of connecting city[N] to city[1], it was connecting city [N-1] to city[1] and adding that distance to my total.


#12

I had a mistake in my algorithm as well.

All the information is in the description, I would encourage reading twice.

My mistake, was then when I was compare the next city, I kept comparing distance to the first, not the most recent one that was visited.