algorithmchinese-postman

How should I generate the partitions / pairs for the Chinese Postman problem?

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^n

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:

  1. Start with all the odd verticies sorted in increasing order

    12 34 56

  2. Select the pair behind the pair that currently has the max vertice

    12 [34] 56

  3. Increase the second digit in this pair by 1. Leave everything to the left of the selected pair the same, and make everything to the right of the selected pair the remaining numbers in the set, sorted in increasing order.

    12 35 46

  4. Repeat

However, this is flawed. For example, I realized that when I reach to the end and the select pair is at the left most position (ie):

[16] .. ..

The algorithm I worked out will stop in this case, and not generate the rest of the pairs that begin [16], because there is no pair to the left of it to alter.

So, it is back to the drawing board.

Does anyone who has studied this problem before have any tips that can help point me in the right direction for generating these partitions?

Solution

  • You can construct the partitions using a recursive algorithm.

    Take the lowest node, in this case node 1. This must be paired with one of the other unpaired nodes (2 to 6). For each of these nodes, create with match 1, then find all of the pairs of the remaining 4 elements using the same algorithm on the remaining four elements.

    In Python:

    def get_pairs(s):
    if not s: yield []
    else:
        i = min(s)
        for j in s - set([i]):
           for r in get_pairs(s - set([i, j])):
               yield [(i, j)] + r

for x in get_pairs(set([1,2,3,4,5,6])):
    print x

    This generates the following solutions:

    [(1, 2), (3, 4), (5, 6)]
[(1, 2), (3, 5), (4, 6)]
[(1, 2), (3, 6), (4, 5)]
[(1, 3), (2, 4), (5, 6)]
[(1, 3), (2, 5), (4, 6)]
[(1, 3), (2, 6), (4, 5)]
[(1, 4), (2, 3), (5, 6)]
[(1, 4), (2, 5), (3, 6)]
[(1, 4), (2, 6), (3, 5)]
[(1, 5), (2, 3), (4, 6)]
[(1, 5), (2, 4), (3, 6)]
[(1, 5), (2, 6), (3, 4)]
[(1, 6), (2, 3), (4, 5)]
[(1, 6), (2, 4), (3, 5)]
[(1, 6), (2, 5), (3, 4)]