aoj

探索戦略

評価基準

  • 完全性
    • 必ず解を見つけられるか?
  • 最適性
    • 最小経路コストの解を最初に見つけられるか?
  • 時間計算量
    • 解を見つけるための時間計算量
  • 空間計算量
    • 必要なメモリの量

分類

  • 盲目的
    • 知識なしの探索
  • ヒューリスティック
    • 知識に基づく探索

盲目的探索

  1. 幅優先探索(BFS)
  2. 深さ優先探索(DFS)
  3. 反復深化探索(ID)

幅優先探索

方法

  • ノード展開時にゴール判定する
  • 未展開のノードのうち最も浅い位置にあるノードを展開する
  • FIFOキュー

評価

  • 完全性
    • すべての解を見つける
  • 最適性
    • 最も浅いゴールを見つける
  • 時間計算量
    • 深さに応じて指数的に増加
    • 展開したノード
  • 空間計算量
    • 同上
    • 同時に必要なノード