Chinese Postman Problem
The Chinese postman problem is a mathematical problem of Graph theory. It is also known as route inspection problem. Suppose there is a mailman who needs to deliver mail to a certain neighborhood. The mailman is unwilling to walk far, so he wants to find the shortest route through the neighborhood, that meets the following criteria:
- It is a closed circuit (it ends at the same point it starts).
- He needs to go through every street at least once.
If the graph traveled has an Eulerian Circuit, this circuit is the ideal solution.
Best explained: http://www.youtube.com/watch?v=fke5x0rmhpA
