状態空間探索

状態空間探索とは、初期状態から利用可能な行動を介して到達可能な状態の集合を体系的に探索し、目標テストを満たす状態またはそれに到達する経路を見つけることである。

Definition

状態空間探索は、問題をノードが状態でありエッジが行動であるグラフとして扱い、フロンティアから固定された戦略に従って状態を拡張し、目標状態が見つかるか空間が尽きるまで進行する。

Scope

このトピックでは、問題を状態空間（状態、行動、遷移モデル、目標テスト、経路コスト）として定式化する方法と、領域固有のガイダンスなしにそれを探索する非情報探索戦略（幅優先探索、一様コスト探索、深さ優先探索、深さ制限探索、反復深化探索）について扱う。これには、これらの戦略の完全性、最適性、時間計算量、空間計算量による分析、および繰り返し状態検出を伴う木探索とグラフ探索の区別が含まれる。ヒューリスティックなガイダンスは、ヒューリスティック探索とA*に関する別のトピックで扱われる。

Core questions

• 問題はどのように状態、行動、遷移モデル、および目標テストとして表現されるか？
• 幅優先探索、深さ優先探索、一様コスト探索、および反復深化探索は、フロンティアの順序付けにおいてどのように異なるか？
• 各非情報戦略の完全性、最適性、時間、および空間に関する保証は何か？
• グラフ探索は、木探索が許容する状態の無駄な再探索をどのように回避するか？

Key concepts

• 初期状態と目標テスト
• 遷移モデルと後続状態
• フロンティア（オープンリスト）と探索済み集合
• 幅優先探索
• 深さ優先探索
• 一様コスト探索
• 反復深化
• 木探索 vs. グラフ探索

Key theories

フロンティアの順序付けが戦略を決定する

非情報探索アルゴリズムは、フロンティアから状態を削除する順序によってのみ区別される。FIFOキューは幅優先探索を、LIFOスタックは深さ優先探索を、経路コストに基づく優先度キューは一様コスト探索をもたらす。

空間効率の良い最適解としての反復深化

深さ優先反復深化探索は、深さ制限付き深さ優先探索を制限を増やしながら繰り返し実行することで、深さ優先探索の線形空間と、幅優先探索の完全性および最適性（単位コストの場合）を組み合わせる。

Clinical relevance

非情報状態空間探索は、経路探索、パズル解決、モデル検査における到達可能性分析の概念的および実装上の基盤であり、ヒューリスティック探索や敵対的探索が構築される基盤でもある。その複雑さを理解することは、盲目的な探索が実行可能である場合とヒューリスティクスが必要とされる場合を判断するのに役立つ。

History

体系的な状態空間探索は、ムーアとダイクストラの最短経路研究を含む1950年代のグラフ走査アルゴリズムに由来し、初期のAIにおいて問題解決のモデルとして定式化された。Korfの1985年の反復深化に関する分析は、線形空間を持つ許容可能な木探索の中でその最適性を確立した。

Key figures

• Nils J. Nilsson
• Richard E. Korf
• Edward F. Moore
• Edsger W. Dijkstra

Seminal works

• nilsson1971
• russell2020

Frequently asked questions

幅優先探索はいつ最適か？

幅優先探索は、すべてのステップが同じコストを持つ場合に最適である。なぜなら、最も浅い目標を最初に見つけるからである。ステップコストが異なる場合、一様コスト探索（累積経路コストによってフロンティアを順序付ける）が、最小コスト解を保証する非情報戦略である。

単純な幅優先探索の代わりに反復深化を使用するのはなぜか？

幅優先探索はフロンティア全体を保存するため、深さに対して指数関数的なメモリを必要とする場合がある。反復深化は、深さ制限を増やしながら深さ優先探索を繰り返し実行することで、浅いノードを再拡張するコストを伴うものの、線形メモリのみを使用しながら、単位コスト問題に対して完全性と最適性を維持する。