3

色付きの有向グラフ (各ノードには色があります) があり、ノード A からノード B へのパスが存在し、そのパスが各色を MOST で 1 回通過するかどうかを調べたいと考えています。

この問題は、ネットワーク フローを使用して定式化できると思います。ノードが繰り返される場合、フローを 0 または無限大にする同じ色のノードに何らかのペナルティを課すことができます。

ありがとう！

4

3 に答える 3

1

検索アルゴリズムを使用してそれを行いたいと仮定すると、グラフからアクセスした各ノードを削除 (または既にアクセス済みとしてマーク) し、バックトラッキングで深さ優先を使用する可能性が最も高いでしょう。

訪問した色のハッシュテーブルを保持して、見つかった新しい色がわかっているかどうかをすばやく確認します (または、A から C [=現在] または C から A へのグラフ上の訪問されたパスを確認します [関係ありません]別の構造を使用することはできず、グラフにプロパティをアタッチするだけです)。

バックトラッキングの場合、デッドエンドにつながった発信リンクからノードにバックトラックした後、次の発信リンクを確認できます (つまり、B に到達できませんでした)。これは、リンクにいくつかの暗黙的な順序付けがあることを前提としています (つまり、次のリンクを要求できます - そして、それが発信リンクであるかどうかをチェックするか、それ以上利用できなくなるまで次のリンクを要求することができます)。バックトラックしながら戻ってきた））

ただし、グラフの（並列化可能な）前処理を行い、特定の色または任意の色からの検索に役立つノードおよび/またはリンクに値を添付する、より優れたアルゴリズムが必要です。

于 2015-11-08T01:03:01.747 に答える
1

これは、すべての禁制ペアが互いに素である必要がある「禁制ペアのあるパス」問題の特殊なケースからの還元による NP 困難です。禁断の各ペアに色を割り当てるだけです。「禁制ペアのあるパス」はよく知られた NP 困難な問題です (互いに素なペアの場合でも NP 困難のままです)。ゲイリーとジョンソンの本では、識別子「GT54」があります。

しかし、一意でない色の数 ( ) が小さな定数である場合、時間計算量 O(|E| * 2 2*kk )で修正された BFS アルゴリズムを適用できます。

ここでは、この BFS アルゴリズムについて説明します (簡略化されたバージョンから始めます)。

パスがアクセスしたすべてのノードの色は、ビットセットにエンコードする必要があります。たとえば、3 つの使用可能な色 (赤、緑、青) があり、緑のノードにアクセスしたパスがある場合、これは としてエンコードされ010ます。このパスが赤いノードにもアクセスした後、 としてエンコードされ011ます。パスの色は、最後にアクセスしたノードとともに BFS キューに格納されます。

各ノードは、色の組み合わせごとに「訪問済み」フラグを保存する必要があります。3 色の例を想定すると、アクセスされていない各ノードには、「false」値を持つ 8 つのブール値が格納されます。赤/緑のパスでこのノードにアクセスした後、その「訪問済み」フラグを次のように変更する必要があります。

index.bool  index.dec  visited_flag
       000          0         false
       001          1         false
       010          2         false
       011          3          true
       100          4         false
       101          5         false
       110          6         false
       111          7         false

アルゴリズムが同じ色の組み合わせでパスを処理しているときに同じノードに遭遇した場合、「真」の訪問フラグがあるため、アルゴリズムはそれを無視する必要があります。

BFS アルゴリズムのメイン ループの擬似コードは、次のように書き換えることができます。

 while Q is not empty:

     (u, c) = Q.dequeue()

     for each node n that is adjacent to u:
         if (c & n.color) == 0 && n.visited[c] == false:
             n.visited[c] = true
             Q.enqueue((n, c | n.color))

アルゴリズムは通常どおり終了します。宛先に到達する (パスが存在する) か、BFS キューが空になる (パスが存在しない) かのいずれかです。

このアルゴリズムの最悪の場合の時間計算量は O(|E| * 2 k ) です。それでも、多くの冗長な作業を行っています。BFS アルゴリズムでは、短い (そしてカラフルではない) パスが長いパスよりも早いと見なされるため、一部のノードは最初に赤いパスで、次に緑のパスで、次に赤/緑のパスで訪問される可能性があります。この場合、この赤/緑のパスを処理しても改善は見られませんでした。つまり、緑のパスを処理しながら、赤/緑を以前に「訪問済み」としてマークすることで、アルゴリズムを高速化できます。この最適化は無料ではありません: 各パス/ノードの組み合わせを処理する際にいくつかのフラグをマークする必要があり、最悪の場合の時間の複雑さが O(|E| * 2 2*k ) に増加します。ただし、追加の作業はすべてノード内でローカルに行われます。また、すべて 2 kの場合フラグは 1 つの CPU レジスタに収まるため、この作業はすべて、ビットごとの論理演算で並列に実行できます。

于 2015-11-08T12:37:21.270 に答える