Send the link below via email or IMCopy
Present to your audienceStart remote presentation
- Invited audience members will follow you as you navigate and present
- People invited to a presentation do not need a Prezi account
- This link expires 10 minutes after you close the presentation
- A maximum of 30 users can follow your presentation
- Learn more about this feature in our knowledge base article
The Chinese Postman Problem
Transcript of The Chinese Postman Problem
-Routing problems are concerned with finding ways to route the delivery of goods or services to an assortment of destinations; like mail or garbage collection.
-A weighted graph is a graph in which the edges are assigned positive numbers called weights. The weights can represent distances, times, or costs.
-The Chinese postman problem is the problem of finding a trip that covers all the edges of a weighted graph and that is optimal.
-These problems are a generalization of Euler Circuit problems.
So this is an example of the simplest case of the Chinese Postman Problem. The simplest case occurs when every vertex in the graph has even degree, in this case an Euler circuit solves the problem because any Euler circuit will have the minimum total weight because no edges need to be retraced.
-When solving a Chinese Postman Problem it is important that if there are many possible routes, to figure out which one is the best. The best route is the one that is either the quickest, most efficient, or cheapest depending on what the weights represent.
-Ask which route is the best in terms of cost, distance, or time.
-There could be a road network which must be traveled by a mail carrier delivering mail to buildings along the streets, a snowplow which must clear snow from each lane of the streets, a highway department crew which must maintain each street, a police patrol car which makes its rounds through all streets several times a day.
-In each case, the person or vehicle must travel each street at least once. In the best situation, where every road intersection (i.e. vertex) has even degree, no retracing is needed. In such a case, any Euler Circuit solves the problem.
-But it is rarely the case that every vertex in a road network is even.
-Euler's theorem proves that when there are
vertices, it is impossible to plan a circuit that goes through every edge exactly once.
-Since every road needs to be traced, some roads must be retraced.
-So this is
The Chinese Postman Problem: plan a route so that the total amount of retracing is as small as possible.
Hannah Amado, Lacey Wilson, Taylor Stewart
The Chinese Postman Problem
A mail carrier has to deliver mail to all streets in a subdivision. The mail carrier has to start and end at point A, where the post office is. The weight of each edge represents the length of each street. What is the most efficient route for the mail carrier?
A mail carrier has to start at A, walk along all 13 streets and return to A. The weight on each edge is the length of each street. Find a route that uses all the edges of the graph and that is most efficient.
Chinese Postman Algorithm
List all odd vertices.
List all possible pairings of odd vertices.
For each pairing find the edges that connect the
vertices with the minimum weight.
Find the pairings such that the sum of the weights is minimised.
On the original graph add the edges that have been found in Step 4.
The length of an optimal Chinese postman route is the sum of all the edges added to the total found in Step 4.
A route corresponding to this minimum weight
can then be easily found.
The odd vertices are A and H
There is only one way of pairing these odd vertices, namely AH
The shortest way of joining A to H is using the path AB, BF, FH, a total length of 160.
Draw these edges onto the graph
The length of the optimal Chinese postman route is the sum of all the edges in the original graph, which is 840, plus the answer found in step 4, which is 160. So the length is 1000.
One possible route corresponding to this length is ADCGHCABDFBEFHFBA, but many other possible routes of the same minimum length can be found.