3

アイデアと代替ソリューションで返信してくれた皆さんに感謝します。問題を解決するためのより効率的な方法はいつでも歓迎されます。とはいえ、私がアルゴリズムで解決しようとしている問題をしばらく無視して、私が書いたアルゴリズムの非常に複雑な部分を分析するのを手伝ってもらいたいのですが、すべて単純なパスです.ここで説明されている深さ制限検索を使用したグラフで、ここで実装されています。ありがとう！

編集：これは宿題ですが、私はすでにこの課題を提出しており、私の答えが正しいかどうか知りたいだけです. 再帰が関係している場合、Big-O の複雑さに少し混乱します。

以下の元の質問：

このアルゴリズムによって与えられる全パス検索の複雑さを見つけようとしています。2 つの頂点が与えられた場合、深さ優先検索を使用してそれらの間のすべての単純なパスを見つけています。

DFS の時間計算量は O(V+E) であり、その空間計算量は O(V) であることを知っています。私の直感では、全パス検索の複雑さはそれ以上になると思いますが、それが何であるかを決定します。

関連する SO の質問はこちらとこちらです。

更新（以下のコメントに応じて）：

私は6 次のケビン ベーコン問題を解こうとしています。これには通常、アクターのペア間の最小の分離度を見つける必要がありますが、すべての分離度を見つける必要があります (現時点では 6 未満ですが、これは変更される可能性があります)。

4

4 に答える 4

5

最悪のシナリオは (私が思うに) n頂点の完全なグラフです。このグラフにはn ! 単純なパスであり、それらのそれぞれについて、アルゴリズムは少なくともn ^2 の計算ステップを実行します。パスの最後の頂点に隣接する各頂点について、以前にアクセスしたノードのリンクされたリストに対して線形スキャンを実行します。(検索のすべての中間段階を数えているわけではありません。) したがって、複雑さは少なくとも O( n ^2 * n !) であり、さらに悪い可能性があります。

あなたが解決しようとしているより大きな問題は何ですか？

于 2009-12-02T05:02:23.400 に答える
1

制限を与えるので、6度はいいです。6は変わる可能性があることは理解していますが、ここでのアプローチはまだ適用できると思います. 「6」と言うところはどこでも、「度数」に置き換えてください。

必要に応じて、幅優先探索 (BFS) を使用できます。私の理解が正しければ、開始点 (俳優/女優) が与えられ、エンドポイント (ケビン ベーコン) までの 6 エッジ以下のすべてのパスを見つける必要があります。最初に 1 エッジ離れたすべての接続を見つけ、次に 2 エッジ離れたすべてのパスを見つけて ... 、最後に 6 エッジ離れたすべてのパスを見つけると言って、サブ問題に分割できます。これはまさに BFS の仕組みです...最初に 1 エッジ離れたすべてのノードを調べ、次に 2 エッジというように調べます。

別の方法として、通常の DFS を実行して修正された深さ優先検索 (DFS) を使用し、各パスをできる限り追跡することもできますが、カウンターを保持し、特定のパスに 6 エッジを超えて深くならないようにします。

すべての頂点にアクセスしたり、すべてのエッジに沿って移動したりする可能性が低いため、通常の O(V + E) よりもはるかに優れたソリューションになると思います (グラフが多数のアクター間の関係であると仮定します)。むしろ、グラフ全体のサブグラフに制約されます。すべての頂点/エッジにアクセスするように検索アルゴリズムを開始しますが、BFS を使用するか DFS を使用するかに関係なく、グラフ全体を調べるのではなく、開始頂点から 6 つのエッジで停止します。 .

DFS のようなものは O(V+E) として表すことができますが、O(b^d) として表すこともできると考えてください。ここで、b は分岐係数、d はグラフの深さです (詳細については、Wikipedia_DFSを参照してください)。俳優が何人いるかを考えると、b は何になるでしょうか? 問題について知っている制約 (6 度とそうでないもの) を考えると、d はどうなるでしょうか?

私はおそらく十分に言ったと思います。うまくいけば、それがあなたのためにそれを開始します。私は実際に答えを確実に知らないという警告を追加する必要があります。これが問題が私を襲う方法です;）

于 2009-12-02T06:40:34.317 に答える
1

私の分析で私自身の質問に答えて、コメント/修正してください!

The algorithm is simplified and analyzed as follows: 
(Note: here MAXDEPTH is the maximum degrees of separation to search for, default 6)
1. For the current vertex, get neighbors (amortized O(1))
2. For every neighbor, do the following [O(b), where b is the branching factor, or the avg. number of neighbors of a vertex]
2.1.    Check if already visited [O(MAXDEPTH), since it’s a linked list of max size MAXDEPTH)
2.2.    Append path to paths list [amortized O(1)]
3. End for 
4. Do the following MAXDEPTH times [O(MAXDEPTH)]
4.1.    For every neighbor do the following [O(b)]
4.1.1.      Check if already visited [O(MAXDEPTH)]
4.1.2.      Add to visited list [O(1)]
4.1.3.      Recursively call search again [becomes O(MAXDEPTH*b)]
4.1.4.      Delete from visited list [O(1)]
4.2 End for /* Neighbor */
5. End loop /* MAXDEPTH */

Thus, the complexity becomes O((MAXDEPTH*b)^MAXDEPTH).
于 2009-12-04T04:04:46.197 に答える
0

O((n^2)*depth ) アルゴリズムの使用を考えていました

  1. 各俳優について、彼が働いていたすべての俳優を見つけます。(O(n^2) の空間と時間の複雑さですが、どちらも実際の接続数に依存し、ほとんどのアクターは 500 または Facebook の友達の数の 5 倍を超えません) これにより、500*n の時間と空間の複雑さがもたらされます。

  2. すべての人を同じ深さで 3 つ全体を組み立て、このすべての接続を追加します。O(n^2*深さ)

接続を保存するために二重にリンクされたツリーを使用すると、すべての接続を深さ * n の複雑さで見つけることができます

于 2009-12-02T08:00:33.467 に答える