Finding Grandma's Car - a word problem 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!
 A: The problem is equivalent to the traveling salesman problem. We can visualize this with a 3x3 version:

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.
A: 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
