<p>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.</p>

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

<p>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. </p>

<p>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 <a href="http://www2.research.att.com/~dsj/chtsp/index.html" rel="nofollow">here</a> for some good heuristics. Bill Cook's <a href="http://www.tsp.gatech.edu/concorde.html" rel="nofollow">Concorde</a> 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. </p>

CC BY-SA 3.0
2012-10-22T16:39:18.757Z
So it's not clear to me how you came up with $\theta(\sqrt{{pq}/k})$ as the average edge length. Can you please clarify it?
Javad
CC BY-SA 3.0
2012-10-22T22:44:27.950Z
I have had quite a bit of experience with TSP-type problems. You have to know that for random points in $d$-space (the metric doesn't matter, because the distance in different metrics only differs by a constant factor), the average edge length is a constant factor larger than the expected distance from a point to its nearest neighbor. Now, if you have $k$ points in a $p\times q$ rectangle, and they are evenly spaced, each point gets area $\theta(pq/k)$. Take the square root of that.
Peter Shor 
CC BY-SA 3.0
2012-10-09T07:24:25.673Z
Using the terminology from [TSPLIB](http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/), 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.
Javad
CC BY-SA 3.0
2012-10-09T07:26:00.443Z
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.
Javad
CC BY-SA 3.0
2012-10-09T07:27:18.883Z
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$?
Javad
CC BY-SA 3.0
2012-10-09T13:07:28.467Z
@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)$.
Peter Shor 
CC BY-SA 3.0
2012-10-09T13:16:14.510Z
For $k \approx 10^6$, the difference between the TSP length and the SOP length should be nearly negligible.
Peter Shor 
CC BY-SA 3.0
2012-10-09T18:02:56.647Z
A $p\times q$ grid has $(p+1)q+p(q+1)$ unit length edges including the boundary edges. So, the coefficient should be $\sqrt {((p+1)q+p(q+1))k}$. Am I right?
Javad
CC BY-SA 3.0
2012-10-09T18:04:39.933Z
@javad: maybe, but $\sqrt{((p+1)q+p(q+1)k} \approx \sqrt{2 pqk}$, and the 2 can be absorbed by the function $f$, so to first order it doesn't matter.
Peter Shor 
CC BY-SA 3.0
2012-10-09T18:15:28.970Z
You're right. I have two more concerns: First, you suggested to estimate $f$ and $g$ using small values of $p$ and $q$. Using small $p$'s and $q$'s, difference between TSP and SOP would not be negligible. The second concern is that I am also interested to have a close form expression for smaller $p$'s and $q$'s. Do you propose the same expression for this range as well? Do you know any good SOP solver?
Javad
CC BY-SA 3.0
2012-10-15T19:29:34.930Z
@javad: I don't have any better expression for smaller $p$'s and $q$'s, even though this expression won't be as good an approximation.
Peter Shor 
CC BY-SA 3.0
2012-10-22T07:27:55.397Z
I guess you assumed that this problem is dealing with Euclidean distances. Then you calculated the average edge length as $\theta(\sqrt{{pq}/k})$. Though, this problem is formulated based on Manhattan distance, hence I think the correct coefficient should be ${pq}/k\times k=pq$. Is it true?
Javad
CC BY-SA 3.0
2012-10-22T12:59:03.270Z
@Javad: no, that's wrong. The difference between Manhattan and Euclidean distance is only a constant, and so can be absorbed into the $\theta$.
Peter Shor 
CC BY-SA 3.0
2012-10-08T17:37:38.753Z
2012-10-09T13:08:13.863Z
2012-10-09T13:08:13.863Z
Peter Shor 
<p>$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.</p>

<p>I am looking for an efficient way to calculate the <em>expected length</em> of the shortest (minimum total weight) hamiltonian path passing through these $k$ nodes. More precisely, the following naive approaches are not desired:</p>

<p>$\bullet$ Calculating the exact path length for all combinations of k nodes and deriving the expected length.</p>

<p>$\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)</p>

