Stevey Yegge のGet That Job At Googleの記事を読んだ後、次の短い引用が興味深いものであることがわかりました。
誰かがあなたに問題を与えるときはいつでも、グラフを考えてください。それらは、あらゆる種類の関係を表現する最も基本的で柔軟な方法です。そのため、興味深いデザインの問題にグラフが関係しているのは、50 ～ 50 ショット程度です。他のソリューション タイプに移る前に、グラフを使用してそれを解決する方法を思いつかないことを絶対に確認してください。このヒントは重要です！
グラフのデータ構造/アルゴリズムによって最もよく表現および/または解決される問題の例は何ですか?
私が考えることができる 1 つの例: 現在の場所から別の場所への道順を提供するナビゲーション ユニット (ala Garmin、TomTom) は、グラフと高度なパス アルゴリズムを利用します。
他のいくつかは何ですか？
コンピュータ ネットワーク:グラフ モデルは、コンピュータ ネットワークとインターネットを直感的にモデル化します。多くの場合、ノードはエンド システムまたはルーターを表し、エッジはこれらのシステム間の接続を表します。
データ構造:ポインターを使用してデータをリンクするデータ構造は、何らかのグラフを使用しています。これには、常に使用されるツリー構造とリンクされたリストが含まれます。
パスとマップ:ある場所から目的地までの最短または最長のパスを見つけようとすると、グラフが使用されます。これには、Google マップなどのアプリケーションで見られるようなパスや、ビデオ ゲームで AI キャラクターがたどるパスの計算、および他の多くの同様の問題が含まれます。
制約の充足: AI の一般的な問題は、制約のリストを満たす何らかの目標を見つけることです。たとえば、大学がコースのスケジュールを設定するには、特定のコースが競合しないこと、教授が同時に 2 つのコースを教えていないこと、講義が特定の時間帯に行われることなどを確認する必要があります。 . このような制約充足問題は、多くの場合、グラフを使用してモデル化および解決されます。
分子:グラフを使用して原子や分子をモデル化し、相互作用や構造を研究することができます。
私はグラフ理論に非常に興味があり、それを使って非常に多くの異なる種類の問題を解決しました。グラフを使ってパス関連の問題、マッチング問題、構造問題などの多くの問題を解くことができます。
パスの問題には多くのアプリケーションがあります。
これはキャリアカップのインタビューの質問でした. サブ配列の最長合計を見つけたいとします。たとえば[1, 2, 3, -1]、最長の合計は 6 です。それを有向非巡回グラフ( DAG ) としてモデル化し、ダミーのソースとダミーの宛先を追加します。数に対応する重みを持つエッジで各ノードを接続します。この問題を解決するには、DAG で最長パスアルゴリズムを使用します。
同様に、金融の世界でのアービトラージ問題や、最長の重複構造を見つける幾何学の問題でさえ、同様のパスの問題です。
いくつかの明白な問題は、ネットワークの問題です(ネットワークにコンピューターの人、組織図などが含まれている可能性があります)。次のような
多くの構造情報を収集できます
私は、グラフを使用して多くのプロジェクト管理関連の問題を解決してきました。イベントのシーケンスは、有向グラフとして描くことができます(サイクルがない場合は、そのほうがよいでしょう)。だから、今、あなたはすることができます
多くのマッチング問題はグラフで解くことができます。たとえば、プロセッサをワークロードに一致させたり、ワーカーをジョブに一致させたりする必要がある場合です。私の最終試験では、人々をレストランのテーブルに合わせる必要がありました. 同じ原則に従います (二部マッチング -> ネットワーク フロー アルゴリズム)。シンプルでありながら強力です。
特別なグラフであるツリーには、コンピューター サイエンスの世界で数多くの用途があります。たとえば、プログラミング言語の構文やデータベースのインデックス構造などです。
最近では、コンパイラの最適化問題でもグラフを使用しました。魅力的なテクニックを教えてくれるモーガンの本を使っています。
リストは本当に延々と続きます。グラフは、関係の美しい数学の抽象化です。正しくモデル化できれば、本当に素晴らしいことができます。また、グラフ理論は非常に多くの応用が見出されているため、この分野では多くの活発な研究が行われています。そして、数多くの研究のおかげで、研究を後押ししているさらに多くのアプリケーションが見られます.
グラフ理論を始めたい場合は、初心者向けの優れた離散数学の本 ( Rosenが思い浮かびます) を入手してください。また、 FouldやEvenなどの著者から本を購入できます。CLRSには優れたグラフ アルゴリズムもあります。
ソース コードはツリー構造であり、ツリーは一種のグラフです。AST (Abstract Syntax Tree) について話しているのを聞くときはいつでも、彼らは一種のグラフについて話しているのです。
ポインタはグラフ構造を形成します。ポインターを操作するものはすべて、ある種のグラフ操作を行っています。
ウェブは巨大な有向グラフです。Google を検索で優位に立たせた重要な洞察は、Web のグラフ構造がページのテキスト コンテンツと同等またはそれ以上に重要であるということです。
ステート マシンはグラフです。ステート マシンは、ネットワーク プロトコル、正規表現、ゲーム、およびその他のあらゆる分野で使用されます。
ある種のグラフ構造を含まないことを考えるのはかなり難しいです。
ほとんどの人がよく知っている例は、ビルド システムです。Make は典型的な例ですが、ほとんどの優れたビルド システムは有向非巡回グラフに依存しています。基本的な考え方は、方向がソースとターゲットの間の依存関係をモデル化し、物事を正しく構築するために特定の順序でグラフを「ウォーク」する必要があるということです->これはトポロジカルソートの例です。
もう 1 つの例は、ソース管理システムです。これも DAG に基づいています。たとえば、共通の親を見つけるために、マージに使用されます。
コンパイラが使用する多くのプログラム最適化アルゴリズムは、グラフに基づいています (たとえば、呼び出しグラフの把握、フロー制御、多くの静的解析)。
多くの最適化問題はグラフに基づいています。多くの問題はグラフの彩色や同様の問題に還元できるため、他の多くの問題もグラフに基づいています。
グラフがすべての関係を表現する最良の方法であることに同意するかどうかはわかりませんが、これらの「釘を打った、ハンマーを見つけよう」というアプローチは避けようとしています。多くの場合、グラフはメモリ表現が貧弱であり、多くのアルゴリズムは、行列、ビットセット、およびその他のものを使用して実装すると、実際には (実際には) より効率的です。
OCR。斜めにスキャンされたテキストのページを想像してみてください。画像にはノイズがあり、テキストの行間のスペースを見つける必要があります。1 つの方法は、ピクセルのグラフを作成し、ページの一方の端からもう一方の端までの最短経路を見つけることです。明るさの差はピクセル間の距離です。
この例はAlgorithm Design Manualからのもので、グラフの問題の実例が他にもたくさんあります。
人気のある例の1つは、ガベージコレクションです。
コレクターは一連の参照から開始し、次に参照するすべてのオブジェクトをトラバースし、次にそこで参照されるすべてのオブジェクトをトラバースします。見つかったものはすべて、到達可能なオブジェクトのグラフに追加されます。他のすべてのオブジェクトは到達不能であり、収集されます。
2 つの分子が結合できるかどうかを調べます。薬を開発するとき、薬の分子が体内のより大きな分子に収まるかどうかに関心を持つことがよくあります。これが可能かどうかを判断する際の問題は、分子が静的ではないということです。分子のさまざまな部分が化学結合の周りを回転できるため、分子はさまざまな形に変化します。
それぞれの形は、形で構成される空間内の点を表していると言えます。この問題を解決するには、この空間を通る経路を見つける必要があります。空間を通るロードマップを作成することでそれを行うことができます。これは基本的に、合法的な形状で構成され、形状がどの形状に変わるかを示すグラフです。このロードマップを通じて A* グラフ検索アルゴリズムを使用することで、解決策を見つけることができます。
さて、それはおそらくあまり理解できなかったり、明確でなかったりする、たくさんのせせらぎでした。しかし、私が言いたいのは、グラフはあらゆる種類の問題で現れるということです。
グラフはデータ構造ではありません。それらは関係の数学的表現です。はい、グラフを使用して問題について考え、理論化することができます。それに関する理論は数多くあります。しかし、アルゴリズムを実装する必要がある場合は、グラフではなく、問題を最もよく表すデータ構造を選択しています。一般的なグラフを表す多くのデータ構造があり、特殊な種類のグラフにはさらに多くのデータ構造があります。
あなたの質問では、これら2つのことを混ぜ合わせています。同じ理論上の解決策がグラフの観点からである場合もありますが、実際の解決策では、グラフを表すために異なるデータ構造を使用する場合があります。
以下は、グラフ理論に基づいています。
グラフは、依存関係を管理するのに最適です。
私は最近、キャッスル ウィンザー コンテナを使い始めました。カーネルを調べたところ、GraphNodes プロパティが見つかりました。Castle Windsor はグラフを使用してオブジェクト間の依存関係を表し、注入が正しく機能するようにします。この記事をチェックしてください。
また、単純なグラフ理論を使用してプラグイン フレームワークを開発しました。各グラフ ノードはプラグインを表し、依存関係が定義されたら、グラフを走査してプラグインのロード順序を作成できます。
各プラグインが特定のバージョンで重み付けされるように、ダイクストラのアルゴリズムを実装するようにアルゴリズムを変更することを計画しています。したがって、単純な変更ではプラグインの最新バージョンのみが読み込まれます。
私はこれをもっと早く発見しました。「誰かがあなたに問題を与えるときはいつでも、グラフを考えてください」という言葉が好きです。確かにそうだと思います。
人々の間の社会的つながりは、興味深いグラフの例になります。従来の RDMS を使用して、これらの接続をデータベース レベルでモデル化しようとしましたが、難しすぎることがわかりました。最終的にグラフ データベースを選択しましたが、人 (ノード) 間の接続 (エッジ) を簡単にたどることができるので、これは素晴らしい選択でした。
リレーショナルデータベースで外部キーとしてモデル化できるものはすべて、基本的にグラフのエッジとノードです。
ほとんどのものはRDBMSで簡単にモデル化されるので、おそらくそれは例を考えるのに役立つでしょう。
プロファイリングおよび/またはベンチマークのアルゴリズムとコードでの実装。
Neo4j wiki の例をいくつか見てみましょう。
および Neo4j が使用されているプロジェクト (既知のもの)
それ以外の場合は、レコメンダー アルゴリズムがグラフに適しています。たとえば、PageRank などを参照してください。
問題のドメインオブジェクトをノードに定義できる場所ならどこでもグラフを利用でき、ノード間の制御やデータのフローとしてソリューションを利用できます。
木が実際に有向非巡回グラフであるという事実を考慮すると、グラフ理論を使用できる領域はさらに多くあります。
データベース理論におけるトランザクションのシリアライゼーションの分析。
基本的に、ツリー、リスト、キューなどのほとんどすべての一般的なデータ構造は、グラフのタイプと考えることができ、いくつかは異なるタイプの制約を持ちます。
私の経験では、通信ネットワークのルーティングと 最適化、ワークロードの割り当て、マッチング、サプライ チェーンの最適化、公共交通機関の計画など、多くの分野で使用されるネットワーク フローの問題で集中的にグラフを使用してきました。
別の興味深い分野は、前の回答で述べたソーシャル ネットワーク モデリングです。
集積回路の最適化など、はるかに多くのものがあります。