How do maps (like on Google or Mapquest) know exactly where a house is and are able to give driving directions

How do maps (like on Google or Mapquest) know exactly where a house is and are able to give driving directions to/from it?|||How does mapquest know where a house is?





Simple answer, they guess. Thats right, they guess. Mapquest has an algorithm called Geocoding which uses the US post office data (for US maps) to guess (quire accurately typically) the latitude and longitude of the address you specify. Geocoding takes the address and compares it to the number of addresses the US post office says is on the current block, and guesses based upon how many addresses there are and the address supplied. For example, suppose you ask for 135 Main St. Now mapquest looks up the info it has for Main St as it is supplied by the US post office, which consists of the address on the end of the block (have you ever seen the signs that say "400" on a street sign?). Now suppose that 135 Main lies on the block that starts at 100 Main and ends at 400 Main. This means there are 300 addresses on this block. Each address is assumed to take 1/300th of the street space. Thus 135 Main will lie 35/300th's of the distance from the 100 end of the block to the other side of the block. Mapquest knows the latitude and longitude of the intersections and computes the lat/long of the address using these numbers. Further explanation here: http://www.mapquest.com/features/main.ad鈥?/a>





How is mapquest able to give driving directions?





Again, they guess. They have very good ways of guessing, but without a massive amount of computation it is not possible to give a perfect answer. Typically the method used for such driving directions is an example of something called a "greedy algorithm". I would hazard a guess that they actually use a form of an A* ("A Star") algorithm, but the technicalities are not important. Basically the algorithm takes a location and looks at all possible directions a person can go if they are at a specified location and chooses the direction which gets the person closer to their goal. They call this a "greedy" algorithm because it continually tries to get closer to the goal. Typically this type of search arrives at the best solution. Other considerations such as travel time are taken into consideration in the real calculations.


For more information on greedy algorithms:


http://www.personal.kent.edu/.../greedyI鈥?/a>


http://en.wikipedia.org/wiki/Greedy_algo鈥?/a>





I hope this answers your question without being to technical.|||GPS Dee Dee Dee