Chinese postman problem
Finding shortest walks through all graph edges
Chinese postman problem
In graph theory and combinatorial optimization, Guan's route problem, the Chinese postman problem, postman tour or route inspection problem is to find a shortest closed path or circuit that visits every edge of an (connected) undirected graph at least once. When the graph has an Eulerian circuit (a closed walk that covers every edge once), that circuit is an optimal solution. Otherwise, the optimization problem is to find the smallest number of graph edges to duplicate (or the subset of edges with the minimum possible total weight) so that the resulting multigraph does have an Eulerian circuit. It can be solved in polynomial time, unlike the Travelling Salesman Problem which is NP-hard. It is different from the Travelling Salesman Problem in that the travelling salesman cannot repeat visited nodes and does not have to visit every edge. The problem was originally studied by the Chinese mathematician Meigu Guan in 1960, whose Chinese paper was translated into English in 1962. The original...
Read on Wikipedia · Image Cmglee, CC BY-SA 4.0
Open boosters, collect cards and trade them. Free to play.
Play for free