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