algorithm - 我应该如何为中国 postman 问题生成分区/对？

Question

我正在为涉及解决 Chinese Postman problem 问题的类(class)编写程序.我们的任务只要求我们编写一个程序来解决硬编码图的问题，但我正在尝试自己解决一般情况。

给我带来麻烦的部分是为奇数顶点生成配对分区。

例如，如果我在图中有以下标记的奇数顶点:

1 2 3 4 5 6

我需要找到我可以用这些顶点进行的所有可能的配对/分区。

我想通了，我会得到 i 分区:

  n = num of odd verticies  
  k = n / 2  
  i = ((2k)(2k-1)(2k-2)...(k+1))/2^n

因此，鉴于上面的 6 个奇数顶点，我们将知道我们需要生成 i = 15 分区。

15 个部分看起来像:

1 2   3 4   5 6
1 2   3 5   4 6
1 2   3 6   4 5
...
1 6   ...

然后，对于每个分区，我取每一对并找到它们之间的最短距离并为该分区对它们求和。选择其对之间的总距离最小的分区，然后我将奇数顶点之间的最短路径(在所选分区中找到)之间的所有边加倍。

这些代表 postman 必须走两次的边缘。

起初我以为我已经制定了一个合适的算法来生成这些分区:

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

但是，这是有缺陷的。例如，我意识到，当我到达终点时，选择对位于最左侧的位置(即):

[16] .. ..

在这种情况下，我制定的算法将停止，并且不会生成以 [16] 开头的其余对，因为它的左侧没有要更改的对。

所以，它又回到了绘图板上。

之前研究过这个问题的人有没有任何提示可以帮助我指明生成这些分区的正确方向？

Answer 1

您可以使用递归算法构建分区。

取最低的节点，在本例中为节点 1。这必须与其他未配对的节点之一(2 到 6)配对。对于这些节点中的每一个，使用匹配 1 创建，然后对剩余的四个元素使用相同的算法找到剩余 4 个元素的所有对。

在 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

这会生成以下解决方案:

[(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)]