問題タブ [bacon-number]

私はいくつかのことをいじっていて、 Kevin Baconの数を理解しようとするアイデアを思いつきました。この目的のためにソーシャルネットワークと見なすことができるサイトのデータがあります。Facebook だとしましょう (議論を簡単にするため)。私には人々がいて、彼らの友達のリストを持っているので、彼らの間のつながりがあります。ある人から別の人への距離 (基本的には、ケビン ベーコン数) を計算するにはどうすればよいですか?

私の最善のアイデアは、深さ制限のある双方向検索です（計算の複雑さを制限し、グラフで接続できない人々の問題を回避するため）が、これはかなり力ずくであることに気付きました。

小さなサブグラフ (Facebook のグループに相当するようなもの) を作成し、それらの間の最短距離を (おそらく前もって) 計算してから、THOSE を使用してリンクを見つけようとする方がよいでしょうか? これには事前計算が必要ですが、より少ないノードを検索できる可能性があります (ノードは個人ではなくグループである可能性があり、グラフがはるかに小さくなります)。ただし、これは依然として双方向検索になります。

また、特定の目的地の個人に接続する可能性が最も高い可能性があるため、最初に「人気のある」人々のノードを検索して、個人が接続している人の数を事前に計算することもできます。これは、可能な最短経路に対する速度のトレードオフになることを認識しています。他のケースで使用する予定の幅優先検索の代わりに、深さ優先検索も使用したいと思います。

誰かがこれを行うためのより簡単で高速な方法を考えられますか? 2 人の間の最短の長さを見つけられるようにしたいので、終点が常に同じであるほど簡単ではありません (Kevin Bacon の問題など)。

200人のチェーンを取得できるなどの問題があることは認識していますが、検索する深さに制限があるため、それは解決できます。

Oracle9i のデータベースに次のテーブルがあります。

映画 (fid) で働いた俳優 (援助) に関するデータが含まれています。

私がやりたいことは、 ベーコン数を計算することに似ています

私のケビンベーコンを除いて、援助517635を持っていることで知られています.

517635 への接続を見つけるために、特定のアクターを (別の支援によって) 接続する必要があるアクターの数を (SQL ステートメントのみを使用して) 計算する方法についての手がかりがありません。

クエリの結果は、指定されたアクターが私の男に到達するために接続する必要があるすべてのアクターのリスト、または単なる数字のいずれかになります。

そのためには、最初に 517635 が協力したすべてのアクターを取得する必要があると考えました。これらのアクターは、彼と直接協力した結果として 1 になります。テーブルは大きすぎませんが、それを不可能にするのに十分な大きさです。

例として、ブラッド・ピットが私の 517635 であるとしましょう。彼はミスター・アンド・ミセス・スミスでアンジェリーナ・ジョリーと仕事をしたとしましょう。それは彼女をナンバー 1 にするでしょう。ジョリーは彼と一緒だったので、ブラッド・ピットに対するブルース・ウィリスの番号は2になります.

私のクエリでは、指定された番号がアンジェリーナの場合、結果は次のようになります: "ブラッド ピット 1" または単に "1" 指定された番号がウィリスの場合、結果は次のようになります: "アンジェリーナ ジョリー ブラッド ピット 2" または "2" 何の例表にあります：

私は何も考えていません。私はSQLにまったく慣れていないので、ループの数をカウントする変数を使用して無限ループにつながると考えることができます。どこから始めて、運が良ければ終了するかについてのアイデアはありますか?