- 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."
And as a result it's been broken since May 2022: https://github.com/mrdoob/three.js/releases/tag/r141
I downloaded the HTML file and replaced the link with a versioned one, and the viewer still works just fine.
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.
So, the heuristic solver worked pretty darn well :) Although, I’m not sure how close it would have been the heuristic algorithm you are describing (I suspect that it is considerably more advanced for good reasons, randomly picking will take too long to converge).
[0] https://en.m.wikipedia.org/wiki/2-opt
[1] https://en.m.wikipedia.org/wiki/Lin%E2%80%93Kernighan_heuris...
LKH is a bit different, refers to Lin-Kernighan+Helsgaun -- http://webhotel4.ruc.dk/~keld/research/LKH/
For each iteration:
apply some randomisation
starting at each place
cut the path in 2..n places
reconnect in the most optimal way
if the new tour is the new best, save
reversing subarray from b to d is a 2-opt move.
3-opt (1 particular move):
a b c d e f
a e d c b f -- reversal from b to e
a e d b c f -- reversal from c to b
LK heuristic is a bit more involved, but focuses on continuing to reverse the subarray on the [b, ..., d] segment, with search and backtracking involved. (I think that's refered to as sequential k-opt moves, but I think it's already quite hard to know what exactly LK is, and LKH does much more)
By focusing on the subarray, assuming distance symmetry (length from b to e is same as length from e to b, but there are correct workarounds if this does not hold), you can evaluate the cost of the new route in constant time (but with bigger k there's more moves to evaluate https://oeis.org/A001171)
I checked a few dots near where I live and they're all fried chicken joints. Yeah, we do love chimaek around here. :)
God I miss this place so much <3
[1] https://www.ibisworld.com/us/industry/ohio/bars-nightclubs/1...
0: https://en.wikipedia.org/wiki/List_of_countries_and_dependencies_by_population_density[0]: https://rentechdigital.com/smartscraper/business-report-deta...
They are such an urban phenomenon. A largely empty rural state, with the legacy of prohibition, where you have to drive? That's going to have way fewer drinking locations. A culture of hanging out and drinking requires walkable urbanism. Many of the UK pubs pre-date the invention of the car; "peak pub" appears to have been the late 1800s with over 100,000.
I'm impressed that Korea has more than the UK, but this is definitely going to be a matter of size and the tiny Korean bars.
I don't think that's really true. In the UK, villages had pubs. Gradually some of the villages were joined together into larger cities, and the pubs remained. It wasn't planned as walkable urbanism.
So in Ohio probably everything with class C and D license. How many is not public but probably many times more than 4k.
Many actual street level bona fide bars in Seoul (which has half of all the people of the entire country and the most bars by far) are tiny rooms that fit a few people each. But you always have a "bar street" with 50 of those next to each other.
South Korea apparently ranks #97 on alcohol deaths, so it's apparently not a problematic number of bars, by global standards.
https://codelibrary.amlegal.com/codes/plaincity/latest/plain...
Codes like these are the secret sauce of America's asphalt deserts, in which you'll find - by international standards - comparatively large restaurants and stores. Walkable cities tend to gravitate towards smaller equivalents, and more of them.
Usually parking minimums are WAY too high in required parking spaces to make sense in most cases. Which leads to stuff like a arena having 5x the land area be parking than what is taken up by the arena itself. [1]
0: https://codelibrary.amlegal.com/codes/harrison/latest/harris... (this is for harrison, ohio, just happened to be the first result I found. it's under commercial -> "Tavern, bar, club, lodge, and dance hall.")
How do people do this in practice? Just drink and drive and hope they don't crash / get fined? Or does everybody bring 1 friend who sips colas the whole night?
This, they are making the mistake that all the people on /r/askamerican do over on reddit. Laws like this mostly aren't nationwide or even statewide, they are decided on a very local level.
You can see people taxi/uber into a place if they are definitely planning to get blathered.
That hasn't been my experience. Anytime I've wanted to go somewhere halfway popular the lot is usually full or nearly full. On the flipside, the lots are often empty during times when the business is closed, but reducing the size of the lot would exacerbate the issue of not being able to park nearby when the business is open. You aren't going to stop the US from being car centric, so you either have to dictate that businesses maintain a reasonable amount of parking or you have to have the municipality maintain several large parking structures throughout the city. Most cities would rather have the businesses that need the parking pay for the parking and most people would rather park near the businesses that they frequent.
I think this isn't true. The same way suburbia spread out from cities, I think walkability can spread outwards too in baby steps.
For example, SF is relatively walkable/has public transit. The next step would be slowly removing parking minimums and making the areas surrounding SF more walkable. And then over time as people in those surrounding areas start using their cars less (not getting rid of them but at least trying to do short journeys on foot/bike/transit).
Over time that spreads outwards because half the community served by an area no longer needs a car for their daily travel and the envelope of walkability spreads further.
Plus being able to walk or take a train home makes them far more accessible for people than needing to drive home.
https://www.math.uwaterloo.ca/tsp/korea/data/korea81998.xy.t...
Really puts into perspective a movie like "Train to Busan", which would be like taking a train from Gary to Madison!
How in the hell?
The idea of driving home to the suburbs and locking yourself into your private home is very North American.
I just got back from10 months across Europe. The number of people in public places eating, chatting and just spending time (no simply going somewhere) makes LA or Chicago look like a ghost town.
the UK in totality has 45k pubs, nearly half Seoul's number
this is mostly emblematic of South Korea's major alcoholism problem. way too many bars and too much drinking.
https://www.ibisworld.com/us/industry/ohio/bars-nightclubs/1... (2025) estimates there are about 3,000 "bars and nightclubs" in Ohio.
And https://vinepair.com/articles/map-states-with-most-bars/ (2022) estimates there are 1800 bars in Ohio, apparently placing it in the Top 10 of states with the most bars.
[1] https://www.math.uwaterloo.ca/tsp/korea/computation.html
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.
N=15 was even considered solved in the 60s, and N=20 has never been considered large instances, especially not of Euclidean TSP.
I cannot see how anyone could say 13 is the max: you need 100k memory slots and 1M comparisons. This has been trivial for quite some time.
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....
Is anything supposed to happen if you click on those red circles? I was hoping it will show name or other info!
But I would guess the answer is "no".
If you can prove, as they claim, that you have an algorithm that gives you the optimal solution (aside from the obvious, brute-forced one), you might be one stone throw away to make an argument for some P == NP, that would be HUGE.
But it seems that some people get offended when you tell them their perpetual motion machines are not real.
The solution was found in a few days by the LKH TSP heuristic solver. They spent months (and decades of CPU time) using well-known techniques to bound the specific problem and prove that this was an optimal solution. It’s not something that you can synthesize to a page. They are literally announcing that they verified the heuristic-derived solution.
Consider it like any science, where folks can make shit up. But you can just run the bounding algorithms yourself, or prove they are incorrect.
>These claims are provisional. Until someone produces a better tour or a valid counter-proof, this stands as the best-known solution.
Are we looking at the same website? Because those two are quite different things.