↑: [[Mini-Max法]] [[G検定に関する知識|G-exam]] - [[TODO]] - 種類：[[幅優先探索]]、[[深さ優先探索]]、A*探索、[[Mini-Max法]]、[[αβ法]]、[[モンテカルロ法]] - **A*探索**：評価関数 f(n)=g(n)+h(n)（スタートからの実コスト＋ゴールまでの推定コスト）が最小のノードを優先展開するベスト優先探索 - 最適解（最短経路）の保証には h が実コストを**過大評価しない**「許容性」が必要。過大評価すると最適性が崩れる ← 重要 - h≡0ならダイクストラ法と同等。コストが均一なグラフではさらに幅優先探索と同等 - hが真のコストに近いほど展開ノード数が減り効率的 - **ハノイの塔**：n枚で最低2ⁿ−1手、状態数は3ⁿで**有限**。探索空間の指数的増大を示す代表例。再帰で最適解が決定的に求まる（モンテカルロ法は不要、二人零和ゲーム用のαβ法は適用対象外）