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

111–120 of 147 posts

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

#111

Post by internetter »

noduerme wrote: post #12

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.

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

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

#113

Post by unnah »

moralestapia wrote: post #60
alexchamberlain wrote: post #50

Earlier quoted context omitted.

Is the solver guaranteed not to land in a local minima/maxima?

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

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.

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

#115

Post by alexfoo »

skrebbel wrote: post #109
vulcan01 wrote: post #103

Earlier quoted context omitted.

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

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?

Taxis exist.

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

#118

Post by skrebbel »

alexfoo wrote: post #115
skrebbel wrote: post #109

Earlier quoted context omitted.

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?

Taxis exist.

The parking minimum is for taxis?

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

#119

Post by BrtByte »

OsrsNeedsf2P wrote: post #4

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

Gotta respect the planning that went into choosing a problem that's both absurd and actually solvable

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

#120

Post by mherkender »

bbno4 wrote: post #44
notesinthefield wrote: post #8

I am overwhelmed with the thought of nearly 82 thousand bars within a country roughly the size of Ohio.

americans always compare massive cities to empty states

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

Post reply on HN