探索 木探索・グラフ探索

ウィキペディア

探索

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/01/15 02:36 UTC 版)

木探索・グラフ探索

木探索・グラフ探索共通

• 幅優先探索
• 深さ優先探索
  • 反復深化深さ優先探索
  • 深さ制限探索
• 均一コスト探索
• 双方向探索

グラフ探索固有

• 最短経路問題
  • ダイクストラ法
  • ベルマン-フォード法
• 最小全域木
  • プリム法
  • クラスカル法
• 最大フロー問題・最小カット問題
  • フォード・ファルカーソンのアルゴリズム
  • エドモンズ・カープのアルゴリズム
• 巡回セールスマン問題
  • 最近傍法
• 連結度
  • 最大隣接順序
  • 最小次数順序

木探索（英: tree search）アルゴリズムは、探索技法の中心である。木のノードを探索するもので、最初から木が明示される場合と動的に木を生成する場合がある。基本原則は、データ構造から1つのノードを選び、その後者を調べてデータ構造に追加していく。このデータ構造の操作にあたっては、同じレベルのノードから順に見ていく幅優先探索と葉ノードまで見ていってバックトラックする深さ優先探索がある。

グラフ理論の問題の多くは、グラフ探索アルゴリズムで解くことができる。いくつかの物は木探索アルゴリズムを拡張したものと見ることもできる。

知識を用いた探索

知識を用いた探索（英: informed search）では、問題に固有のヒューリスティクス（評価関数）を補助として使う。良いヒューリスティックを使えば、探索は劇的に改善される。 知識を用いた探索アルゴリズムの多くは木探索である。最良優先探索や A* などがある。知識を用いない探索と同様、これらはグラフ向けにも拡張可能である。

• 局所探索法・山登り法
• 最良優先探索
• A*

メタヒューリスティクス

汎用的に使えるヒューリスティクスをメタヒューリスティクスという。

• 焼きなまし法 - 確率的探索アルゴリズムの一種
• タブーサーチ - 探索が局所解で停滞するのを防ぐ技法
• 遺伝的アルゴリズム - 探索空間を縮小させるヒューリスティクスとして進化の考え方を使う。
• 蟻コロニー最適化
• 粒子群最適化

連想配列

問題に関する知識に基づいてハッシュ関数を定義したハッシュテーブルは知識を用いたリスト探索アルゴリズムである。

敵対探索

• ミニマックス法
• アルファ・ベータ法
• 分枝限定法
• NegaScout
• MTD(f)

チェスのようなゲームでは、考えられる全ての「手」で構成されるゲーム木があり、この木を使って最良の手を捜すことができる。この種の問題は、相手も自分にとって最良の手を選択すると想定するという興味深い特徴がある。そのため、ゲームを行う人工知能などでは、ミニマックス法、探索木の刈り込み、アルファ・ベータ法といった特徴的な探索アルゴリズムを使う。