Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Shortest-possible walking tour to 81,998 bars in South Korea

math.uwaterloo.ca

Post reply on HN
Print view View original

71–80 of 147 posts

Re: Shortest-possible walking tour to 81,998 bars in South Korea

#71

Post by vjerancrnjak »

n4r9 wrote: post #66
amscanne wrote: post #56

Earlier quoted context omitted.

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 i…

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_heuris...

2-opt is a bit simpler.

LKH is a bit different, refers to Lin-Kernighan+Helsgaun -- http://webhotel4.ruc.dk/~keld/research/LKH/

Re: Shortest-possible walking tour to 81,998 bars in South Korea

#72

Post by paulluuk »

gampleman wrote: post #68
gku wrote: post #64

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."

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?

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.

Re: Shortest-possible walking tour to 81,998 bars in South Korea

#73

Post by batuhandirek »

gampleman wrote: post #68
gku wrote: post #64

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."

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?

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.

Re: Shortest-possible walking tour to 81,998 bars in South Korea

#74

Post by vjerancrnjak »

yobbo wrote: post #65
Animats wrote: post #52

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 optima…

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?

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)

Re: Shortest-possible walking tour to 81,998 bars in South Korea

#75

Post by forgotoldacc »

codemac wrote: post #45
lifthrasiir wrote: post #16

Earlier quoted context omitted.

That country has a population of 52 million, i.e. about 5 times Ohio.

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...

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.

Re: Shortest-possible walking tour to 81,998 bars in South Korea

#76

Post by skrebbel »

xmprt wrote: post #53
codemac wrote: post #45

Earlier quoted context omitted.

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...

I don't think bars in Korea have parking minimums like they do in Ohio.

What's a parking minimum?

Re: Shortest-possible walking tour to 81,998 bars in South Korea

#78

Post by gampleman »

paulluuk wrote: post #72
gampleman wrote: post #68

Earlier quoted context omitted.

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?

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.

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.

Re: Shortest-possible walking tour to 81,998 bars in South Korea

#80

Post by chmod775 »

skrebbel wrote: post #76
xmprt wrote: post #53

Earlier quoted context omitted.

I don't think bars in Korea have parking minimums like they do in Ohio.

What's a parking minimum?

The minimum number of parking that needs to be available per seat/dining area.

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.

Post reply on HN