I am studying the euclidian version of the Travelling Sales Man problem:
Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city, where the direct connection from city A to city B is never farther than the route via intermediate city C.
And I wonder:
Is it possible to make the number of cities on the list have no influence on the average/estimated time it will take to find a solution? For example, to modify the rules that with 10 cities that you require 4 cities in the path, and with a million cities, that you require 400 cities in the path. So that each list will take about the same time to solve, no matter its length?