Show HN: Interactive visual solver for the traveling salesman problem | Hacker News Reader

Show HN: Interactive visual solver for the traveling salesman problem

tspvis.com

113 pointsintrepidev10 comments

Really cool visualisation, thanks for sharing.

Mentally I tend to further categorise heuristics into "construction" and "improvement" heuristics. Your "shortest path" is a construction heuristic that I normally call "nearest neighbour". Other common heuristics are "greedy" (iteratively add the shortest feasible edge) and "farthest insertion" (iteratively add the farthest point from the subtour to the best position). There's an interesting synergy between construction and improvement strategies, e.g. 2-opt might be more worthwhile after nearest neighbour than greedy. It would be extra awesome to be able to choose both construction as well as improvement and see how it pans out.

Thanks so much! I haven't formally studied these so the terminology still gets me sometimes.

When you say "choose construction as well as improvement", I'm curious what you mean. It may not be clear, but if you run shortest path, the resulting best path is fed into whatever algorithm you run next. Is that what you mean?

Ah I see, I didn't realise you could combine heuristics. I still think it would be cool if you could pick from multiple construction heuristics (shortest path, farthest insertion...), followed by which improvement heuristic/s you want to use (2-opt, 3-opt...).

The choice of which heuristics you use and what order you do them in is sometimes called your meta heuristic strategy.

Really nice!

If the optimal result is known maybe you could present that somehow? To see how good/bad the current solution is.

Very cool! FYI, double clicking the map is throwing an error for me and crashes the app to a white screen.

thanks for the heads up! should be fixed

I've been thinking about this problem for a while with a little twist. What if you wanted to run/walk all the streets in your city? What is the shortest path to do it? How do you calculate the number of kilometers of streets in a city?

This problem is called Chinese Postman Problem and can be solved in polynomial time using matching algorithms:

https://en.m.wikipedia.org/wiki/Route_inspection_problem

Nice. If I can suggest a cosmetic improvement, you list number of possible paths, it would be cool to see how many paths algorithm tried so far until it finishes (and how many paths it tried in total).

really like this idea - I'll look into it, maybe with a progress bar or something

Reply on news.ycombinator.com