Help for The Travelling Salesman Problem puzzle

Puzzles
#1

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

#2

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

1 Like
#3

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

#4

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.

#5

“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.

#6

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