[vanderZwan]

> I wonder how many other "in the trenches hacks" people have done that overturn widely accepted things the inventors didn't realize were a big deal: "well I usually have a bunch of deliveries to make and I've figured out a clever way to map out the quickest path... "

A lot of them. Having said that: yes, I can imagine that others would have thought up Dijkstra's shortest path algorithm, since he himself said it came to him while shopping, and that it only took him twenty minutes to reason through the original O(n²) algorithm. (edit: oh wait, that's what you're alluding to isn't it? Heh, that went straight over my head).

On the other hand, I don't think the faster versions of Dijkstra's algorithm would have been invented by anyone without at least some understanding of priority queues and big-O behavior. And at that point I hope people realize that they possess some specialized knowledge that might not be entirely common.

In fact, I'd argue that the true strength of Dijkstra's write-up is that it gives us a vocabulary to reason about it and come up with specialized data structures for particular situations.

Anyway, what you're touching on is the difference between engineering and science: engineering works with confidence built from tests, rules of thumb that reflect lessons learned from historical results, and (in modern times) verified predictions from science. Those rules of thumb might be used when lacking a deeper scientific understanding of why it works. The tests might exist to work around the limitations of scientific knowledge (e.g. modelling turbulence). Science creates insights and predictions through modelling of empirical results. At least that's the difference according to Bill Hammack[0].

In an ideal world the two professions work together and build on each other's results to propel each other forward of course.

[0] https://www.youtube.com/playlist?list=PL0INsTTU1k2X4kCPqmi1e...

[chrisweekly]

> "some specialized knowledge that might now be entirely common"

now -> not, right?

great comment

I'm not being pedantic about a typo, but it reverses the point I think you're making about UNcommon knowledge...

[vanderZwan]

Yes, that was a typo that made it look like I contradicted myself, thank you for catching that :)

[kristopolous]

I was referring to the general TSP being solved.

[vanderZwan]

Eh, the trading salesmal problem is more like the Collatz conjecture: it looks simple but there's a lot of complexity hiding under the surface, and it requires some expertise to truly understand why it's really hard. So then we're talking about the opposite problem.

Note that your informal description did not match the TSP since there's no reason to disallow backtracking or visiting the same place twice.