[HN Gopher] Shortest-possible walking tour to 81,998 bars in Sou...
___________________________________________________________________
Shortest-possible walking tour to 81,998 bars in South Korea
Author : geeknews
Score : 406 points
Date : 2025-04-24 00:20 UTC (22 hours ago)
(HTM) web link (www.math.uwaterloo.ca)
(TXT) w3m dump (www.math.uwaterloo.ca)
| labster wrote:
| They call it the Traveling Salesman Problem, but it sounds more
| like the Drunkard's Walk to me.
| The28thDuck wrote:
| I'd like to call it a stumble :)
| srcreigh wrote:
| Title is incorrect. 178 days is the walking time of the optimal
| tour, not how long it took to solve for the best route
| modeless wrote:
| 3 months, using 44 CPU-years, is that time.
| dang wrote:
| (Submitted title was "Shortest walking tour to 81,998 bars in
| Korea -- TSP solved in 178 days".)
| OsrsNeedsf2P wrote:
| 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
| bjornsing wrote:
| Do we know they didn't just prune problematic bars from the
| dataset until they found a one with a solution?
| dumbfounder wrote:
| You and I don't know. But this is hacker news so there is
| probably somebody here keeping them honest.
| omoikane wrote:
| In the "computations" page[1], the table lists the Netherlands
| computation as costing 97 CPU years with 6 months of elapsed
| time, while the Korean bars costs 44 years of CPU time and 3
| months of elapsed time. I can't tell if the two problems were
| solved using the same hardware.
|
| [1] https://www.math.uwaterloo.ca/tsp/korea/computation.html
| BrtByte wrote:
| Gotta respect the planning that went into choosing a problem
| that's both absurd and actually solvable
| mofunnyman wrote:
| If you spent 40 years of your life on this path, you would still
| be visiting 5.616 bars per day. Nuts.
| kirubakaran wrote:
| Less than 6 bars a day is pretty doable! :-p
| Smar wrote:
| Isn't comma the decimal separator ;)
| throwaway019254 wrote:
| It depends on which part of the world you live in.
| speedgoose wrote:
| It's not that many bars.
| onion2k wrote:
| It's always worth spending 30s verifying something like
| this by reversing what you're arguing - in this case, 5000
| * 365 * 40 is _obviously_ more than 82,000.
| devonkim wrote:
| That's also not considering whether they're open or existing
| anymore after so much time has passed.
| notesinthefield wrote:
| I am overwhelmed with the thought of nearly 82 thousand bars
| within a country roughly the size of Ohio.
| dyauspitr wrote:
| NYC that is like 20 miles across has 11,000 locations that
| serve alcohol.
| zeckalpha wrote:
| How many bars do you expect are in Ohio?
| fakeBeerDrinker wrote:
| Less than 40,000
| zamadatix wrote:
| One would hope with 5x fewer people!
| fakeBeerDrinker wrote:
| I think it's far fewer, probably under 5,000 if we are
| really talking about "bars" and not any ole liquor
| licensed establishment such as a restaurant...
| jhalstead wrote:
| It seems like you're pretty close with that guess.
|
| 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.
| lifthrasiir wrote:
| That country has a population of 52 million, i.e. about 5 times
| Ohio.
| codemac wrote:
| Sure, but Ohio has ~4200 bars[0]. Which is roughly 1/4 the
| ratio of bars to people.
|
| [0]: https://rentechdigital.com/smartscraper/business-report-
| deta...
| aktuel wrote:
| Ohioans love "big bars".
| xmprt wrote:
| I don't think bars in Korea have parking minimums like they
| do in Ohio.
| skrebbel wrote:
| What's a parking minimum?
| chmod775 wrote:
| The minimum number of parking that needs to be available
| per seat/dining area.
|
| https://codelibrary.amlegal.com/codes/plaincity/latest/pl
| ain...
|
| 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.
| Akronymus wrote:
| A minimum amount of parking spots per patron capacity. So
| a bar with 60 people capacity must have 15 parking
| spaces. [0]
|
| 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.")
|
| 1: https://www.youtube.com/watch?v=OUNXFHpUhu8
| skrebbel wrote:
| The idea of a bar (ie a place people go to get drunk)
| with a dedicated parking lot strikes me as particularly
| bad for road safety. I'm baffled that this is not only
| encouraged, but mandated.
|
| 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?
| vulcan01 wrote:
| We call the latter a designated driver [1] though as you
| can imagine sometimes the designated driver is "only"
| _slightly_ drunk.
|
| [1]: https://en.wikipedia.org/wiki/Designated_driver
| skrebbel wrote:
| Yeah but I mean, if everybody goes to the pub by car,
| does it mean everybody brings a designated driver? Or is
| this one of those things where everybody drives drunk but
| pretends nobody does?
| alexfoo wrote:
| Taxis exist.
| skrebbel wrote:
| The parking minimum is for taxis?
| apocalyptic0n3 wrote:
| It's pretty common for people drive to the bar, get
| drunk, taxi/Uber/Lyft/DD home, and then return the
| following day to get their vehicle. I don't think it
| makes sense personally, but I also don't drink at all so
| I'm not a great judge here.
| robocat wrote:
| Makes perfect sense if people are not planning on having
| a big night and then do.
|
| You can see people taxi/uber into a place if they are
| definitely planning to get blathered.
| zhivota wrote:
| Mostly the latter IMO. The most popular bar where I grew
| up is on a busy highway with no housing within walking
| distance. Parking lot reliably fills up every weekend
| night, mostly with single occupancy vehicles. You can do
| the math.
| nonameiguess wrote:
| Parking lots are not mandated for bars in the US, at
| least not everywhere. I helped my girlfriend's dad open a
| bar in Long Beach 20 years ago. The city required us to
| pay for the maintenance of three streetside parking
| spaces, but that was it. Pay the city. We didn't have to
| build anything that didn't already exist.
| Suppafly wrote:
| >Parking lots are not mandated for bars in the US, at
| least not everywhere.
|
| 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.
| Suppafly wrote:
| >Usually parking minimums are WAY too high in required
| parking spaces to make sense in most cases.
|
| 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.
| xmprt wrote:
| > You aren't going to stop the US from being car centric
|
| 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.
| Suppafly wrote:
| Sure you can slowly, over a long time, convert already
| dense areas into being less car centric, but you aren't
| going to make the rest of the country that way. Parking
| minimums, when they exist, are set by super local
| governments, they already don't exist or are set very low
| in areas of high density. The solution is to increase
| density, but again you aren't going to do that in the
| rest of the country. Random bars in Ohio are still going
| to have large parking lots, because land is cheap and
| given the choice, most people prefer less density.
| throwaway290 wrote:
| 82k places in Korea include any restaurant or joint or
| karaoke with a license to serve alcohol. Personally I would
| not care to call 80% of them "bar".
|
| 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.
| saalweachter wrote:
| Ok, that gets the numbers in line -- there are about
| 27,000 liquor licenses in Ohio, according to a random
| Google, which is about the same per capita.
|
| South Korea apparently ranks #97 on alcohol deaths, so
| it's apparently not a problematic number of bars, by
| global standards.
| forgotoldacc wrote:
| A lot of bars in walkable cities fit about 10 or fewer
| people. East Asia in particular has loads of tiny bars.
|
| Plus being able to walk or take a train home makes them far
| more accessible for people than needing to drive home.
| pjc50 wrote:
| Just to compare, they also have a tour for the UK
| https://www.math.uwaterloo.ca/tsp/uk/index.html : 49,687
| pubs.
|
| 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.
| robertlagrant wrote:
| > A culture of hanging out and drinking requires walkable
| urbanism.
|
| 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.
| tlb wrote:
| You didn't have to plan to get walkable urbanism before
| cars. It just happened because everyone needed a pub,
| store, school, etc. within walking distance.
| robertlagrant wrote:
| But it wasn't urban. That's my point.
| ToValueFunfetti wrote:
| This is also upper-bounded by the law; Ohio only issues one
| class D-5 liquor license (license to sell beer, wine, and
| spirits) per 2000 residents, which roughly maxes it out at
| ~5950 bars (in practice this looks to be rounded up on a
| per-town basis, making this an underestimate). An Ohio with
| the population of South Korea would only be allowed ~25000
| bars.
| kijin wrote:
| Looks like they got their hands on a dataset of every
| restaurant that is licensed to serve alcohol -- or at least a
| decent subset of such restaurants, filtered by menu or
| whatever.
|
| I checked a few dots near where I live and they're all fried
| chicken joints. Yeah, we do love _chimaek_ around here. :)
| yard2010 wrote:
| In korea after a certain hour every restaurant, karaoke,
| PCBang, and hotteok parlor is basically a bar :)
|
| God I miss this place so much <3
| bbno4 wrote:
| americans always compare massive cities to empty states
| notesinthefield wrote:
| Snark aside - I used this site which compares the country
| question to the location closest to you. I live in ohio.
| https://www.mylifeelsewhere.com/country-size-
| comparison/unit...
| mherkender wrote:
| South Korea has 5x the population of Ohio, but around 27x the
| number of bars [1]. So it really is a lot of bars.
|
| [1] https://www.ibisworld.com/us/industry/ohio/bars-
| nightclubs/1...
| deepspace wrote:
| As someone married to a Korean, I am not surprised in the
| least. Every single one I have met (males at least) drinks
| like a fish. It is impossible to describe to a westerner
| just how ingrained the drinking culture is over there.
| ZeroTalent wrote:
| They drink more than Eastern and Northern Europeans. It's
| insane!
| not_a_bot_4sho wrote:
| Empty lol
| numpad0 wrote:
| The entire US and North America is massively more empty
| relative to almost anywhere else, even most perceptually
| sparse countries. Many of European countries are 5-10x denser
| than US. 0: https://en.wikipedia.org/wiki/Lis
| t_of_countries_and_dependencies_by_population_density
| ekianjo wrote:
| And South Korea has one of the highest rates of stomach cancer.
| latentsea wrote:
| To be fair, it does sound like a pretty tough place to
| stomach.
| fakeBeerDrinker wrote:
| After living there for about four years, my mind goes
| immediately to soju. Not sure if there is a connection, but
| that's something I might deep dive with an LLM today.
| bigbacaloa wrote:
| "Bar" doesn't mean the same thing in every country. In Spain
| although a bar serves alcohol of all kinds it is also where one
| eats breakfast and lunch and gets a coffee. They are
| indispensable social centers and even a tiny town of 150 has
| one.
| anthk wrote:
| Town? More like village. You can have a nearly empty church,
| but there's no village without a bar.
| bobxmax wrote:
| If this is correct, it seems like Seoul has over 40x the number
| of bars that Chicago has, despite having only about 4x the
| population
|
| How in the hell?
| ceejayoz wrote:
| The bars may be much smaller.
| testing22321 wrote:
| Many countries have much more used "public" spaces, and
| people spend much more time in them, together.
|
| 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.
| bobxmax wrote:
| Sure, but that's still an astronomically higher number of
| bars
|
| 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.
| gniv wrote:
| I checked a few and there's a lot of restaurants included.
|
| https://www.math.uwaterloo.ca/tsp/korea/data/korea81998.xy.t...
| BrtByte wrote:
| South Korea really said "you will not be thirsty on our watch."
| jihadjihad wrote:
| What's really cool is if you go to a site like [0] that shows
| the "true" size of countries etc. (i.e. not distorted by a
| projection), Indiana is probably the most analogous state to
| South Korea, in terms of size and shape. But South Korea has 7x
| the population of Indiana!
|
| Really puts into perspective a movie like "Train to Busan",
| which would be like taking a train from Gary to Madison!
|
| 0: https://thetruesize.com
| flerchin wrote:
| Oh no, looks like a few new bars opened up, and a few others
| closed. Time to recalculate.
| noduerme wrote:
| 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.
| internetter wrote:
| Proper routing is also an expensive computation. Yes you could
| just run A* or something on the roads but that would assume no
| closures, no one way roads, wouldn't account for elevation
| change, ect. Using a proper routing API is almost certainly
| cost prohibitive
| moralestapia wrote:
| >Our computation produced a tour together with a proof that it is
| a shortest-possible route [...]
|
| Proof nowhere to be found.
|
| Waterloo-ers are nice people but I see an increasing trend of
| them just lying to get some cred. Come on guys, you don't have to
| follow the valley model _that_ much.
| inasio wrote:
| Not sure what you expected to get. The Concorde TSP solver is
| an exact solver that uses branch and bound search, it will
| return either a solution with a specified bound or the optimal
| bound. They provide the dataset and the solution they found
| (and I believe their solver is open source), if you don't
| believe them you can go ahead and find a better tour.
| 7e wrote:
| I also expected to get an actual proof.
| inasio wrote:
| Proof in this case is that the upper bound and the lower
| bound of the solver converged. This is not like a SAT
| solver where the solution itself can be trivially evaluated
| to verify the solution, it requires trusting that the
| solver does what it's supposed to be doing, similar to what
| happens when you solve a MILP with Gurobi or CPLEX.
| alexchamberlain wrote:
| Is the solver guaranteed not to land in a local
| minima/maxima?
| moralestapia wrote:
| (I don't know)
|
| 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.
| unnah wrote:
| The branch-and-bound algorithm does provide a proven
| optimal solution. This does not mean that P=NP because
| the size of the proof is not bounded by a polynomial in
| the input size, and neither is the algorithm runtime.
| Also, Euclidean TSP is known to be easier than TSP on
| arbitrary graphs: there are polynomial-time approximation
| schemes that can produce solutions with an (1+epsilon)
| factor of the optimum in polynomial time, for any value
| of epsilon. Thus it is not surprising that a proof of
| full optimality can be constructed for some instances.
| inasio wrote:
| The solver generates a relaxed lower bound that indicates
| how far they could be from the global optimal solution.
| The moment that the lower bound improves enough to match
| a path they can guarantee that it's the global optimum
| unnah wrote:
| You could still save the branch-and-bound tree, the LP
| problems solved at the tree nodes, the derivations of the
| LP cutting planes, and the LP solutions that together
| constitute the proof. Then you could in principle create
| an independent verifier for the branch-and-bound tree and
| cutting plane derivations, which could potentially be
| much more straightforward and simple code than the entire
| Concorde TSP solver, and wouldn't have so high
| performance requirements.
| moralestapia wrote:
| People really really really need to take some time to
| understand the concept of "burden of proof", so they can't
| stop making fools of themselves in public.
| amscanne wrote:
| What are you actually expecting here?
|
| 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.
| moralestapia wrote:
| >What are you actually expecting here?
|
| Didn't you read my comment?
|
| A proof.
|
| Why?
|
| Because they claim to have one.
|
| How?
|
| A link to a paper or something.
|
| Come in, this stuff is very low level.
|
| >But you can just run the bounding algorithms yourself,
| or prove they are incorrect.
|
| People really really really need to take some time to
| understand the concept of "burden of proof", so they
| can't stop making fools of themselves in public x2.
| amscanne wrote:
| The proof here is essentially the execution log of the
| bounding program. I imagine that this would be TB, PB or
| beyond. Not every proof is some clever paper, some are
| just brute force. Like proving a number is prime, or
| calculating the Nth digit of Pi. A paper doesn't always
| make sense, but you can still announce what you've done
| (and maybe you get a paper with algorithmic details, but
| it's not a proof for specific the instance).
| ChrisRob wrote:
| These claims are provisional. Until someone produces a better
| tour or a valid counter-proof, this stands as the best-known
| solution.
| moralestapia wrote:
| >Our computation produced a tour together with a proof that
| it is a shortest-possible route [...]
|
| >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.
| rendaw wrote:
| The code is here I think:
| http://webhotel4.ruc.dk/~keld/research/LKH/ although on another
| page they mention LKH-Merge and I'm not sure what merge is.
| kopirgan wrote:
| Very interesting..
|
| Is anything supposed to happen if you click on those red circles?
| I was hoping it will show name or other info!
| bjornsing wrote:
| 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.
| pkhuong wrote:
| It's classic Lin Kernighan
| (http://webhotel4.ruc.dk/~keld/research/LKH/) for the primal
| heuristic, and optimality proof by Concorde for cutting plane
| generation and branching
| (https://www.math.uwaterloo.ca/tsp/book/index.html, or
| https://www.math.uwaterloo.ca/tsp/korea/computation.html for
| details specific to this instance), with CPLEX as the
| underlying LP solver.
| marvinkennis wrote:
| It would suck to get to bar 51,248 only to find out it's now
| permanently closed
| Mountain_Skies wrote:
| There was a man who documented his travel to every country in
| the world. Not long before he was finished, South Sudan gained
| independence and he had to take a special trip there to
| complete his journey, which apparently had already completed
| all the other countries in Africa long ago.
| awesome_dude wrote:
| Kids, we're going on a road trip!
| rurban wrote:
| 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.
| eduardosalaz wrote:
| There is tons of work to do on running optimization algorithms
| in GPU. In its current form, Branch and Bound and Cutting
| Planes do not gain an advantage if implemented in CUDA. There
| is a new algorithm, PDLP, which is implementable in GPUs but it
| is still in early stages. For more, see
| https://blogs.nvidia.com/blog/cuopt-open-source/.
| JohnKemeny wrote:
| The thing is that Euclidean TSP needs a lot of data to encode
| hard instances.
|
| 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.
| rurban wrote:
| Yeah, I probably mixed it up with the Hamiltonian Path
| problem. It was a long time ago
| moralestapia wrote:
| >80k with proof
|
| Post proof.
| blt wrote:
| 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.
| DennisL123 wrote:
| OSRM lead dev here. Love to see this large of an instance being
| solved.
| Animats wrote:
| 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.
| amscanne wrote:
| Note that the tour itself was found quickly using a heuristic
| solver
| (https://www.math.uwaterloo.ca/tsp/korea/computation.html), the
| achievement here and all the computation is to establish that
| this is the lower bound (assuming I understood correctly).
|
| 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).
| n4r9 wrote:
| The algorithm that OP describes is more commonly known as
| 2-opt [0]. The heuristic used in this case is referred to as
| LKH which I assume means the Lin-Kernighan Heuristic [1]. The
| latter is sort of a meta generalisation of the former.
|
| [0] https://en.m.wikipedia.org/wiki/2-opt
|
| [1] https://en.m.wikipedia.org/wiki/Lin%E2%80%93Kernighan_heu
| ris...
| vjerancrnjak wrote:
| 2-opt is a bit simpler.
|
| LKH is a bit different, refers to Lin-Kernighan+Helsgaun --
| http://webhotel4.ruc.dk/~keld/research/LKH/
| yobbo wrote:
| Iirc the (probably simplified) LKH heuristic they used:
| 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
|
| n is a small number like 4 maybe 5?
| vjerancrnjak wrote:
| 2-opt: [a, b, ..., d, e]
|
| 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)
| neves wrote:
| https://www.youtube.com/watch?v=tChnXG6ulyE
|
| Author's presentation about it
| ustad wrote:
| "The locations were downloaded from a database maintained by the
| Korean National Police Agency."
| gku wrote:
| 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."
| gampleman wrote:
| But that presumably doesn't handle the relative motion of the
| stars, which makes the problem even trickier, since the
| distances will change as you travel, no? Or is my astronomy off
| base here?
| paulluuk wrote:
| I think your astronomy skills are correct, but if we have to
| worry about actual travel then you would also have to
| consider things like fuel capacity, refuel opportunities, the
| fact that you probably don't want to actually fly through a
| star but around it, etc.
| gampleman wrote:
| I think it's still valid to have a distinction between
| travel logistics and having a route that's at least
| theoretically possible. I suppose what they've calculated
| would work with a star gate like system, but then I'm not
| sure what the point of having minimal distance would be.
| consp wrote:
| Isn't the flying around problem just "e" since it is so
| many orders of magnitude less than the distance between
| stars that for this calculation it is irrelevant anyway?
| elymar wrote:
| The bar problem has its own issues. With that many bars
| some may close or new ones may appear during the time of
| the walk.
| manmal wrote:
| At that point we should also factor in time relativity,
| making it hard to measure the actual location of the stars
| at all.
| batuhandirek wrote:
| This also doesn't handle new bars being opened and closed as
| you travel. Not to mention bouncers having bad days so you
| will have to revisit the bar.
| pverghese wrote:
| I don't think this is presented as a means to get drunk
| around south korea. It's just an interesting application of
| TSP
| nurettin wrote:
| But they are so far apart and move on roughly the same
| trajectory that it shouldn't really matter.
| marcellus23 wrote:
| That's not true. The tour is 16.2 billion light years long,
| so even at the speed of light, it would take more than the
| current age of the universe to travel. Stars will move _a
| lot_ over that period of time.
| nurettin wrote:
| Yes I was assuming instant travel, even with one star the
| trajectory will be nonlinear.
| HPsquared wrote:
| Has anyone done the opposite of this, finding the longest
| possible route?
| z3t4 wrote:
| 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
| bk496 wrote:
| Where?
| throwaway519 wrote:
| Does it put the order of others off,i.e. a net loss?
| tiernano wrote:
| 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".
| finalhacker wrote:
| impresive, I have forgot TSP after graduated.
| Uptrenda wrote:
| traveling drinking man's problem
| TehCorwiz wrote:
| No it's: The traveling ale-man's problem. ;)
| bk496 wrote:
| Does it account for "pit stops"
| sylware wrote:
| Is that one of the problem quantum computers would resolve
| instantly if it is actually possible to scale them up?
| Catagris wrote:
| 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.
| BrtByte wrote:
| 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
| nlitsme wrote:
| Seem i do need a pair of dry socks for part of the walk.
| ge96 wrote:
| Sadly I'm not a Soju fan
| pugworthy wrote:
| 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....
___________________________________________________________________
(page generated 2025-04-24 23:02 UTC)