16

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

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

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

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] 的其余对，因为它的左侧没有要更改的对。

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

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

4

1 回答 1

4

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

取最低节点，在本例中为节点 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)]
于 2010-04-26T17:57:12.703 回答