探索問題

俺用メモ。リンク先は ja.wikipedia.org

• 探索問題 search problem
  • 探索木 search tree
  • 探索グラフ search graph
• 網羅的探索方 brute-force search
  • 解の質 quality of solution
  • 最適解 optimal solution
  • 縦型探索法 (深さ優先探索法) depth-first search
    • 縦型反復深化法 depth-first iterative-deepening
    • バックトラック backtrack
  • 横型探索法 (幅優先探索法) breadth-first search
    • 両方向横型探索法 bi-derectional breadth-first search
• 発見的探索法 heuristic search
  • 最良優先探索 best-first search
    • 発見的関数 heuristic function
  • A* アルゴリズム A* algorithm
    • 反復深化A*アルゴリズム interative-deepening A* algorithm
    • ダイクストラ法 dijkstra's algorithm
      • 均一コスト探索 uniform-cost search
    • マンハッタン距離
  • 局所探索法 local search
    • 山登り法 hill climbing
    • 焼きなまし法 simulated annealing
    • タブーサーチ tabu search
  • ビーム探索法 beam search
• ゲームにおける探索法
  • ゲーム木 game tree
  • 組合わせ的爆発 combinatorial explosion
  • ミニマックス法 mini-max method
  • アルファ・ベータ法 alpha-beta method
    • アルファ・ベータ枝刈り alpha-beta pruning