This word problem came up in a lunchtime discussion with coworkers. None of us are professional mathematicians or teachers of math, and we weren't sure how to get the answer. The word problem goes like this:

Grandma Q drove her car downtown to do some shopping and parked it at a random spot on the street. While shopping she forgot where she parked and called me on her cell phone asking how to find her car.

The downtown is a 10x10 set of square city blocks in a regular grid pattern. The car could be on any one of the streets of this grid, including the outside edges, between two intersections.

Grandma Q can see both sides of the street so she only has to walk one time between any two intersections to search for her car. However she can only see cars on the street she is on between the two intersections she is walking (i.e. she can't look down to the next block or from an intersection to the four blocks it connects).

Because she is elderly and gets tired easily (but not while shopping apparently), I don't want to have her walk where she has already searched, and I want to get to the car as quickly as possible.

Is there a mathematical way to determine the most efficient (minimum time, minimum retracing) search pattern for Grandma Q? Is there more than one solution? Does it matter where she starts (center, edge, corner, random)? Can the answer be scaled to any x-by-x square or x-by-y rectangle?

(we weren't sure which branch of math most effectively deals with this kind of problem, so if someone could tell me, that would be great too.)

Thank you!

  • $\begingroup$ Sounds like graph theory and a bit of optimization too...but I might be wrong. $\endgroup$ – Ataraxia Aug 2 '13 at 2:33
  • 3
    $\begingroup$ You're looking for the shortest path which visits every edge on the $10\times10$ grid graph. Unfortunately, this graph isn't Eulerian, so some amount of retracing is inevitable. $\endgroup$ – Rahul Aug 2 '13 at 2:40
  • 2
    $\begingroup$ The Chinese postman problem asks for the path with the best worst-case behavior. $\endgroup$ – Chris Culter Aug 2 '13 at 2:56
  • $\begingroup$ @RahulNarain: Well, it's not exactly the same as finding a fast way to enumerate ALL nodes of a graph. It's more of a search problem, because the order of searching the graph matters (on average, we don't expect to exhaust the graph because we terminate when the car is found). In fact, you may be able to construct good heuristics to solve practical instances of the search problem (which are not available in the "iterate through all nodes" perspective). $\endgroup$ – pre-kidney Aug 2 '13 at 3:00
  • $\begingroup$ yes, i agree that some retracing is necessary, and i want to minimize it as much as possible. $\endgroup$ – SteveED Aug 2 '13 at 3:20

The problem is equivalent to the traveling salesman problem. We can visualize this with a 3x3 version:

enter image description here

Here the intersections are circles and are connected by a line. Draw something like the dual of the graph, i.e. on each edge place a new vertex (marked by an X) and connect those vertices if you could get from one street to another (blue line). Your problem really isn't about the intersections (circles), but about streets themselves (x's).

Each blue line has a weight, the cost of going from one street to another. On a uniform city block all the weights are unity. We now have the traveling salesman problem since we want to find the shortest route that visits every (X) vertex at least once.

In general this problem is NP-complete, meaning it is (probably) quite difficult to solve exactly. However, our graph has symmetry and structure that may be worth exploiting. There are also approximate algorithms that do good job much more quickly. In addition, the computational cost might be worth if Grandma gets lost in the same city all since the underlying graph (and hence the solution) would be the same.

  • 1
    $\begingroup$ Exactly the approach I was thinking about last night! $\endgroup$ – Emily Aug 2 '13 at 18:51
  • 3
    $\begingroup$ Paths on the "dual" graph (actually known as the line graph) do not correspond to paths on the original graph. Consider this. $\endgroup$ – Rahul Aug 3 '13 at 0:56
  • $\begingroup$ wow! this is very interesting, i had no idea we were that deep! Thank you very much! $\endgroup$ – SteveED Aug 3 '13 at 3:07
  • $\begingroup$ s/equivalent/a special case of. This answer is actually much less complete than it appears. $\endgroup$ – djechlin Jan 2 '15 at 17:44

Since the problem boils down to performing a fast search, I would consider this a computer science problem. You can think of the cars as being values stored in nodes of a graph, and you are looking for a path that stumbles near a node with the requested value.

See for instance https://en.wikipedia.org/wiki/Graph_search_algorithm

  • 1
    $\begingroup$ Your link is not helpful: finding a path is completely different from graph traversal. Grandma cannot explore downtown in a breadth-first manner. $\endgroup$ – Rahul Aug 2 '13 at 8:11

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.