How should I generate the partitions / pairs for the Chinese Postman problem?
- by Simucal
I'm working on a program for class that involves solving the Chinese Postman problem. Our assignment only requires us to write a program to solve it for a hard-coded graph but I'm attempting to solve it for the general case on my own.
The part that is giving me trouble is generating the partitions of pairings for the odd vertices.
For example, if I had the following labeled odd verticies in a graph:
1 2 3 4 5 6
I need to find all the possible pairings / partitions I can make with these vertices.
I've figured out I'll have i paritions given:
n = num of odd verticies
k = n / 2
i = ((2k)(2k-1)(2k-2)...(k+1))/2
So, given the 6 odd verticies above, we will know that we need to generate i = 15 partitions.
The 15 partions would look like:
1 2 3 4 5 6
1 2 3 5 4 6
1 2 3 6 4 5
...
1 6 ...
Then, for each partition, I take each pair and find the shortest distance between them and sum them for that partition. The partition with the total smallest distance between its pairs is selected, and I then double all the edges between the shortest path between the odd vertices (found in the selected partition).
These represent the edges the postman will have to walk twice.
At first I thought I had worked out an appropriate algorithm for generating these partitions / pairs but it is flawed. I found it wasn't a simple permutation/combination problem.
Does anyone who has studied this problem before have any tips that can help point me in the right direction for generating these partitions?
