alt Hacker NewsShortest-possible walking tour to 81,998 bars in South Korea
Comments
If you just use the simple-minded Bell Labs probabilistic algorithm, how much worse is that result?
The classic TSP approach is:
1. Hook up all the nodes in some arbitrary path.
2. Cut the path in two places to create three pieces.
3. Rearrange those three pieces in the six possible ways and keep the shortest.
4. Iterate steps 2-3 until no improvement has been observed for a while.
This is not guaranteed to be optimal, but for most real-world problems either finds the optimal result or is very close.
It's strange that they don't mention the total distance. I understand that the point-to-point travel time is what they're solving for, but it would be interesting to know what the actual distance of travel was, if for no other reason than calculating caloric burn. But then you could also see how much it deviated from the shortest-distance path.
I am overwhelmed with the thought of nearly 82 thousand bars within a country roughly the size of Ohio.
I'm impressed they found a dataset this hard, but not much harder. It's a delicate balance between beating the last Traveling Salesman hiscore (Netherlands), and never finishing your compute
reminds me of a question they used to ask in the Irish army back in the 60s. My Dad told me this. "How do you get from Bachelor's Walk to Collins Barracks without passing a bar?". People would spend hours and days working on the answer. In the end, the answer was "Go in to every one".
So NP is like P again. I learned in school 13 is the max and one of my algebra professors advanced it to 15 (in the 80ies). Then came 20, then came 20.000, this is 80k with proof, and at the World TSP page we see the record was 1m.
http://webhotel4.ruc.dk/~keld/research/LKH/
The biggest proven optimum is for 3178031 right now.
This should be really done with CUDA, not plain C, btw.
During COVID I made it a goal to walk every street in my town using the web-based CityStrides (https://citystrides.com/) tracker. It keeps tracks of streets you have walked and lets you know what percentage of a town you have walked. It didn't optimize my routes for coverage, but it was a fun mental puzzle to plan out my walks to hit as many streets as possible without duplication. An automated tool might be fun, but doing it by hand was part of the journey as it were.
As you browse the CityStrides site you can find people's LifeMaps which show all their walking. Some people have done amazing amounts of walking. See this user for example and their coverage of Paris, France...
https://citystrides.com/users/15259/map#48.85741101618777,2....
Oh no, looks like a few new bars opened up, and a few others closed. Time to recalculate.
Branch-and-bound is an algorithm "from the book" to me. Fundamentally very simple, provided you view the LP solver as a black box, but incredibly useful.
OSRM lead dev here. Love to see this large of an instance being solved.
If you spent 40 years of your life on this path, you would still be visiting 5.616 bars per day. Nuts.
They call it the Traveling Salesman Problem, but it sounds more like the Drunkard’s Walk to me.
I looked at near my home, they missed a few. A issue is that in Korea a lot of the local spots are not on any public maps.
Has anyone done the opposite of this, finding the longest possible route?
This is both hilarious and genuinely impressive. A TSP solution involving nearly 82 000 bars? That's a level of dedication to both math and beer I didn't know I needed in my life
Would be nice if they could briefly describe the algorithm. Sounds like they’ve turned the TSP into an integer linear program that they can do branch and bound on, but I’m not sure.
I zoomed in on the map and discovered at least one shortcut where one could have saved a few seconds, now is that proof enough that the solution is not optimal? :P
Is that one of the problem quantum computers would resolve instantly if it is actually possible to scale them up?
Very interesting..
Is anything supposed to happen if you click on those red circles? I was hoping it will show name or other info!
It would suck to get to bar 51,248 only to find out it's now permanently closed
Seem i do need a pair of dry socks for part of the walk.
Does it account for "pit stops"
Kids, we're going on a road trip!
Sadly I'm not a Soju fan
impresive, I have forgot TSP after graduated.
“The locations were downloaded from a database maintained by the Korean National Police Agency.”
Title is incorrect. 178 days is the walking time of the optimal tour, not how long it took to solve for the best route
[dead]
If you find this impressive, take a look at the 1.33 billion stars TSP solution provided by the same authors.
- Gaia DR2 (1,331,906,450 Stars): https://www.math.uwaterloo.ca/tsp/star/gaia2.html
> "The tour is at most 1.0038 times the length of a shortest-possible route."