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

Computer Scientists Break Traveling Salesperson Record

quantamagazine.org

Post reply on HN
Print view View original

161–170 of 188 posts

Re: Computer Scientists Break Traveling Salesperson Record

#161

Post by ClikeX »

doctor_eval wrote: post #121
robohoe wrote: post #119

Earlier quoted context omitted.

Lately it feels like agile is where innovation goes to die :(

I agree. It’s sad. Agile principles are awesome, but by the time you run them through many company’s implementations of Scrum or SAFe or (God forbid) Jira, you may as well just do waterfall. I don’t think waterfall is necessarily bad, that agile is always right, or that there aren’t other good practices. But practicing waterfall and calling it “agile” is rarely going to end well for anyone.

We do Scrum at my office. But really, it's just applying sprints to waterfall. We do get some shorter feedback loops to improve features before going live. But the whole scope is still set at the start of the project, and that scope needs to be completed at the end of it.

And to be very honest. It doesn't work if the people in the team don't think Agile. Your team needs to be able to self-reflect and try to improve themselves just as they'll do with client work in a sprint.

Re: Computer Scientists Break Traveling Salesperson Record

#162

Post by scoot »

stevedzreams wrote: post #156
aidenn0 wrote: post #128

Earlier quoted context omitted.

Route-finding is much simpler than traveling salesperson. The hard part for real-world directions is getting the cost-function right. Older map systems used to make some very questionable assumptions that made them quite inaccurate (one example; assume all highway miles are equal; some were 55MPH and have traffic lights, railroad crossings and stop-signs others were 65 with no at-grade intersections -- today even hig…

We have a related problem in the UK. Sometimes very small "country lanes" have no explicit speed limit, so defaults to national speed limit of 60mph, which you would have to be suicidal to drive at (or just hate your car), but Google maps still often route finds along these roads. An example: https://maps.app.goo.gl/HhMWPgE2gznsPsQ9A

Except that Google uses an average of the recorded speed of vehicles using a road segment, linked to time of day, and not the speed limit.

Re: Computer Scientists Break Traveling Salesperson Record

#163

Post by mousebaiker »

fjfaase wrote: post #138
chottocharaii wrote: post #120

Earlier quoted context omitted.

Hey man, this is just a person’s fun and imaginative side project. Is there a reason you’re offering such serious and negative critical commentary on this?

I think the parent wanted to point out that this is about a completely different problem. The algorithm mentioned works on cities that are defined with coordinates in some plane and where the distances between two points is defined as the geometric distance. The article talks about the problem where the distances between cities are given (and not based on their coordinates). The later is a much harder problem.

The original paper mentioned in the article [1] deals with metric TSP, so a triangle inequality must be satisfied. This means that you can actually find a space where the points will be the coordinates.

Anyway, the grandparent solves the Euclidean TSP which is still an NP-complete problem. I will be reluctant to say that it is an easier problem in a general sense. I agree though that there are better and easier approximations for it.

[1] https://arxiv.org/abs/2007.01409

Re: Computer Scientists Break Traveling Salesperson Record

#164

Post by Nightshaxx »

scoot wrote: post #162
stevedzreams wrote: post #156

Earlier quoted context omitted.

We have a related problem in the UK. Sometimes very small "country lanes" have no explicit speed limit, so defaults to national speed limit of 60mph, which you would have to be suicidal to drive at (or just hate your car), but Google maps still often route finds along these roads. An example: https://maps.app.goo.gl/HhMWPgE2gznsPsQ9A

Except that Google uses an average of the recorded speed of vehicles using a road segment, linked to time of day, and not the speed limit.

This. Google has a major advantage in that they have a massive dataset. They can use their data to improve the cost function even in real time to detect traffic.

Re: Computer Scientists Break Traveling Salesperson Record

#165

Post by 0xfaded »

bigiain wrote: post #122
booleandilemma wrote: post #91

Earlier quoted context omitted.

“so you don’t have anything to demo, then?”

Interestingly, I demoed and shipped a wayfinding solution for a mobile app earlier this year, where I just brute forced the shortest paths between all pairs ~200 "intersections" in the area of interest for this event, and just stored the answers in a KV store based on the intersections (then does some cheesy last 20m stuff to route you to and from the nearest intersections to your location and destination). In a limi…

Check out google-ortools which does just this.

Re: Computer Scientists Break Traveling Salesperson Record

#166

Post by cyberdrunk »

scoot wrote: post #162
stevedzreams wrote: post #156

Earlier quoted context omitted.

We have a related problem in the UK. Sometimes very small "country lanes" have no explicit speed limit, so defaults to national speed limit of 60mph, which you would have to be suicidal to drive at (or just hate your car), but Google maps still often route finds along these roads. An example: https://maps.app.goo.gl/HhMWPgE2gznsPsQ9A

Except that Google uses an average of the recorded speed of vehicles using a road segment, linked to time of day, and not the speed limit.

... which, given that most people are speeding, makes their estimates completely unrealistic if you want to actually obey the law.

Re: Computer Scientists Break Traveling Salesperson Record

#167

Post by cyberdrunk »

pjmlp wrote: post #155
doctor_eval wrote: post #121

Earlier quoted context omitted.

I agree. It’s sad. Agile principles are awesome, but by the time you run them through many company’s implementations of Scrum or SAFe or (God forbid) Jira, you may as well just do waterfall. I don’t think waterfall is necessarily bad, that agile is always right, or that there aren’t other good practices. But practicing waterfall and calling it “agile” is rarely going to end well for anyone.

Waterfall is actually agile, if one bothers to read the original paper properly, regardless of its bad name.

The whole idea of waterfall as I know it is to have large-ish iterations (typically a couple months), which comprise of analysis, dev and testing stages. Is this different from what you have in mind?

Re: Computer Scientists Break Traveling Salesperson Record

#168

Post by pjmlp »

cyberdrunk wrote: post #167
pjmlp wrote: post #155

Earlier quoted context omitted.

Waterfall is actually agile, if one bothers to read the original paper properly, regardless of its bad name.

The whole idea of waterfall as I know it is to have large-ish iterations (typically a couple months), which comprise of analysis, dev and testing stages. Is this different from what you have in mind?

That is page one of the waterfall document, there are other pages though.

https://pragtob.wordpress.com/2012/03/02/why-waterfall-was-a...

Re: Computer Scientists Break Traveling Salesperson Record

#169

Post by cyberdrunk »

MaxBarraclough wrote: post #84

> able to subtract 0.2 billionth of a trillionth of a trillionth of a percent ... > “This is a result I have wanted all my career,” said David Williamson of Cornell University, who has been studying the traveling salesperson problem since the 1980s I love this. Oh to be a theoretician. Here's hoping for a flood of further improvements.

Honestly this sounds like taken from The Onion.

Re: Computer Scientists Break Traveling Salesperson Record

#170

Post by dt123 »

MaxBarraclough wrote: post #84

> able to subtract 0.2 billionth of a trillionth of a trillionth of a percent ... > “This is a result I have wanted all my career,” said David Williamson of Cornell University, who has been studying the traveling salesperson problem since the 1980s I love this. Oh to be a theoretician. Here's hoping for a flood of further improvements.

> Yet this minuscule improvement breaks through both a theoretical logjam and a psychological one. Researchers hope that it will open the floodgates to further improvements.

Please don't take quotes out of context

Post reply on HN