我应该如何为中国邮递员问题生成分区/对？

Question

我正在编写一个课程程序，涉及解决中国邮递员问题。我们的作业只需要我们编写一个程序来解决硬编码图的问题，但我正在尝试自己解决一般情况。

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

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

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   ...

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

这些代表邮递员必须走两次的边缘。

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

1. 从所有奇数顶点开始按升序排序

   12 34 56

2. 选择当前具有最大顶点的对后面的对

   12 [34] 56

3. 将此对中的第二个数字增加 1。将所有内容留给 所选对的左侧相同， 并使一切都在右边 所选对 剩余的 集合中的数字，已排序 增加订单。

   12 35 46

4. 重复

但是，这是有缺陷的。例如，我意识到当我到达末尾并且选择对位于最左边的位置（即）：

[16] .. ..

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

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

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

Answer 1

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

采用最低节点，在本例中为节点 1。它必须与其他未配对节点（2 到 6）之一配对。对于每个节点，使用匹配 1 创建，然后对剩余 4 个元素使用相同的算法查找剩余 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)]