木探索グラフ探索

ウィキペディア小見出し辞書

木探索・グラフ探索

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/04/15 03:07 UTC 版)

「探索」の記事における「木探索・グラフ探索」の解説

木探索・グラフ探索共通 幅優先探索 深さ優先探索反復深化深さ優先探索 深さ制限探索 均一コスト探索 双方向探索 グラフ探索固有 最短経路問題ダイクストラ法 ベルマン-フォード法 最小全域木プリム法 クラスカル法 最大フロー問題・最小カット問題フォード・ファルカーソンのアルゴリズム エドモンズ・カープのアルゴリズム 巡回セールスマン問題最近傍法 連結度最大隣接順序 最小次数順序 木探索（英: tree search）アルゴリズムは、探索技法の中心である。木のノードを探索するもので、最初から木が明示される場合と動的に木を生成する場合がある。基本原則は、データ構造から1つのノードを選び、その後者を調べてデータ構造に追加していく。このデータ構造の操作にあたっては、同じレベルのノードから順に見ていく幅優先探索と葉ノードまで見ていってバックトラックする深さ優先探索がある。 グラフ理論の問題の多くは、グラフ探索アルゴリズムで解くことができる。いくつかの物は木探索アルゴリズムを拡張したものと見ることもできる。