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

81–90 of 188 posts

Re: Computer Scientists Break Traveling Salesperson Record

#81

Post by nefitty »

li4ick wrote: post #78
mensetmanusman wrote: post #20

If we are renaming things from the past to quell the moderns, it should be renamed Traveling Seller since it rolls off the tongue so much better.

Just stop already. Nobody notices these kinds of things, and if they're offensive to anyone, that's their problem. It's a math problem as old as the 1800s for gods sake. Stop already. Why, out of everything that is important in this world, would you immediately notice the fucking "man", out of all things?

I literally imagined a man in a 50’s style suit with a briefcase and wouldn’t have given it a second thought. I had to manually untangle that concept to add the realization that women can sell stuff too.

Maybe it has an effect on behavior? I’m not sure of any research behind gendered language.

Re: Computer Scientists Break Traveling Salesperson Record

#82

Post by r0ze-at-hn »

molticrystal wrote: post #49

While it is wonderful they are getting closer to solving it, if your problem is a simple and practical you can try some alternative algorithms. For fun, I used pytspsa [0] which uses the simulated annealing method to solve the TSP and applied it to BOTW. Simulated annealing was inspired by thermodynamic free energy involved in crystal formation from annealing metal. [1] I combined it with a Breath of the Wild waypoin…

Looking at the BOTW solution is doesn't seem to take into account the fact that a straight line is not the fastest solution. Climbing is incredibly slow, swimming is slow and perilous, in some places such as the dark forest you can only enter/exit in one place, not randomly, you can travel faster on roads.

I guess later in the game one doesn't mind randomly walking right by the castle just because it is the shortest path, just going to eat some time dealing with each guardian of course.

Same for swimming across a the river twice around a bend rather than just following the coastline.

Also there are 226 waypoints, the linked map is missing a lot...

I am not sure what it is trying to show. Was this the waypoints you had not done at the end of the game?

Re: Computer Scientists Break Traveling Salesperson Record

#83

Post by MaxBarraclough »

teknopurge wrote: post #79

It looks like it's predicated on an assumption that "nodes with odd numbers of edges have short edges." It's novel, but not reliable. I do love the breakdown and effort though - very useful.

> It's novel, but not reliable.

Isn't that really the best we can hope for? It's an NP-complete problem, but we can still realistically hope that researchers might discover efficient algorithms for solving subsets of the problem space, hopefully broad subsets.

If we get to the point that 90% of travelling salesman problems can be solved quickly, and the remaining 10% can quickly be approximately solved (to within 5% percent of the optimum solution, say), that would be pretty great, even if we never 'really' crack NP-complete problems. (Which, of course, might not even be possible.)

As an example, a smart TSP algorithm should be able to very quickly solve problems where all nodes fall on points in a circle.

(Disclaimer: this stuff isn't my wheelhouse, corrections welcome.)

Re: Computer Scientists Break Traveling Salesperson Record

#84

Post by MaxBarraclough »

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

Re: Computer Scientists Break Traveling Salesperson Record

#86

Post by gotoeleven »

dragonwriter wrote: post #70
echelon wrote: post #59

Earlier quoted context omitted.

I'm still confused whether it's appropriate to refer to actresses as "actor". The guidance appears to be skewed. (I'm being completely earnest here - I don't want to offend anyone.)

> I'm still confused whether it's appropriate to refer to actresses as "actor". It is generally appropriate, and increasingly preferred in many contexts, but not yet generally considered the only acceptable thing. (E.g., "actress" is almost never considered wrong .)

And the oscar for best actor who presently identifies as a woman in a leading role goes to...

Re: Computer Scientists Break Traveling Salesperson Record

#87

Post by jfk13 »

Grustaf wrote: post #74
Jabbles wrote: post #69

Earlier quoted context omitted.

It's not inappropriate to use "actress" yet. But consider that we used to have the word "doctoress" to refer to a female doctor. Using that feels weird.

Sex is not very important for a doctor, for an actor is pretty much defines what roles you can play.

Shakespeare might like a word...

(Alternatively: then why don't we have separate words for black actors, white actors, native American actors, south-east Asian actors, transgender actors, and so on?)

Re: Computer Scientists Break Traveling Salesperson Record

#88

Post by gotoeleven »

X6S1x6Okd1st wrote: post #28

For people that want to argue about salesperson vs salesman you may be comforted to know that you don't need to, it's already being done! https://en.wikipedia.org/wiki/Talk:Travelling_salesman_probl...

It reminds me of when at some point in the 90s everyone decided to stick it to jesus by changing B.C. to B.C.E.

Re: Computer Scientists Break Traveling Salesperson Record

#89

Post by lurquer »

nefitty wrote: post #81
li4ick wrote: post #78

Earlier quoted context omitted.

Just stop already. Nobody notices these kinds of things, and if they're offensive to anyone, that's their problem. It's a math problem as old as the 1800s for gods sake. Stop already. Why, out of everything that is important in this world, would you immediately notice the fucking "man", out of all things?

I literally imagined a man in a 50’s style suit with a briefcase and wouldn’t have given it a second thought. I had to manually untangle that concept to add the realization that women can sell stuff too. Maybe it has an effect on behavior? I’m not sure of any research behind gendered language.

Traveling Avon Lady?

Re: Computer Scientists Break Traveling Salesperson Record

#90

Post by pkaye »

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.

Meanwhile in an agile dev team.... "can you optimize it in the next sprint?"
Post reply on HN