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