Given a connected road network on an Island without one-way streets, where should I para-shoot in and what route should I take to deliver mail to all houses on the island (being picked up again by helicopter)?
Or in terms of Graphs: Given an un-directed, connected, weighted Graph, what is the optimal start vertex and shortest path that visits every edge at least once (return to the start vertex not required)?
This question is an altered version of the Route Inspection Problem or Chinese postman problem.
The solution I have working is O(n^5) and I'm trying to improve this.
A Slow-ish Solution
- First we need to change the graph so that an Eulerian Path exists. We can do this by finding the Minimum Weight, Perfect Matching between all odd vertices (removing two odd vertices since we want a Path and not a Cycle!)
- We can use Edmonds' Blossom Algorithm to make the Matching computation efficient. My implementation is currently
O(n^3) - Adding the computed edges into the Graph ensures an Eulerian Path exists (using the two skipped Vertices as start and end point)
- We then compute the Eulerian Path and have an optimal solution for the chosen start and end vertex
Question:
The big questions is which two odd vertices to use as the start and end point for the Eulerian Path. So far I am computing all possible Matchings using the Blossom algorithm and taking the one with the minimum weight.
Is there a way that we can do this better? Potentially already integrating it into the Blossom algorithm? Are there any assumptions we can make about the vertices that are optimal? I.e. in a lot of cases two odd vertices with largest distance in the original graph are the best choice, however this is not always true (see Example 3).
How can we adjust e.g. this implementation to consider only Matchings of maximum size - 1?
Example 1
Here is the optimal solution for a maze (the coloring indicates the chosen path). The computation for a given start-end vertex pair is relatively fast (around 100ms). However since this needs to happen for every odd-vertex pair, the overall computation time is over an hour.
There are 278 odd vertices in the maze. Hence we have to compute a Matching (278 * (278 - 1)) / 2 = 38503 times.
Example 2
In this example it is obvious that the optimal start and end points are very far apart.
Example 3
The maximal distance between two odd Vertices (the one at the top and the one at the bottom) is 50. However for the optimal path the distance is only 11.
PS: Had all the terms nicely linked in the question, but can only include two links due to not having reputation. Oh well...
