1
$\begingroup$

TL;DR: What's the minimum distance one has to travel to visit each node in a square matrix in which the nodes are D distance apart?

I ask because I'm working on a fun feature on how long it takes Santa to reach every child in the country, using a Travelling Salesman algorithm to map his route through the counties. But I need to estimate how long he needs to spend in each county.

For each county, we know:

Given that this is mostly an exercise in TSP, I don't need a deeply precise value here. (We don't know how many children live in the same household or the specific population density of each county.) So I'm assuming the children are roughly evenly distributed across 50% of the county's land mass.

The question is: How do I approximate the time it takes to reach each node in an arbitrary amount of space, assuming those nodes are neatly positioned? (After all, we can't run a TSP for each of the 3,000+ counties as well, even if we had everyone's address!)

My best guess is to imagine the N nodes arranged in a square matrix. Then, the distance between two nodes is sqrt(area * 0.5) / sqrt(N)--I think. Then you imagine that you (Santa) has to travel to each node. I think this is just N steps since it's a neat square martix, unless I'm deeply miscalculating the number of edges in a square matrix. Thus, I came up with:

sqrt(area * 0.5) / sqrt(N) * N

Unfortunately, it's difficult to fact-check this sort of calculation since it's imaginary!

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

If you have $N$ nodes in a square matrix it takes $N-1$ times the distance between neighboring nodes to visit them all. You can't get from one to another in less distance and a snaking path will keep you at that minimum. Your grid is $\sqrt N \times \sqrt N$ so the area is $N$ times the square of the spacing, which gives the distance between as $\sqrt{\frac {area}N}$ and total travel of $\sqrt{N \cdot area}$

$\endgroup$
2
  • $\begingroup$ Thanks! My only confusion is why sqrt(area/N) * (N-1) isn't equal to sqrt(N * area). $\endgroup$
    – Chris Wilson
    Dec 19, 2017 at 16:44
  • $\begingroup$ The $-1$s are a pain. The area should really be $(\sqrt N-1)^2$ because of the fencepost problem. It is easiest to ignore them because $N$ is much larger. If you ignore the $-1$ they are equal. $\endgroup$
    – Ross Millikan
    Dec 19, 2017 at 16:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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