Chinese Postman or Route Inspection problem

The Chinese Postman or Route Inspection Problem is a type of Eulerian circuit problem that finds the shortest closed path in an undirected graph such that every edge is visited at least once. This problem is also very relevant in cases when a postman needs to deliver mail to every street in a city and the aim is to find the most optimal route covering each street at least once.

Route Inspection Problems

Closest path traversing all the nodes of the network is obtained via network inspection.

What is the purpose of the Route Inspection Problem?

The purpose of the Chinese postman problem, also named the postman tour is to find the minimal closed tour that completely traverses all the edges of the undirected (connected) graph.

Problem Statement:

Given an undirected graph, the task is to find the shortest cyclic path that visits all vertices or edges at least once.

Algorithm:

Chinese Postman Algorithm:

1. Input:
   • Read n (number vertices) and m (number of edges).
   • Set up the adjacency matrix a, distance matrix d and degree array deg.
   • Sum is initially 0.
2. Graph Initialization:
   • Set all entries of the matrix a to infinity (INF).
   • For each edge (x, y, c):
   • For each edge (x, y, c):
   • x and y are to be decremented 1 (for 0-based indexing).
   • Updating a[x][y] and a[y][x] by taking the minimum of the latter and equal to c.
   • Increment deg[x] as well as deg[y] by 1.
3. Depth-First Search (DFS):
   • Set a boolean stitched array mark that tracks of the visited vertices.
   • Start DFS by calling dfs(0) for depth-first search of vertex 0.
   • Check if anyone of the vertex has not been visited (mark[i] > 0) and has positive degree (degree[i] > 0). If true, the denied will be true.
4. Graph Connectivity Check:
   • If this is bad - output -1 and exit, otherwise continue.
5. Floyd-Warshall Algorithm:
   • Echo matrix a to matrix d.
   • Utilize the Floyd Warshall algorithm to find the shortest distances between every pair vertex in d-matrix.
6. Memorization Initialization:
   • Initiate a mem array of length 2^15 in which all holders have been set to -1.
7. Dynamic Programming (Recursion):
   • Defining a recursive function rec(mask) to find the best path cost.
   • Apply memorization to store and recall those that have been pre-computed.
8. Construct Initial Mask:
   • Start with a mask of odd-degree vertices (mask |= (1 <<i) for i& |mask.
9. Calculate Result:
   • Calculate the result that equals the sum of the original and rec(mask) outcomes.
10. Output:
    • Print the result on the final sheet.

Code Implementation(Java):

Explanation:

1. Input Handling: The code receives n and m as inputs which are the number of vertices and number of edges, respectively and then initializes the arrays of the adjacency matrix a, distances matrix d and the arrays deg and mark.
2. Edge Input: The code processes edges and their costs, qualitatively updating the adjacency matrix a and calculating the final cost.
3. DFS to Check Connectivity: This uses DFS (Depth-First Search) to determine whether graph is connected or not. If None of the vertex are ticked and has positive degree, the graph is not connected.
4. Floyd-Warshall Algorithm: The Floyd-Warshall algo is used to find out how long between all the vertex-pairs and that value is kept in the matrix d.
5. Dynamic Programming with Bitmask (DP): The bitmask technique in DP computation is applied to find the cheapest route which means that the visited vertices can be recorded.
6. Output: And now we determine the result that is the sum of all the costs and the minimal value of the DP function. If the orgraph is not connected, -1 is returned.

Time Complexity:

• The DFS is done once on the graph (and this takes O(n + m) time with n being the number of vertices, and m being the number of edges).
• The Floyd-Warshall algorithm written with nested loops has the time complexity of O(n^3), where n is the number of vertices.
• The function rec is memoized using the dynamic programming technique and with bitmask states In the most complex case, there are at most 2^n states, and the recurrence relation is computed for every state. Consequently, the time complexity of the DP part becomes O(2^n * n^2).
• The main factor is the dynamic programming part, hence the overall time complexity in the order of O(2^n * n^2).

Space Complexity:

• The adjacency matrix a and the distance matrix d both will take O(n^2) space, where n is the number of vertices.
• The space complexity is O(n) of storing the deg array, the mark array and the mem array.
• The space complexity of input variables, temporary variables and loop indices is O(1 ).
• The most implication is the space used for matrices, so complexity overall is O(n^2).

Applications:

Network optimization, vehicle routing, and circuit design are a few applications of the Chinese Postman Problem beyond mail delivery. The solving of this problem gives information for making an efficient transportation route for various real life situations where all edges have to be covered and resources have to be used effectively.

Conclusion:

The Graph coloring Algorithm is based on the Chinese Postman or Route Inspection Problem. The main objective of this problem is to find the shortest cyclic path which visits all the edges of an undirected graph at least once. This issue arises in cases like constructing mail delivery routes or network inspection.