The Traveling Salesman Problem (TSP) is NP-Hard.
Finding the optimal route to visit even a moderate number of cities would require more computation than what we have available on this planet. See Wikipedia.
So why are real traveling salesmen not totally paralyzed?
Because they are intelligent. Which means they do not have to be Scientifically Correct.
Intelligence is the ability to jump to reasonable conclusions on scant evidence, based on a lifetime of experience. Because scant evidence is all we will ever have in the real world.
So real travelling salesmen just pick a reasonable route and follow that. The need to be mathematically optimal is a non-goal in real life.
Mathematicians adopt the Reductionist Stance because Math requires that.
Traveling Salesmen, like humans in almost all everyday situations, find solutions to their everyday problems by adopting a Holistic Stance. Where good enough is, well, good enough.
The 2012 breakthrough in Artificial Intelligence happened because we figured out how to write computer programs that jump to conclusions on scant evidence.
AI is not Scientific. A lot of people are unhappy about this. 😀
I expect AI to help us with “The Remaining Hard Problems” – problems that do not have solutions that would satisfy Reductionist criteria for optimality, completeness, repeatability, and explainability. Things like the global economy, drug interactions in the human body, the complexity of the brain, genomics, global politics, etc.
Species level problems require a Holistic Stance
My Red Pill post discusses this (and many other surprises enabled by a Holistic Stance) in great detail.