4

ノードのグラフ (ネットワーク) があるとします。重み付けは次のとおりです。 1. 2 つのノード間のリンクを片道移動する。2. 2 つのノード間のリンクを逆方向に移動する (これらは異なる場合があります)。3. あるリンクから別のリンクへの変更。

また、一部のノードは一方向のみです。

この場合、次の場合に最適なアルゴリズムは次のとおりです。a) 最小スパニング ツリーを見つける b) 2 つのノード間の最短ルートを見つける c) 「巡回セールスマン」パス (つまり、どこにでも行き、重複を最小限に抑える最短ルート) を見つける?

また、双方向のものを、各方向に異なる重みを持つ双方向パスではなく、2 つの単方向パスとして扱うのが最善でしょうか?

- -例 - -

              3
  A --<2/3>-- B --<3/2>-- C
  | 1        2|3
  |           |
  ^1/4       ^4/3
  |           |
  |3         4|
8 D --<3/5>-- E
  |2
  |
1 ^3/1
  |
  |
  F

<2/3> は、左に移動する 2 と右に移動する 3 の重量を意味します。^1/4 は、1 が上に移動し、4 が下に移動することを意味します。2 つのリンク間の 1 つの数値は、リンクを変更するコストです。たとえば、AD から DF に移動するには 8 のコストがかかり、AB から BE に移動するには 2 のコストがかかります。

それが理にかなっていることを願っています...

サイモン

(ps悪い用語についてお詫びします-「リンク」、「エッジ」-好きなものなら何でも;))


重み付けの種類をよりよく説明するために、エッジが線路であり、ノードが駅であると想像してください。エッジのコストは 2 つの駅間の電車の移動時間であり、ノードのコストはインターチェンジ時間の長さです (プラットフォームがどれだけ離れているかによって、同じノードであってもエッジ間で異なる場合があります。サービスの定期性など)。

4

2 に答える 2

4

はい、これらを 1 つではなく 2 つのエッジとして扱います。次に、特に各方向に重みがあることが常に保証されている場合は、これに従来のグラフ理論アルゴリズムを問題なく使用できます。これらのアルゴリズムは、作成を支援したばかりの「通常の」グラフを使用している場合は簡単に見つけることができます。

最短経路にはダイクストラを使用できます。

最小スパニング ツリーの Primを実行できます。

非対称 TSP を Google で検索して、そのアルゴリズムを見つけようとすることができます。アルゴリズムの紹介にもこれに関する何かがあると確信しています。申し訳ありませんが、適切な実装が見つかりませんでした。非対称 TSP と呼ばれることがわかったので、ここには非対称 TSP に関する良い質問がいくつかあります。

幸運を!グラフ理論が好きです。

-ブライアン・J・スティナー-

于 2011-04-26T23:35:54.377 に答える
2

「交換」重みについては、それらをエンコードする小さなサブグラフを作成できます。たとえば、次のようなものがあります。

  |   
  |3  
8 D --
  |2
  |

次のように、エッジの重みだけを使用してエンコードできます。

  |
  |
  D0
  | \3
  |  \
 8|   D2--
  |  /
  | /2
  D1
  |
  |

D0 から D1 に移動するために 8 エッジを使用する必要がないことに注意してください。代わりに、5 の重みで D0->D2->D1 に移動できます。それが元の定式化で許可されているかどうかはわかりません。

于 2011-04-28T18:17:36.527 に答える