Previous Topic

Next Topic

CHINESE POSTMAN PROBLEM

The Chinese Postman Problem is an example of a problem in discrete mathematics and graph theory.  The problem is thought to have originated from an old Chinese puzzle involving a postman.  In this puzzle, a postman has to go through many streets to deliver letters and wishes to do it in the shortest distance possible.

In mathematical language, it is a problem in graph theory which seeks to find the minimum length closed walk that traverses each edge at least once. Finding an optimal solution in a graph with both directed and undirected edges is NP-complete.

The Chinese Postman Problem may also got its name because it was proposed by Mei-Ko Kwan, a Chinese mathematician, in 1962.  An alternative and more modern name is “Route Inspection Problem”.
 

Previous Topic

Next Topic