CC BY-SA 3.0
2012-10-08T08:20:50.633Z
Currently, there is no hope for efficient algorithm since unweighted  Hamiltonian path problem on planar grid is NP-complete.
Mohammad Al-Turkistany
CC BY-SA 3.0
2012-10-08T12:17:17.887Z
When you speak of hamiltonian path, are you thiking about the hamiltonian path with smallest weight (aka. the travelling salesman problem)?
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2012-10-08T16:02:36.857Z
@MohammadAl-Turkistany the hardness of HAM PATH is not necessarily an obstacle, since the OP merely an estimate for random points.
Suresh Venkat
CC BY-SA 3.0
2012-10-08T16:03:54.360Z
@a3nm yes, and I fixed it.
Suresh Venkat
CC BY-SA 3.0
2012-10-08T16:41:25.983Z
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?
Peter Shor 
CC BY-SA 3.0
2012-10-08T16:51:22.383Z
Maybe the OP is also asking if anything is known analytically ?
Suresh Venkat
CC BY-SA 3.0
2012-10-08T17:08:04.250Z
@MohammadAl-Turkistany as Suresh Venket stated, this problem is different than TSP for planar graphs as I am looking for the expected length unless you offer a transformation for this problem to convert it to TSP and show that it is NP-hard.
Javad
CC BY-SA 3.0
2012-10-08T17:08:50.440Z
@SureshVenkat & a3nm: I am looking for the path not the tour. Even having the expected TSP (traveling sales person) length is helpful, because we can multiply it by (k-1)/k to find the desired answer.
Javad
CC BY-SA 3.0
2012-10-08T17:10:18.817Z
$k,p$ and $q$ are all more than $10^6$. So an efficient approach is desired.
Javad
CC BY-SA 3.0
2012-10-08T17:12:00.250Z
@Suresh Venkat I did not quite understand your last question.
Javad
CC BY-SA 3.0
2012-10-08T17:14:29.890Z
@Javad are you also potentially looking for a closed form expression ? sometimes this might exist (for example for uniformly sampling from the unit square)
Suresh Venkat
CC BY-SA 3.0
2012-10-08T17:37:37.783Z
@SureshVenkat In [wikipedia](http://en.wikipedia.org/wiki/Travelling_salesman_problem#TSP_path_length_for_random_pointset_in_a_square), good approximations for lower bound and upper bounds are given. Although there are two issues with these values:
1- The location of points are not integer.
2- Euclidean distance is assumed instead of Manhattan distance.

Do you know any better close form expression?
Javad
<graph-theory><co.combinatorics><planar-graphs><hamiltonian-paths>
What's the expected length of the shortest hamiltonian path on a randomly selected points from a planar grid?
Javad
# What's the expected length of the shortest hamiltonian path on a randomly selected points from a planar grid?

(Asked by: username_0 on 2012-10-08)

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

**Tags:** graph-theory, co.combinatorics, planar-graphs, hamiltonian-paths
> **Comments:**
> **username_1**: Currently, there is no hope for efficient algorithm since unweighted  Hamiltonian path problem on planar grid is NP-complete.  
> **username_2**: When you speak of hamiltonian path, are you thiking about the hamiltonian path with smallest weight (aka. the travelling salesman problem)?  
> **username_3**: @MohammadAl-Turkistany the hardness of HAM PATH is not necessarily an obstacle, since the OP merely an estimate for random points.  
> **username_3**: @a3nm yes, and I fixed it.  
> **username_4**: 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?  
> **username_3**: Maybe the OP is also asking if anything is known analytically ?  
> **username_0**: @MohammadAl-Turkistany as Suresh Venket stated, this problem is different than TSP for planar graphs as I am looking for the expected length unless you offer a transformation for this problem to convert it to TSP and show that it is NP-hard.  
> **username_0**: @SureshVenkat & a3nm: I am looking for the path not the tour. Even having the expected TSP (traveling sales person) length is helpful, because we can multiply it by (k-1)/k to find the desired answer.  
> **username_0**: $k,p$ and $q$ are all more than $10^6$. So an efficient approach is desired.  
> **username_0**: @Suresh Venkat I did not quite understand your last question.  
> **username_3**: @Javad are you also potentially looking for a closed form expression ? sometimes this might exist (for example for uniformly sampling from the unit square)  
> **username_0**: @SureshVenkat In [wikipedia](http://en.wikipedia.org/wiki/Travelling_salesman_problem#TSP_path_length_for_random_pointset_in_a_square), good approximations for lower bound and upper bounds are given. Although there are two issues with these values: 1- The location of points are not integer. 2- Euclidean distance is assumed instead of Manhattan distance.  Do you know any better close form expression?  

---

## 1 answers

### Answer by username_4 on 2012-10-08. Score: 6

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](http://www2.research.att.com/~dsj/chtsp/index.html) for some good heuristics. Bill Cook's [Concorde](http://www.tsp.gatech.edu/concorde.html) 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.

> **Comments:**
> **username_0**: Using the terminology from [TSPLIB](http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/), 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.  
> **username_0**: 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.  
> **username_0**: 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$?  
> **username_4**: @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)$.  
> **username_4**: For $k \approx 10^6$, the difference between the TSP length and the SOP length should be nearly negligible.  
> **username_0**: A $p\times q$ grid has $(p+1)q+p(q+1)$ unit length edges including the boundary edges. So, the coefficient should be $\sqrt {((p+1)q+p(q+1))k}$. Am I right?  
> **username_4**: @javad: maybe, but $\sqrt{((p+1)q+p(q+1)k} \approx \sqrt{2 pqk}$, and the 2 can be absorbed by the function $f$, so to first order it doesn't matter.  
> **username_0**: You're right. I have two more concerns: First, you suggested to estimate $f$ and $g$ using small values of $p$ and $q$. Using small $p$'s and $q$'s, difference between TSP and SOP would not be negligible. The second concern is that I am also interested to have a close form expression for smaller $p$'s and $q$'s. Do you propose the same expression for this range as well? Do you know any good SOP solver?  
> **username_4**: @javad: I don't have any better expression for smaller $p$'s and $q$'s, even though this expression won't be as good an approximation.  
> **username_0**: I guess you assumed that this problem is dealing with Euclidean distances. Then you calculated the average edge length as $\theta(\sqrt{{pq}/k})$. Though, this problem is formulated based on Manhattan distance, hence I think the correct coefficient should be ${pq}/k\times k=pq$. Is it true?  
> **username_4**: @Javad: no, that's wrong. The difference between Manhattan and Euclidean distance is only a constant, and so can be absorbed into the $\theta$.  
> **username_0**: So it's not clear to me how you came up with $\theta(\sqrt{{pq}/k})$ as the average edge length. Can you please clarify it?  
> **username_4**: I have had quite a bit of experience with TSP-type problems. You have to know that for random points in $d$-space (the metric doesn't matter, because the distance in different metrics only differs by a constant factor), the average edge length is a constant factor larger than the expected distance from a point to its nearest neighbor. Now, if you have $k$ points in a $p\times q$ rectangle, and they are evenly spaced, each point gets area $\theta(pq/k)$. Take the square root of that.  

---

