7

これは私が最近インターネットで見つけたインタビューの質問です：

Facebookで2人の分離度をどのように見つけますか？さまざまなアイデア、アルゴリズム、およびトレードオフについて話し合います。（分離度の定義：http：//en.wikipedia.org/wiki/Six_degrees_of_separation）

これが私がそれについて考えることです：

私が考えることができる候補アルゴリズムは、幅優先探索（BFS）、深さ優先探索（DFS）、深さ制限探索（DLS）、反復深化探索（IDS）です。

まず、DFSを考慮する必要があります。2人が接続している場合（つまり、分離度= 1）でも、アルゴリズムが間違ったパスを長時間検索し続ける可能性があります。

BFSは、最小の分離度を見つけることが保証されています（グラフは重み付けされていないため）。最大分岐係数がbであり、2人の対象者間の実際の分離度がdであると仮定すると、時間計算量と空間計算量の両方がO（b ^ d）になります。

可能な最大の分離度は不明であるため（6より高くなりすぎないようにする必要があります）、DLSを使用することはお勧めできません。ただし、IDSはBFSよりも優れたアイデアのようです。時間計算量もO（b ^ d）です（ただし、中間ノードに繰り返しアクセスするため、実際の時間はBFSよりも少し高くなります）が、空間計算量はO（ bd）、これはO（b ^ d）よりもはるかに優れています。

結局のところ、私はIDSを選択します。それは面接で受け入れられる答えですか？上記の推論で間違いを犯しましたか？または、私が見逃したより良い解決策はありますか？

前もって感謝します。

4

2 に答える 2

10

より良い解決策は、両方のノードから同時にBFSを開始することです。次の擬似コードのようなもの：

nodes1 = (A);
nodes2 = (B);
d = 1;
loop {
    nodes1 = neighbors(nodes1);
    if (intersects(nodes1, nodes2)) {
        return d;
    }
    d += 1;
    nodes2 = neighbors(nodes2);
    if (intersects(nodes2, nodes1)) {
        return d;
    }
    d += 1;
}

このアルゴリズムの時間計算量は、はすべてのノードの最大次数であり、O(m ^ (d/2))は最大距離です。を使用した単純なBFSと比較すると、大きなグラフではこれがはるかに高速になります。mdO(m ^ d)

于 2013-03-10T01:17:39.593 に答える
1

If you're looking for the degree of separation between two specific people, I'd use Dijkstra's algorithm, which will find the shortest paths from a chosen source to all reachable nodes.

于 2013-03-09T22:38:21.043 に答える