学習アルゴリズム

第7章 グラフ グラフ接続する！

この作品はAIを使って翻訳されている。ご意見、ご感想をお待ちしている：[e-mail]

この章では、次のことを学ぶ：

• スタック抽象データ型。

• インデックス付き最小プライオリティ・キュー・データ型であり、本書に含まれる最後のデータ型である。

• ノードとエッジを使ってグラフをモデル化する方法。有向グラフでは、辺は方向を持つ。重み付きグラフでは、辺は関連する数値を持つ。

• デプスファーストサーチは、グラフ内の検索を整理するためにスタックをどのように使うか。

• Breadth First Searchはどのようにキューを使ってグラフを検索するのか。ソース・ノードとターゲット・ノードの間にパスが存在する場合、Breadth First Searchは存在する最短パスを返す。

• 有向グラフにサイクルが含まれているかどうかを検出する方法：特定のノードから始まり、特定のノードで終わる辺のシーケンス。

• 有向グラフのトポロジカル・ソートを使用して、有向グラフのすべての依存関係に適合するノードの線形ソートを生成する方法。

• あるノードから他のすべてのノードまでの、重み付きグラフにおける最短の累積パスを決定する方法。

• 重み付きグラフの任意の2ノード間の最短累積パスを決定する方法。

グラフは有用な情報を効率的に保存する

これまで、情報システムにおけるデータストアやデータ処理に関する一般的な問題を解決するアルゴリズムについて説明してきた。これらのアルゴリズムは、問題を適切にモデル化することさえできれば、数え切れないほどの現実の問題を解決することができる。ここでは、そのような問題をグラフを使って3つ解決する：

• 迷路は、他の部屋に通じる出入り口のある部屋で構成されている。入り口から出口までの最短パスを発見する。

• プロジェクトはタスクの集合体として定義されるが、タスクの中には、開始前に他のタスクの完了が必要なものもある。プロジェクトを完成させるために、タスクをどのような順番で実行すればよいかを記述したリニアスケジュールを組み立てる。

• マッピングには、高速道路の区間とその長さ（マイル）が含まれている。地図上の任意の2地点間の最短移動距離を発見せよ。

これらの問題はそれぞれ、何世紀にもわたって数学者が研究してきた基本概念であるグラフを使って効果的にモデル化することができる。データ間の関係をモデル化することは、しばしばデータ値そのものと同じくらい重要である。グラフは、情報を辺で結ばれたノードとしてモデル化する。図7-1に見られるように、グラフはさまざまな応用領域の概念をモデル化できる。無向グラフは、プロパン分子の炭素原子と水素原子の構造関係をモデル化できる。モバイルアプリは、一方通行の道の向きを有向グラフとして表現することで、ニューヨークの道案内を提供できる。ドライバー用の道路地図は、イギリス各州の州都間の走行距離を重み付きグラフで表すことができる。少し計算すれば、コネチカット州ハートフォードからメイン州バンゴールまでの最短運転距離が278マイルであることがわかる。

グラフは、N個の異なるノードの集合を含むデータ型であり、各ノードにはノードを識別するための一意のラベルが付けられている。¹グラフに辺を追加して、2つの異なるノードuと vを互いに接続することができる。 辺は(u,v)として表現され、uと vはそのエンドポイントと呼ばれる。各辺(u,v)はuと ...