I was thinking about the Travelling Salesman problem this morning. I came up with an algorithm that permits a few nice optimizations. My guess is that Knuth probably already came up with this algorithm, formally analyzed it, and then came up with 15 others that were much better. Nonetheless, I figured I'd jot it down.

Rather than picking the first segment of the journey and working my way to the end, I want to pick a middle segment of the journey and work my way outwards recursively.

Given a list of distances (or times, or costs, or whatever) between cities, sort the list from shortest distance to longest distance regardless of which cities are involved. Now, loop over this list and use each element of the list as a middle segment of your journey. This gives us a list of "first steps" (or rather, first midd…

**Warning**: This is a rough draft of an algorithm. You shouldn't bother reading this if you want real rigor. I'm just writing it down to get it off my chest.Rather than picking the first segment of the journey and working my way to the end, I want to pick a middle segment of the journey and work my way outwards recursively.

Given a list of distances (or times, or costs, or whatever) between cities, sort the list from shortest distance to longest distance regardless of which cities are involved. Now, loop over this list and use each element of the list as a middle segment of your journey. This gives us a list of "first steps" (or rather, first midd…