[Community Puzzle] The Travelling Salesman Problem

Puzzles
#1

Coding Games and Programming Challenges to Code Better

Send your feedback or ask for help here!

#2

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?

#3

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.

#4

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.

1 Like
#5

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.

#6

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?

#7

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.
1 Like
#8

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

Edit: Code removed

#9

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.

#10

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.
#11

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.

1 Like
#12

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.

#13

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.

#14

Thank you a lot, you saved me at least 30 minuts of debugging.
For those who are very near to solution, choose to never round result (use double during all the “computing”).
Use Math.round only at the end (in the sys out).

#15

Bonjour Ă  tous,

J’ai essayé de résoudre ce problème The Travelling Salesman Problem , mais mes solutions sont inférieur à celles attendues. Pourtant quand je debug mes résultats je suis bien passé dans toutes les villes. Le premier test passe correctement mais les autres pour 10, 12, 14 villes sont donc faux.
Je me demande si le problème peux venir du calcul des distances euclidiennes, mais le fait que le premier test soit correct me dit que non.

Voila voila, si quelqu’un a une idée à me proposer, ça m’intéresse.

Merci :slight_smile:

Hi everyone,
i have tried to resolve the puzzle The Travelling Salesman Problem, but all my solutions are inferior than expected. However when i debug my results i went well in all cities.
The first test is ok, but the others for 10, 12, 14 cities are wrong.
I ask me if the problem can comes form the calculation of Euclidean distances, but the fact of the first test is ok say me to not.

So, if anyone have an idea to propose me, i’m interested.

Thanks

#16

Maybe you have a rounding problem? Maybe you are rounding the result after each step, instead of rounding the final result?

1 Like
#17

Maybe you have a rounding problem? Maybe you are rounding the result after each step, instead of rounding the final result?

But this is un-clear in the problem description

#18

I don’t know any situation where you must compute a sum step by step and it would be a good idea to round it at each step.

I’ve witnessed people working in non scientific fields (cough history teachers cough) trying to compute cumulative frequencies like this, ending up with 98% at the end of their last column, and having absolutely no clue of why they wouldn’t get 100% as expected.

But if you’re in the CS field, come on, it shouldn’t even cross your mind to do it that way.

#19

“Computer science” doesn’t necessarily mean “science”.
Furthermore, being registered on CodinGame doesn’t mean that you are in the computer science field.
And being in the computer science field doesn’t mean that you have any mathematic background.
There’s students (even from secondary), hobbyists…
So don’t be so patronizing please.

#20

Yeah sorry I didn’t mean to make anyone feel dumb, we’re all here to learn, I just wanted to point out how a bad idea rounding at each step is in general.
But I got a bit carried away ^^

2 Likes