$k$ distinct points are selected randomly from a $p\times q$ grid. (Obviously $k\leq p\times q$ and is a given constant number.) A complete weighted graph is built from these $k$ points such that weight of the edge between vertex $i$ and vertex $j$ equals the Manhattan distance of two vertices on the original grid.
I am looking for an efficient way to calculate the expected length of the shortest (minimum total weight) hamiltonian path passing through these $k$ nodes. More precisely, the following naive approaches are not desired:
$\bullet$ Calculating the exact path length for all combinations of k nodes and deriving the expected length.
$\bullet$ Calculating the approximated path length for all combinations of k nodes using the basic heuristic of using minimum spanning tree which gives up to 50% error. (A better heuristic with less error may be helpful)