[beagle3]

Of course. But it's O(n*2^n) at best, IIRC (The trivial is O(n!) - just test all orders)

There are simple <=2x and slightly more complicated <=1.5x guaranteed approximate solutions on metric spaces, but on most spaces there aren't even approximate solutions.

[AstralStorm]

It so happens that a map is a metric space. Euclidean metric. If you want to include transport, change it to optimal travel time metric. (Requires evaluating optimal travel time in the tested vicinity first. There are nice and fast algorithms to do it, starting with variants of A* and IDDFS.)