22

有向グラフで強連結成分を見つける方法を説明するいくつかのアルゴリズムを見つけましたが、これを実行する理由を説明するものはありません。強連結成分のいくつかのアプリケーションは何ですか？

4

3 に答える 3

23

Coursera の Tim Roughgarden の Introduction to Algorithms コースをチェックしてください。彼が調べたすべてのアルゴリズムについて、彼はそのいくつかのアプリケーションを説明しています。非常に便利で、アルゴリズムを研究する価値を実感させてくれます!

彼が言ったことを覚えている強連結成分の使用は、それを使用して、膨大なデータセットでより密接に関連している人々のグループを見つけることができるということです。Facebook のことを考えてみてください。Facebook があなたの友達になりそうな人をどのように推薦するかを考えてみてください。

これは、集団のチャンクを表示するためにも使用できます。「うわー、この巨大なコンポーネントはすべて、後ろ向きに歩くのが趣味で、かびの生えたピザを食べるのが好きです!」と言うと、相関関係が示される可能性があります。かびの生えたピザの広告主は、このデータを使用して、後ろ向きに歩くのが好きな人をターゲットにします。知るか！

于 2012-06-26T17:25:19.040 に答える
10

1 つの例は、モデルのチェックです。

強く連結されたコンポーネントの検出は、正式な検証の明示的なモデル チェックで行われます。

モデル チェックでは、ソフトウェア/ハードウェアのモデルを表すステート マシンがあり、その上で時相論理1の式を証明しようとします。

例: 数式のEG(p)意味: グラフにはパスがあり、各状態について - 論理式pは を生成しtrueます。

グラフ(モデル) でEG(p) が真かどうかを証明するアルゴリズムは、最大の強連結成分 (SCC) を見つけてから、グラフでそれにつながるパスをチェックします。

モデル チェックは、特にハードウェア コンポーネントの正確性を証明するために、業界で広く適用されていることに注意してください。

(1) コンピューター サイエンスにおける時相論理の重要性は高く、その発明者であるAmir Pnueliはチューリング賞を受賞しました。

于 2012-06-26T17:35:06.030 に答える