1

さまざまなセットのノード間の最短パスを見つける必要があります。ここでは、すべてのセットからノードを 1 回だけ使用できます。すべてのノードは、距離を介して他のすべてのノードに接続されています。セット内のノードがそれらの間で接続されていない例外があります。パスには、すべてのセットから 1 つのノードが含まれている必要があります。

例えば。

    Set A - [a1, a2, a3]
    Set B - [b1, b2]
    Set C - [c1]
    Set D - [d1, d2, d3]
    Set Z - [z1, z2, z3]

ノードは a1、a2、a3、b1、b2... です。

例えば。ノードa1は接続しています

b1,b2,c1,d1,d2,d3,z1,z2,z3

またはノードc1が接続している

a1,a2,a3,b1,b2,d1,d2,d3,z1,z2,z3

考えられるパスは次のとおりです。

a1 -> b1 -> c1 -> d1 -> z1、または c1 -> z2 -> a3 -> b1 -> d2

すべてのノード間の距離 (セット内のノードを除き、接続はありません) は 0 から 1 です。

4

1 に答える 1

1

これは、一般化巡回セールスマン問題として知られています。

C. Noon & J.Bean より、一般化された巡回セールスマン問題の効率的な変換:

一般化巡回セールスマン問題(GTSP) は、選択と順序の決定に関する問題に役立つモデルです。問題の非対称バージョンは、アーク A と対応するアーク コスト c のベクトルを接続するノード N を持つ有向グラフで定義されます。ノードは、相互に排他的で網羅的な m 個のノードセットに事前にグループ化されています。接続アークは、異なるセットに属するノード間でのみ定義されます。つまり、セット内アークはありません。定義された各アークには、対応する非負のコストがあります。GTSP は、各ノードセットから正確に 1 つのノードを含む最小コスト m アーク サイクルを見つける問題として述べることができます。

このペーパーでは、問題を標準的な巡回セールスマン問題のケースに変換する方法について説明します。

于 2013-04-22T18:24:49.123 に答える