> “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.
In a limited-enough space (like an event), this works out just fine. I'm glad I'm not the guy who needs to solve GoogleMap's routing problems though. I wonder if they have a huge BigTable store of every street intersection pair on the planet and a recalculated best route between them? I _hope_ they do something smarter than my "works in my constrained requirements space" brute-force hack...
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 higher speed limits are seen as the lingering effects of the national speed-limit have worn off).
Even after 1995, many states were very slow to raise the speed limit (I lived near the Maryland/Virginia boarder and remember Maryland did well before Virginia), and when they did raise the speed limit it was by small amounts.
Today, you can drive from Los Angeles to New York and not hit any significant stretches of freeway with speedlimits under 65, and west of the Mississipi river, you will spend most of it at 70mph or higher.
On top of that, the actual speed that will get you pulled over can be much higher (In CA you are very unlikely to get pulled over for single-digit MPH speeding on a freeway, making a 65 speed limit a de-facto 74; in the northeast US it's not uncommon to get pulled over for going just 5MPH over the posted limit).
The NMSL (National Maximum Speed Limit) was enacted in 1973, modified in 1987 to allow 65 mph speed limits on rural interstates, and repealed in 1995.
Many states in the southeast, midwest and west raised their posted speed limits very soon after the NMSL was repealed. States in the northeast took a bit longer to update their laws to remove their state maximum speed limit.
Edit: to add value to the conversation: in germany I find googles estimates on long car trips quite accurate. And I'm actually a very erratic driver, sometimes taking every hole in traffic I can to get ahead, just slowing down to speed limit+20km/h where there is a speed trap, sometimes just cruising 80km/h on open autobahn getting overtaken by cargo trucks
FWIW, Advisory speed-limits on autobahn are similar to the western US statutory speed limits (130km/h == 80mi/h). That being said, 200km/h and no other moving violations would quite possibly get you thrown in jail in "The land of the free"
Unfortunately IIRC most of the screenshots I took show my actual address/immediate surrounding area etc, so they'd be fairly heavily censored. If anyone [is actually reading this and] is especially interested, I can try braving my scary not-organized screenshot archive and try and find them.
I kinda feel all the _actual_ innovation is doing things that align with Agile's underlying principals of valuing individuals/working-software/response-to-changes over processes/documentation/plans - while all th3e people who _talk_ about doing "Agile" rarely follow those principals, and mostly just mean "We have meetings we call 'standups', and negotiated deadlines that we call 'sprints'".
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.
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.
You cannot appoint somebody to the strange title of “scrum master” (which I guess makes the rest of us scrum slaves?) to lead a process of “daily scrum” where we look together at a kanban board and make sure that we are “sprinting” and then turn around to insist that you value “individuals and interactions over processes and tools,” which is ¼ of the Manifesto. You have voted with your intention and your vote was to value your process and tools over trusting the individual developers and letting them have direct interactions with your customers.
Even the word “sprint.” I used to play Ultimate in one of the teams in the Dutch national league, it is a sprinting sport. The word “sprint” means exhaustion. It means stopping. If you jog around in Ultimate you lose, you have to rest, sprint, rest, sprint. If your model is “always sprinting” then do not tell me that you value “individuals and interactions.” And if you do value the latter please either (a) remove the metaphor “sprint” from your process or (b) add “rest weeks” after each sprint to “clean up” the mess you made! Anything else is lying to yourself.
The phenomenon of estimating “story points” is even worse, no? It is intrinsically about processes and tools and the idea of a developer having a phone call or face-to-face with the client directly to see if this feature request is actually accurate, deciding that it is not, and trashing it to open a different request... it's not just “do we claim those juicy story points when this happens?” but also “was part of your measure of ‘complexity’ the complexity of determining that the Ask did not meet the Need?” ...And so the fundamental idea of estimating a “todo” does not fit well with agile, whereas you can estimate “in progs” and “done” just fine.
And before you say “no by the time we estimate we should already know that we want the feature, devs should never have to talk to clients,” please be aware that this response explicitly abdicates another ½ of the Agile manifesto, “customer collaboration over contract negotiation” and “responding to change over following a plan.” The whole point of the Agile manifesto is that your kanban board is stale. Not because it's a kanban board, but because it is written down. Like one of the four principles (the last ¼ not covered in the above ¾) is explicitly anti-literary.
This is sort of “no true Scotsman” of me but my read is that the moment Agile was systematized, it died a little on the inside. It was a “screw your systems!” reaction that then got steamrollered by the real world, where “bullshit jobs” and middle management reign even though they bespeak a bureaucratic feudalism rather than a lean-and-mean capitalism.
What I am challenging in the above is that there is a "lip service" given rather than a deep assimilation. So when the principles say "business people and developers must work together daily throughout the project" they mean that there should be an open-door policy, “hey Amanda I am working on the Estimating-Work-in-Process application and I was wondering what you do with ____” “Oh, that is not supposed to be possible,” type of interactions. The ‘lip service’ is “your boss will answer any questions at daily stand-up.”
Because these interactions are routine, the idea of needing constant scheduling and progress updates ideally ‘should be’ a lesser issue. People want progress updates to make sure that you are not spending all your time on Reddit, they will be able to see that more readily if they see you working.
The core of agile is anti-establishment thinking. One of the principles is “The best architectures, requirements, and designs emerge from self-organizing teams. At regular intervals, the team reflects on how to become more effective, then tunes and adjusts its behavior accordingly.” Elsewhere Don Wells elaborates on it, “Don't panic. With professional software engineers on our project we can relax knowing that the team will do what is needed to get the job done. Any activity needed with any combination of people will just get done without any further scheduling or ceremony. This is the spirit and benefit of a self organizing team.”
And so a fundamental idea of agile, perversely enough, is that you’re not going to have one size fits all, there is no one ‘proper implementation.’ There is just the way that you made it work. If you have different personalities it’s gonna express differently.
I am not being facetious here, though I realize it sounds kind of like it! Adam Savage had a great video a little while back about something unrelated—weathering prop money—where he took live questions from the audience, and one question was about “the best way” to make that money look bloody, and he answered in true artisan style:
> So, your question though, “what is the best way”... The answer is, there is no, there is no best way! There is the way you figure out how to do it. Yeah! That’s really the thing. It may be that you’ve gotta, like, take a brush and kinda work at a whole bunch of different bills, and then take the stack and then effect the stack, right?, I think that’s like a multi-stage process, and then you should do some tests with different paints and see, like, under the lighting conditions these will be seen—I don’t know if it’s for a theater or a film—does it communicate? Does it tell you that it’s bloody, dirty money? That’s the question to be asking, you gotta hold it up, look at it, [mimes looking at it and pausing and thinking] “does that sell to me?”—and ask other people, “does this sell?”... and like most of the time they’re gonna go, “no,” and you’re gonna keep on going. But it’s trial and error.
And like the fundamental story about agile is that agile is trial and error, it is about trying to work together as a team and being like “did that work” and the answer is usually “no, Leah is totally burned out after she had to work 60+ hours of straight development that one week,” or “Alvin is having trouble with nobody inviting him in, he wants to start contributing to this project and everybody is like ‘nah man we got it’ and he is being excluded” and you’re gonna have to reshape. There is a necessary aspect of vulnerability in other words in any proper development strategy whether top-down design-first waterfall or agile or something else.
There is no one agile software development process. There is a set of agile software development values. It is a values-driven approach, “how are we living up to our self-commitments today?” rather than “did I follow the appropriate procedure?” And thus it is quite anarchist at its fundamental core. This is probably why I am ragging on scrum in the end, scrum came in and said “there is a non-anarchist way to do agile” and I am sitting here like “uh, do you know what you just said?”
With that said, all the usual caveats, I understand that you want to be able to state what all is likely to be in an upcoming release and what all isn’t and this requires creating estimates and so forth. But perhaps the most damning thing is when estimates turn into deadlines. When an estimate becomes a deadline it gets padded and re-padded, then the urgency of the feature gets de-emphasized because you have such an abundance of time to do it in, so you spend a bunch of time up-front completing your “design doc” about what you are about to build and then someone asks to weigh in and “approve it” and you have reinvented waterfall.
I've only seen scrum implemented as a planning tool. But the teams aren't truly agile.
> And like the fundamental story about agile is that agile is trial and error, it is about trying to work together as a team and being like “did that work”
This is exactly what I meant with needing the team to be able to self-improve based on experiences. You can trial-and-error velocities all you want. But if you don't employ that same agility on a deeper level it's never going to work anyway.
Please don't take quotes out of context
This wasn't intended to be read as sarcastic. It really is a great development. It's still amusing that the number is so tiny.
Simulated annealing was inspired by thermodynamic free energy involved in crystal formation from annealing metal. 
I combined it with a Breath of the Wild waypoint generator  to make my way around the map  in a mostly optimal fashion for my trip about Hyrule.
If you ever have a toy problem or even a real one, I suggest experimenting with pytspsa to see and understand in a concrete way the problem is solved.
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?
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.
I had good results with genetic algorithms as well.
That is 0.0000000000000000000000000000000002% better than the existing solution.
Where can I find more details on crystal quality in popular CPUs like Intel's Xeons?
It does mention choosing tree paths at random... so couldn't that be an improvement by chance?
It's lengthy and full of some quite technical sections, but those are interspersed with sections sketching the high-level intuition and proving more informal versions of the technical theorems in simplified cases. An example is on p. 19, section 3.1, "Ideas underlying proof of Theorem 3.1".
I think this is the paper?
> they were only able to subtract 0.2 billionth of a trillionth of a trillionth of a percent.
That’s so subtle to suggest but incredible hard to prove
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.)
Finding the optimal solution is NP-complete, but approximations are not necessarily so:
The TSP problem is NP-complete, but it may be possible to come up with an 'incomplete' algorithm that works efficiently for a large subset of the problem space, and it may be possible to find an approximate algorithm that efficiently finds guaranteed near-optimum solutions to all problems.
Neither of those two things requires doing the truly difficult (perhaps impossible) work of coming up with a precise, complete, and efficient algorithm to an NP-complete problem.
From the paper you linked:
heuristics based solutions are still superior to deep learning based solvers regarding accuracy and execution time for larger problem sizes.
circuit satisfiability and related hard problems are all reducible to each other
For example, given a list of cities, an approximate solution on actual roads to visit all of them once?
Someone should make a front end for this.
Older than you’d think.
> 0.2 billionth of a trillionth of a trillionth of a percent
Vandalizing HN like this is not cool.
Also you can't claim he ignored your many requests to stop, because you never made a single request to stop what can be interpreted the same way by both of you, he probably thought he followed them. Again, you were using this as manufactured justification to ban him.
Anyone who sincerely wanted to follow the rules at https://news.ycombinator.com/newsguidelines.html would be behaving completely differently. Sincere misunderstandings are generally quite easy to clear up. If someone doesn't sincerely want to follow the site guidelines, they shouldn't be posting here. We're trying for a specific kind of community.
Even the worst case is easy to fix. If someone doesn't want to be banned, they're always welcome to email email@example.com and give us reason to believe that they'll follow the rules in the future.
> When someone is routinely dropping lit matches in a dry forest, "he only started one wildfire" is obviously no defense.
He has lots and lots of comments of which only a couple that you didn't like. Absolutely nothing like "routinely dropping lit matches".
One could attempt to make this same argument over virtually any ban ever. There doesn't need to be a reason in my opinion. HN has never allowed freedom to express any opinion you want. A pattern of unpopular opinions tends to result in an automatic hellban, for example.
If somehow he slips and they manage to do it, he will rephrase them next time, make them more vague and more subjective to make sure they don't. Like I saw a warning he gave someone to stop creating new accounts every couple of comments, but then in other warnings he stretched his definition farther and farther to include more comments and more time.
But I figured that was just me being cranky and objectionable lately.
As an aside, can someone explain why a generic "-man" suffix is taken to indicate only the masculine by some people? It's no different than using the masculine for indefinite gender, so why the objections?
And 'a hundred years' is not much of a defense. Women couldn't sign a mortgage in the US in the 70's. I imagine folks defended that too - "Its the way we've always done it."
yeah you're going to need to provide a source for such a ridiculous claim. My grandmother has owned her house for much longer than that.
* edit: all you downvoters need to look at the claim being made instead of bringing up different issues. credit cards are not mortgages. "couldn't sign" is not the same as "needed a cosigner" or "discounted rates". the original claim implies that women could not own houses through a bank loan, which is very much false.
Specifically there wasn't a law to prevent it AFAIK, but in practice banks denied women lines of credit without their husband's approval as a course of normal business.
you still have not addressed the claim that "women could not sign mortgages in the 70s"
> Part I discusses the extent of discrimination against women in this field. It concluded that such discrimination is wide-spread and takes two forms. First, lenders discount a working wife's income when she applies with her husband for a home mortgage. Second, lenders are less likely to make a loan to a single woman than to a man.
Maybe not mortgages but this article from 2013: https://www.huffpost.com/entry/25-years-since-women-need_b_4... "25 Years Since Women Needed a Male Co-Signer". (Link should end "b_4164299".)
the original claim was "women couldn't even sign a mortgage in the US in the 70s".
that is a false claim.
Our recently deceased Supreme Court Justice was instrumental in securing that right.
Here's a brief history for the Google-challenged: https://www.directlendingsolutions.com/women_and_credit.htm
there is nothing in your link that says that women couldn't sign a mortgage.
the original claim is that "women couldn't even sign a mortgage in the US until the 70s." this claim is false.
Who cares? Did your ancestors coin the term or something? You can keep writing "salesman" whenever you write things yourself. "Salesperson" doesn't seem at all offensive, and I think it's bizarre to nitpick such a trivial and irrelevant aspect of the article. It reads to me like political virtue-signaling since the article has nothing to do with the gender of the traveling agent.
e: well? he's polynomial
It's often reduced to TSP.
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.)
But consider that we used to have the word "doctoress" to refer to a female doctor. Using that feels weird.
(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?)
And we are talking about human language here, it's something that has evolved over centuries, to a large extent spontaneously. That's why we make some distinctions and not others that may seem equally important.
If we were talking about a programming language your argument be more relevant, although I would still argue that sex is a much more dramatic difference than race.
Sort of like "model". Most of the time you just say "model" and it could be either sex, but if you want to talk specifically about male models you say that.
This level of specificity probably only works for media in which there’s only one main female character.
For an even weirder example, see ‘priestess’. No-one ever refers to modern female priests as priestesses, but historians often refer to, say, female priests in Ancient Rome as priestesses. On the other hand, historians never use the term ‘doctress’ for archaic female doctors.
“Solution of a Large-Scale Traveling-Salesman Problem“
Currently Google scholar shows ‘salesman’ with an order of magnitude more references than ‘salesperson’
My only point is that if we are going to fork the reference, we should use something that is easier to say. (I honestly don’t care if we fork the reference :) ).
Maybe it has an effect on behavior? I’m not sure of any research behind gendered language.
It's called the Sapir-Worff hypothesis. Pinker called it something like "the most well known hypothesis in linguistics, too bad it's almost certainly false." It's pre-Chomsky, in date and concept.
Nah, if it's offensive to me and you're trying to convince me of something or sell to me, it's clearly your problem.