9
$\begingroup$

$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)

Improve this question
$\endgroup$
12
  • $\begingroup$ Currently, there is no hope for efficient algorithm since unweighted Hamiltonian path problem on planar grid is NP-complete. $\endgroup$
    – Mohammad Al-Turkistany
    Oct 8, 2012 at 8:20
  • $\begingroup$ When you speak of hamiltonian path, are you thiking about the hamiltonian path with smallest weight (aka. the travelling salesman problem)? $\endgroup$
    – a3nm
    Oct 8, 2012 at 12:17
  • $\begingroup$ @MohammadAl-Turkistany the hardness of HAM PATH is not necessarily an obstacle, since the OP merely an estimate for random points. $\endgroup$
    – Suresh Venkat
    Oct 8, 2012 at 16:02
  • $\begingroup$ @a3nm yes, and I fixed it. $\endgroup$
    – Suresh Venkat
    Oct 8, 2012 at 16:03
  • $\begingroup$ What is wrong with computing the exact tour length for many random samples of $k$ points, and finding the expectation and standard deviation? How big do you need $k, p, q$ to be? $\endgroup$
    – Peter Shor
    Oct 8, 2012 at 16:41

1 Answer 1

Reset to default
6
$\begingroup$

Assuming that $p$ and $q$ are fairly large, one would expect that the expected length would mainly depend on the density, with some correction term depending on the perimeter. So it would, to first order, be a function of the following form.

$$ L \approx (pqk)^{1/2} f(k/pq) + (p+q) g(k/pq).$$

Now, you could use experiments on smaller-size problems to figure out what $f$ and $g$ are. First, to estimate $f$, you want to do experiments on a sample without a boundary: the easiest way to do this is to use a $p\times p$ grid with the left side connected to the right and the top to the bottom, forming a torus. To estimate $g$, you can use experiments on a $p \times q$ grid.

For estimation, you need to solve (exactly or approximately) relatively large TSPs, since the larger the ones you use for the estimation, the better your results will be. You could either use heuristics that come within a few percent, or exact TSP code. See here for some good heuristics. Bill Cook's Concorde TSP solver will find the exact optimum for reasonably large instances (it's the best TSP code available), and can be used without charge for academic research.

Improve this answer
$\endgroup$
13
  • $\begingroup$ Using the terminology from TSPLIB, I was looking for SOP not TSP. Multiplying the $E[L]$ calculated for TSP by $(k-1)/k$ gives an upper bound for SOP. Unfortunately, Concorde TSP solver does not handle SOPs and I could not find any SOP solver online. $\endgroup$
    – Javad
    Oct 9, 2012 at 7:24
  • $\begingroup$ I guess for calculating $E[L]$, the cases which have larger $L$'s and smaller $L$'s are equally distributed around $E[L]$, so one may come up with a constructive approach to find an arrangement of $k$ points in the grid which (maybe approximately) gives $E[L]$. Finding such arrangement would obviously dramatically decrease the cost of computation. $\endgroup$
    – Javad
    Oct 9, 2012 at 7:26
  • $\begingroup$ I also did not quite understand the reason for the coefficient $k^2$. Why shouldn't it be $k^2/(pq)$? How does this approximation formulation change for smaller values of $p$ and $q$? $\endgroup$
    – Javad
    Oct 9, 2012 at 7:27
  • $\begingroup$ @Javad: Good question. I was wrong, because I somehow was thinking $k^2$ points when I wrote my answer. The coefficient comes from my assumption that the $p\times q$ grid has unit length edges, so the whole region is size $p \times q$. The average edge should be of length $\theta(\sqrt{pq/k})$, and there are $k$ edges, so if you want $f$ to stay roughly constant, the first term should be $\sqrt{pqk} f(k/pq)$. $\endgroup$
    – Peter Shor
    Oct 9, 2012 at 13:07
  • $\begingroup$ For $k \approx 10^6$, the difference between the TSP length and the SOP length should be nearly negligible. $\endgroup$
    – Peter Shor
    Oct 9, 2012 at 13:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.