2

幅優先検索、dfs、A* などの使用方法に関する多くのスタック オーバーフローの質問を読んできました。問題は、最適な使用法と、実際のシミュレートされたグラフでそれを実装する方法です。例えば

Twitter/Facebook/ソーシャル ネットワーキング サイトのソーシャル グラフがあるとします。検索アルゴリズムは次のように機能するように思われます。

ユーザー A に 10 人の友達がいた場合、そのうちの 1 人には 2 人の友達がいて、もう 1 人には 3 人の友達がいました。検索では、最初にユーザー A の友達が誰であるかを特定し、次に 10 人のユーザーそれぞれの友達が誰であるかを調べる必要があります。私にはこれはbfsのように見えますか？

ただし、それがアルゴリズムの実装方法であるかどうかはわかりません。

ありがとう、

4

2 に答える 2

0

私の 2 セントでは、グラフ全体をトラバースしようとしているだけであれば、各ノードに 1 回しかヒットしない限り、どのアルゴリズムを使用しても問題ありません。これは、あなたが注意するときにあなたが言っていることのようです：

グラフ全体をトラバースしようとしているだけです

これは、用語に技術的な欠陥があることを意味します。グラフを検索するのではなく、グラフをたどることについて話しているのです。実際に特定の何かを検索しようとしている場合を除き、質問でまったく言及していないようです。

そうは言っても、Facebook と Twitter は非常に異なるグラフ構造であり、それらの歩き方に影響を与えます。

  1. Facebook は基本的に無向グラフです。X が Y と友達である場合、Y は X と友達でなければなりません。

  2. Twitter は基本的に有向グラフです。X が Y に従う場合、Y は X に従う必要はありません。

これらの問題は、グラフ ウォーキング アルゴリズムに大きな影響を与えます。正直に言うと、すべてのノードにアクセスしたいだけなら、グラフも必要ですか? それらすべてを反復処理しないのはなぜですか? 反復可能なデータ構造 MY_DATA にすべてのノードがある場合、次のようなジェネレーター式を使用できます。

def nodeGenerator(MY_DATA)
    for node in MY_DATA:
        yield node

明らかに、実際にノードにアクセスする方法を処理するには、nodeGenerator の内部を調整する必要があります。そうは言っても、ほとんどのグラフ構造はノード反復子を実装しています。次に、次の方法でいつでもイテレータを作成できます。

 for node in nodeGenerator(MY_DATA):
     (Do something here)

ここで質問の要点を見逃しているだけかもしれませんが、現在、検索の問題のない検索アルゴリズムについて質問しています。最適化と検索のNo Free lunchの性質により、検索アルゴリズムの価値は、調査しようとしている検索の問題に完全に依存します。

これは、同じデータセット間でも同様です。結局のところ、名前が文字 D で始まるすべての人を検索する場合、すべての人をアルファベット順に並べ替えてバイナリ検索を実行するのが優れた方法です。代わりに、全員のケビン ベーコンからの分離度を見つけようとしている場合は、ベーコン氏で始まり、ベーコン氏を知っているすべての人と彼らが知っているすべての人を再帰的に反復するアルゴリズムが必要になります。これらはどちらも Facebook や Twitter でできることですが、具体的な情報がなければアルゴリズムを推奨する方法はありません。したがって、何もわからない場合は、全員をリストとして繰り返します。それは他のものと同じくらい良いです。その後、最適化する場合は、計算をキャッシュします。

于 2011-06-06T00:15:02.947 に答える
0

Facebookには約300人の友達がいて、平均して300人の友達がいる友達もいます。そこからグラフを作成すると、膨大な量になります。間違っていたら訂正してください。. このシナリオでは、BFS は非常に厳しいものになるのでしょうか?

ありがとうJ

于 2011-06-13T19:09:32.560 に答える