  If one places N cities randomly on a lattice of size L, we find that the
normalized optimal travel distances per city in the Euclidean and Manhattan
metrics vary monotonically with the city concentration p. We have studied such
optimal tours for visiting all the cities using a branch and bound algorithm,
giving exact optimized tours for small system sizes (N<100). Extrapolating the
results for N tending to infinity, we find that the normalized optimal travel
distances per city in the Euclidean and Manhattan metrics both equal unity for
p=1, and they reduce to about 0.74 and 0.94, respectively, as p tends to zero.
Although the problem is trivial for p=1, it certainly reduces to the standard
TSP on continuum (NP-hard problem) for p tending to zero. We did not observe
any irregular behaviour at any intermediate point. The crossover from the
triviality to the NP-hard problem seems to occur at p=1.
