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

i = 15したがって、上記の 6 つの奇妙な頂点が与えられると、パーティションを生成する必要があることがわかります。

15 のパーティションは次のようになります。

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

次に、パーティションごとに、各ペアを取得し、それらの間の最短距離を見つけて、そのパーティションの合計を計算します。ペア間の合計距離が最小のパーティションが選択され、奇数頂点間の最短パス間のすべてのエッジが 2 倍になります (選択されたパーティションで見つかります)。

これらは、郵便配達員が 2 回歩かなければならないエッジを表します。

最初は、これらのパーティションを生成するための適切なアルゴリズムを考え出したと思いました。

  1. 昇順でソートされたすべての奇数の頂点から始めます

    12 34 56

  2. 現在最大の頂点を持つペアの後ろのペアを選択します

    12 [34] 56

  3. このペアの 2 桁目を 1 増やします。選択したペアの左側のすべてを同じままにし、選択したペアの右側のすべてをセット内の残りの数字にし、昇順で並べ替えます。

    12 35 46

  4. 繰り返す

ただし、これには欠陥があります。たとえば、最後に到達したときに選択ペアが一番左の位置にあることに気付きました (つまり):

[16] .. ..

私が考案したアルゴリズムはこの場合停止し、[16] で始まる残りのペアを生成しません。これは、その左側に変更するペアがないためです。

それで、それは製図板に戻ります。

この問題を以前に研究したことがある人は、これらのパーティションを生成するための正しい方向に私を導くのに役立つヒントを持っていますか?

4

1 に答える 1

4

再帰アルゴリズムを使用してパーティションを構築できます。

最下位のノード、この場合はノード 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)]
于 2010-04-26T17:57:12.703 に答える