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

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