To a human, reading a map to find a path from one point to another is very intuitive. To a computer, this task is more complicated. A computer cant just look and see what may be very obvious from a casual glance. The computer can either look at all possible paths or make an educated guess about which paths might be best. Both network routing and GPS based route mapping rely on computers being able to quickly and effectively assess routes even in dynamic circumstances.

Consider question 33 in Section 6.4 ((How many bit strings of length n, where n 4, contain exactly two occurences of 01 )))of the text. In it, even a simple network with strict travel rules (up and right only) produces many possible paths. In network or GPS map routing, the network is much more complex, and data or vehicles are allowed to travel any direction. A huge, complex mesh arises in which it is impossible to consider all possible routes.

Think first of a network of roads for GPS mapping. Every road whether in a neighborhood or spanning states is included in possible paths. A dirt road is included in the overall network just like a major highway. Clearly, it is impossible to consider every possible path in every GPS mapping decision. If traveling from your house to the nearest grocery store, it is absurd to consider paths that go through another city 800 miles away. If driving from the Empire State building in New York City to the Golden Gate Bridge in San Francisco, a dirt road in Iowa might be close to on the way but doesnt need to be considered as a path.

The Internet is similar to that mesh of roads with connections ranging from local cable lines to submarine optical cables traversing thousands of kilometers. Just like with the roads, not all possible paths in the network need to be considered for every packet route.

Consider methods to narrow down these paths for GPS mapping or mesh network routing. What strategies and processes might be applied to have a computer algorithmically do what a person glancing at a map does naturally?

For this Discussion:

Choose either the GPS map routing or the Internet routing. Describe an algorithm for quickly determining the best path to take within such a broad mesh. Provide an example to show how the algorithmic process would determine a specific route for an automobile or data packet.