7

のサブセットである単純な無向グラフがあるG(V,E)とします。のすべてのノードからの距離が同じで、距離が最小になるノードをどのように見つけることができますか? ない場合はそのまま戻ります。これは複雑にできると言われました。FVvFvNonevO(|V|+|E|)

すべてのエッジの距離が 1 であると仮定します。

これを行う方法を説明できる人はいますか？疑似コードも役立ちます。

4

2 に答える 2

3

解決策は BFS に似ていますが、少し変更があります。

  1. S = F から開始し、F ノードにマークを付けます。

  2. |S|を見つける S の各要素からの距離が 1 のセット (これらすべてのセットには、マークされていないノードが含まれている必要があります)。これらのセットの共通部分が空でない場合、候補が見つかります。

  3. |S| の結合を取る 上記の S' を設定し、これらのノードをマークします。S' が空の場合は、'None' を返します。

  4. 手順 2 に戻ります。

すべての集合操作に一定の時間がかかると仮定すると、アルゴリズムの複雑さは O(|V| + |E|) である BFS と同じになります。

ここで、集合操作の複雑さについて推論します。私の推論は、ステップ 2 と 3 の結合操作と交差操作を組み合わせて時間 O(|S|) を使用できるため、セット操作によって複雑さが増しません。また、すべてのステップで S は前の反復の S とは異なるため、集合演算の全体的な複雑さは O(|V|) になります。

于 2013-03-26T23:22:49.833 に答える
3

これは、疑似コードのアルゴリズムの 1 つです。コメントを追加して、それがどのように機能するかを説明しようとしています。

declare explored // a table of all the vertices that can keep track of one number (distance, initialized to -1) and a list of vertex references (origins, initialized to null)
to_explore = S  // fifo queue of vertices to explore

while (to_explore not empty) {
    pop vertex v from to_explore
    current_distance = explored[v].distance
    current_origins = explored[v].origins
    for (vertex n, neighbor of v) {
        if (explored[n].origins contains v)
            continue // we just hit a loop and we're only interested in shortest distances
        if (explored[n].distance == -1) { // first time we come here
            explored[n].distance = current_distance+1
            explored[n].origins = current_origins
            push n to to_explore
            continue
        }
        if (explored[n].distance != current_distance+1) {
            continue // we are merging path from another node of S but different distance, cannot lead to any solution
        }
        // only case left is explored[n].distance == current_distance+1
        // so we've already come here from other place(s) in S with the same distance
        add / merge (without duplicates) origins to explored[n].origins
        if (explored[n].origins = S) // maybe compare the size is enough?
            return n // we found a solution
        // if not , we just continue our exploration, no need to add to the queue since we've already been through here before
    }
}

アイデアは、FIFO キューを使用して、セット S から距離 1 にあるすべてのものを探索し、そこに解が見つからない場合は、距離 2 にあるすべてのものを探索するというものです...など..最初に最短距離を見つけます。

複雑さについては完全にはわかりませんが、最悪の場合、すべての頂点とすべてのエッジを 1 回だけ探索すると、O(|E| + |V|). しかし、場合によっては、同じ頂点に複数回アクセスすることがあります。それによって探索するパスが大幅に増えるわけではありませんが、係数 |S| が必要かどうかはわかりません。どこか（ただし、それが定数のように見なされる場合は、問題ありません...）

何も見逃していないことを願っています。明らかに、私はこれをテストしませんでした.... :)

編集(コメントへの返信)

あなたのコードはこのようなグラフで機能しますか? E = ( a, b), (a, c), (a,d) , (b,e), (c,e), (d, e), my F = { b, c , d}. たとえば、bfs を a で始めます。最終的に origins 配列には {a} のみが含まれるため、コードは None を返すと思われます。– 達人デバンラ

この場合、次のようになります。

to_explore is initialized to {b,c,d}
//while (to_explore not empty)
pop one from to_explore (b). to_explore becomes {c,d}
current_distance=0
current_origins={b}
//for (neighbors of b) {
handling 'a' as neighbor of b first
explored[a].distance=1
explored[a].origins={b}
to_explore becomes {c,d,a}
//for (neighbors of b)
handling 'e' as next neighbor of b
explored[e].distance=1
explored[e].origins={b}
to_explore becomes {c,d,a,e}
//while (to_explore not empty)
pop one from to_explore (c). to_explore becomes {d,a,e}
current_distance=0
current_origins={c}
//for (neighbors of c)
handling 'a' as neighbor of c first
explored[a].distance is already 1
explored[a].origins={b,c}
to_explore already contains a
//for (neighbors of c) {
handling 'e' as next neighbor of b
explored[e].distance is already 1
explored[e].origins={b,}
to_explore already contains e
//while (to_explore not empty)
pop one from to_explore (d)
current_distance=0
current_origins={d}
//for (neighbors of d)
handling 'a' as neighbor of d first
explored[a].distance is already 1
explored[a].origins={b,c,d}
that matches F, found a as a solution.
于 2013-03-29T04:41:20.860 に答える