1

オンラインのジャッジのウェブサイトで見つけた問題は次のとおりです。

無向グラフ（ループあり）があります。グラフには k 個の異なるクラスの頂点があります。クラス 1 の頂点は緑、クラス 2 の頂点は赤などと考えることができます。白く着色された頂点の特別なクラスもあります (詳細は後述)。

ここで、ユーザーはソース頂点、宛先頂点、および一連の異なる頂点クラス (白以外) を指定します。

ソース頂点 10、宛先頂点 40、および赤→青→黒のシーケンスが与えられます。

パスが頂点 10 から始まり、1 つの赤い頂点に触れ、その後に 1 つの青と 1 つの黒の頂点が続き、頂点 40 に到達するような最短パスを見つける必要があります。ただし、パスには、必要な数の白い頂点を含めることができます。また、白い頂点を 2 回トラバースすることもできます。

10->20(白)->35(赤)->21(白)->22(白)->30(青)->34(黒)->40

正しくない：

10->20(白)->30(青)->21(白)->22(白)->35(赤)->34(黒)->40 (赤の前に青へ)

10→20(白)→35(赤)→56(赤)→21(白)→22(白)→30(青)→34(黒)→40(赤を通過)二回）

4

3 に答える 3

2

O(n*(n+m))ソリューションは、bfs の変更で完了した単純なグラフの変更に基づいて提案できます。順を追って説明しましょう。

グラフ修正。

  1. トラブルを避けるために、ソースと白い頂点に独自の色を付けます。
  2. グラフを重み付けします。元々存在するエッジの重みは1です。
  3. 色付きの頂点u、vの各ペアに対して、u から v への最短の白いパスに等しい重みを持つエッジ(u,v)を追加します。白いパスは、白い​​頂点のみを通過するパスです。そのような白いパスがない場合は、エッジを追加しないでください。
  4. すべての白い頂点とそれに隣接するエッジを削除します。

2 番目のポイントは、白い頂点のみを通過する各頂点からbfsを実行することで実現できます。これは O( n*(n+m)) で実行されます。

等価。

これで、白い頂点のない重み付けされた色付きグラフができました。変更後も問題が変わらないことは簡単にわかります。ソースからターゲット頂点までの最短経路 (エッジの重みの合計に関して) を見つける必要があります。

検索アルゴリズム。

このグラフの問題を解決するには、提供されたパスの色に対応するレイヤーの bfs のバリエーションを実行します。これは、パス red->blue->black が与えられた場合、bfs が最初に移動するのは、ソースに隣接するすべての赤い頂点に移動し、次に赤でマークされたものに隣接するすべての青に移動し、次にそれらの青にマークされたすべての黒に隣接することを意味します、そして最後にターゲットに。いくつかの頂点が bfs キューにプッシュされるとき、将来の使用のためにパスの長さを覚えておいてください。

疑似コード。

  1. currentVertexes = { (source,0) } // 頂点とパスの長さ
  2. for iから0までの sizeof ( givenPath ) do
    1. nextColor = givenPath[ i ]
    2. 次の頂点= {}
    3. for (v,len) in currentVertexes do
      for all u st exists edge e := (v,u) and u.color = nextColor
      nextVertexes .insert( (u, len + e.length))
    4. 現在の頂点=次の頂点
  3. (ターゲット、長さ) のペアしかないため、 currentVertexesに格納されている最小の長さを選択します。

複雑：

グラフの変更にはO(n*(n+m))の実行時間がかかり、2 番目の部分はO(n*n)を実行します。これは、指定されたパスの長さが n を超えてはならないためです (ステートメントで述べたように色の重複はありません)。であり、各ステップではcurrentVertexesに最大 n 個の頂点が存在できます。全体の複雑さはO(n*(n+m)) + O(n*n) = O(n*(n+m))

于 2013-02-27T10:05:43.867 に答える
1

頂点へのパスが条件を満たしているかどうかを示す追加のフラグを使用して、ダイクストラ アルゴリズムを使用できます。

于 2013-02-27T06:49:42.373 に答える
1

仮定 A1 (後で解除): シーケンス S に色が 2 回存在することはありません。

次に、次のアルゴリズム B1を使用できます。

  1. グラフ G を次の方法で有向グラフ G' に変換します。
    • G' は G と同じノードを持つ
    • v が白ノードで (v,u) が G に存在する場合、(v,u) と (u,v) を G' に挿入します。
    • (v,u) が G に存在し、(color(v),color(u)) が S に存在する場合、G' に (v,u) を挿入します。
    • G の他のすべてのエッジ (ループを含む) は無視されます。
  2. すべてのエッジに同じ重みを割り当てる
  3. G' で最短パス アルゴリズムを実行します。たとえば、Bellman-Ford です。

A1:仮定 A2: S に複数回存在する色は 1 つだけ

アルゴリズム B2 :

  1. wl.og、c0 は S に数回、より正確には n 回存在する色です。
  2. S1=(c1,c2,...,c0), S2=(c3,...,c0)... で、S をサブシーケンス S1、S2、... に分割します。
  3. 各 S_i に対して B1 のステップ 1. に関する変換 G により、グラフ G1、G2、... を生成します。
  4. G1、G2、... Gn を接続してグラフ G' を形成する
    • G1 の色 c0 の各ノードを、色 c3 の各ノードと G2 の任意の白いノードに接続します。
    • G2 と G3 などで同じことを行います。
  5. 送信元が G1 で宛先が Gn の最短パス アルゴリズムを適用する

シーケンス内の複数の繰り返し色への拡張:

シーケンスを繰り返し色のないシーケンスに分割し、B2 を同様に適用します。

于 2013-02-27T08:06:37.097 に答える