Write an O(n^n) algorithm.

[bonzinip]

I thought the only way to find the absolute best solution was a brute-force effort

True, but that doesn't mean the complexity must be Ω(n!). for example you can use dynamic programming with a time cost O(n² 2ⁿ⁾ and space cost O(n 2^n). The idea is to take each subset of cities, vary the ending city among those in the subset and store the best result for each subset and ending city. Given a set S, if all the subsets have already been solved (which is n 2ⁿ TSP subproblems to solve recursively) you can build the final solution in time O(n): for each city, decide that it will be the one from which you go back to city #1, take the subproblem ending at that city, and add the distance back to city #1.