我应该如何为中国邮差问题生成分区/对?

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

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

例如,如果我在一个图表中标记了以下奇数垂直线:

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

所以,它又回到了画板上。

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