Behold! The winning path through all 339 cities(as drawn up by Cheng Sun). For a description of the competition, see here.

**Sreenath Are **(17 — U.S.A.)

**Route Distance:** 217130 km
**Submission Time:** 26 Jan 2014 17:36 GMT
**Programming Language:** C++

Sreenath’s program is available here

He will receive a brand new Android tablet, a winner’s certificate, a Brilliant.org t-shirt, and some secret awesome prizes.

**Cheng Sun** (17 — U.K.)

**Route Distance:** 217130 km (same route as winner)
**Submission Time:** 26 Jan 2014 22:40 GMT
**Programming Language:** Python

Cheng’s program is available here

He will receive a certificate and a Brilliant.org t-shirt.

From opposite sides of the Atlantic, Sreenath and Cheng found the same route through different programming languages. Sreenath edged out a victory by submitting 5 hours ahead of Cheng. We think their routes are pretty impressive given the surprise nature of the competition, and the short time frame to submit a program.

Below are some summary statistics to give you sense of the overall shape of the competition.

**Total Number of Valid Entries:** 45

**Mean Route Distance:** 299 696 km

**First Quartile:** 236 642 km

**Median:** 258 891 km

**Third Quartile:** 279 591 km

**Distribution of route lengths (log scaled):**

**Graph of individual entry lengths:**

We hope you enjoyed exploring a well known problem and claiming some sense of ownership of it for yourself. We sincerely wish that we could have awarded all participants free air travel along the winning route to all 339 cities. Alas, the brilliant.org private jet hasn't been built yet...

So we have to settle for giving out material things to a winner and a runner up.

A good conversation already began in the other thread, but feel free to trade notes and discuss your programs in this thread or in other Notes.

Thanks to everyone for participating!

No vote yet

1 vote

×

Problem Loading...

Note Loading...

Set Loading...

Easy Math Editor

`*italics*`

or`_italics_`

italics`**bold**`

or`__bold__`

boldNote: you must add a full line of space before and after lists for them to show up correctlyparagraph 1

paragraph 2

`[example link](https://brilliant.org)`

`> This is a quote`

Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.`2 \times 3`

`2^{34}`

`a_{i-1}`

`\frac{2}{3}`

`\sqrt{2}`

`\sum_{i=1}^3`

`\sin \theta`

`\boxed{123}`

## Comments

Sort by:

TopNewestMany congratulations to Sreenath! Funny that we independently found exactly the same tour. Maybe we'll meet along the tour in the future :)

A few notes on my approach: I tried several approaches, though ironically it was my first approach that worked the best.

At first, I generated a greedy path as a starting point (see the function

`greedy`

). I sorted every single edge of the graph by length and kept taking the shortest edge that was valid to take.The first, and (disappointingly) the winning strategy, was to simply use 2-opt search with random perturbations. I kept applying 2-opt moves until a starting graph was 2-optimal (see

`do2opt`

), meaning that no more 2-opt moves can be made to improve the tour. Then, I randomly swap the order that two cities were visited in, and 2-optimise it again. This is done from the current best tour until I get a further improved tour. (see`random2`

)I then tried to implement 3-opt search, with little success. I think I got the loop a bit wrong, but it gave inferior results to 2-opt(which should be impossible, as all 3-optimal tours are also 2-optimal). This was on top of it being horrifically slow. I tried using candidate lists, which sped things up, but that didn't make the actual 3-opt search correct!

Because 2-opt is a local search technique, it can get trapped in local minima. I implemented simulated annealing to try to overcome this, where sometimes (depending on the "temperature") I would accept an inferior tour just to try to jump out of a local minimum. Unfortunately there was a tradeoff between the quality of the tour and how slowly I cooled the system, and running it for half an hour did not net any better results than the winning tour that I had previously achieved.

I then looked around and just for fun decided to implement Ant Colony optimisation, where I simulated a bunch of ants wandering around the world and spreading pheromones along the best tours. This ended up being a fickle mess, because there were lots of tweakable parameters in the ant behaviour, and I didn't have the time to tune the system to give me ultimate ant world domination :( It was fun to code, though.

Throughout all my experimentation my code always saved the best tour to disk on termination, so that I could kill the program half-way through, twiddle the code a bit, and resume the search later on. It also meant I could back up the best paths I had found. It meant I was never afraid to try something new, and lose the tours I had before.

In future I might investigate going directly for the optimal solution, by using branch-and-bound or some variant of that. I wasn't confident that I would get that working (fast enough) for this competition though.

(Apologies for the messy coding, if you're reading along. Also, in both of our codes, the double quotes seem to have been mangled: each

`"`

is transformed into two`""`

.)Anyway, I enjoyed this a lot, hope to see more competitions like it on Brilliant!

Log in to reply

I've fixed the wrong quote marks in both source code files. Thanks!

Log in to reply

Oh, wow, my solution is exactly on median, lol.

Congrats to the winners! Congrats also to all of the participants to get their best! :D

Thanks for Brilliant to make this competition, and we are looking forward to your next challenges! ;)

Log in to reply

Can you organize more competitions like this?

Log in to reply

I'm a bit disappointed that there are no honorable mentions. Also, in my opinion, Cheng's code is much more elaborate and interesting.

Log in to reply

Hm, yeah, that's pretty disappointing. I'd be interested to see your code, and what your approach was though.

Log in to reply

Thanks to both of you for participating. As one of the staff who looked through the results, I can say that we felt it was appropriate to give honorable mention to Cheng, not only because his result was tied for first but also because his code showed several nice approaches to the problem.

While several other participants had good code and similar results, we didn't see anything that really struck us as contributing more to the community than posting the two winners listed here. Interestingly, several of the top results used professional software to solve the problem (Concorde TSP solver, Mathematica) but still didn't get better results than our two winners!

Log in to reply

Log in to reply

Congrats to both Shreenath & Chen

Log in to reply

congrats to both the winner and runner up.Could anyone post here the code in c as i don't know any other language?If anyone has solved this problem in C then please post it...Thanks,in advance.

Log in to reply

hey can you tell me which c++ compiler did you used..

Log in to reply