|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ ー ： [ちょうおん] (n) long vowel mark (usually only used in katakana)
トポロジカルソート（）とは、グラフ理論において、有向非巡回グラフ（）の各ノードを順序付けして、どのノードもその出力辺の先のノードより前にくるように並べることである。有向非巡回グラフは必ずトポロジカルソートすることができる。 有向非巡回グラフのノードの集合に到達可能性関係 ''R'' (ノード ''x'' から ''y'' への(各辺の向きに逆行しない)経路が存在するとき、またそのときに限り ''xRy'' とする)を定めると、''R'' は半順序関係となる。トポロジカルソートとは、この ''R'' を全順序になるように拡張したものとみなせる。 == 例 == トポロジカルソートの典型的な利用例はジョブのスケジューリングである。トポロジカルソートのアルゴリズムはPERTというプロジェクト管理手法のスケジューリングのために1960年代初頭に研究が開始された。ジョブはノードとして表現され、XからYへの辺はジョブXが終了しなければジョブYを始められないということを意味する（例えば洗濯が完了しなければ服を乾燥機にかけられないなど）。ジョブをトポロジカルソートすると、ジョブに着手すべき順番がわかることになる。 コンピュータサイエンスでの利用例は、命令スケジューリング、表計算で式を変更したとき再計算が必要なセルの評価順序の決定、論理合成、Makefileで指定されたファイルのコンパイル順序の決定、リンカのシンボル依存関係の解決などがある。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「トポロジカルソート」の詳細全文を読む スポンサード リンク
|