AI用語集
人工知能の完全辞典
幅優先探索 (BFS)
グラフ探索アルゴリズムで、ノードをレベルごとに探索し、キューを使用して開始点から到達可能なすべての頂点を体系的に訪問する。
深さ優先探索 (DFS)
各分岐を可能な限り深く探索してからバックトラックする再帰的な探索技術で、通常はスタックまたは再帰を使用して実装される。
ダイクストラ法
負でない重みを持つ重み付きグラフにおいて、ソース頂点から他のすべての頂点への最短経路を決定する貪欲アルゴリズム。
A*アルゴリズム
ヒューリスティックと実際のコストを組み合わせ、評価関数f(n) = g(n) + h(n)を使用して探索を効率的に導く最適経路探索アルゴリズム。
ベルマン・フォード法
負の重みサイクルを検出できる最短経路アルゴリズムで、すべての辺を反復的に緩和して最小距離を伝播させる。
フロイド・ワーシャル法
各頂点を中間点として順番に考慮し、すべての頂点ペア間の最短経路を計算する動的計画法アルゴリズム。
双方向探索
ソース頂点と宛先頂点から同時に2つの探索を実行し、それらが交差するまで続けることで経路探索を最適化する技術。
トポロジカルソート
各辺u→vがuが最終的な順序でvの前に現れるという制約を尊重する、有向非巡回グラフの頂点の線形順序付け。
タルジャンのアルゴリズム
番号付けとスタックを使用した深さ優先探索を用いて、有向グラフの強連結成分を特定する線形アルゴリズム。
強連結成分
同じサブグラフ内のすべての頂点から有向経路で到達可能な、極大なサブグラフ。
関節点
削除するとグラフの連結成分の数が増加する頂点で、番号付けを伴う深さ優先探索アルゴリズムによって特定される。
グラフの橋
削除すると連結成分の数を増やしてグラフを分割する重要なエッジで、特殊化された深さ優先探索によって検出される。
コサラジュのアルゴリズム
2回の深さ優先探索を使用して有向グラフの強連結成分を特定する2段階のアルゴリズム。
深さ制限探索
探索の深さを事前定義された制限に制約するDFSの変種で、深いグラフでの組み合わせ爆発を回避する。
反復深化深さ優先探索
深さを増やしながら一連の深さ制限探索を実行することで、BFSとDFSの利点を組み合わせる検索戦略。
ジョンソンのアルゴリズム
重み付けされたスパースグラフですべての頂点対間の最短経路を見つける効率的なアルゴリズムで、ダイクストラ法とベルマン-フォードの再重み付けを組み合わせる。
ユニフォームコスト探索
ヒューリスティックなしで累積コストが最小のノードを探索するダイクストラ法の変種。正のコストを持つグラフにおいて最適性を保証します。
オイラー閉路
各辺をちょうど1回だけ通過する経路。連結グラフにおいて、すべての頂点の次数が偶数である場合にのみ存在します。
ハミルトン閉路
各頂点をちょうど1回だけ訪問する経路。存在に関する単純な必要十分条件のないNP完全問題です。