探索の定式化

探索問題の例


このパートでは以下の例のような離散的 (discrete)な探索問題を扱う．

• 経路探索
• パズル: 8パズル，15パズル，覆面算，ジグソーパズル，迷路など
• ゲーム: 囲碁，将棋，オセロなど
• 数学の問題: 因数分解，不定積分，幾何の証明など



離散的な探索問題の性質


1. 問題の解候補は離散的で数え上げることが出来る．

2. 解候補が与えられたとき，それが解かどうかを判定するアルゴリズムが ある．

探索の基本スキーマ


生成検査法 (Generate and Test)

repeat x ← < 次の解候補を生成 > until < xが解である >

状態空間探索


定義

given 状態集合S 初期状態 s0 ∈ S 状態に関する述語 P: S → {T,F} 基本操作の集合 O = {oi | oi(s) = f, s, f ∈ S} find P(ojn(・・・(oj1(s0))・・・)) = T を満足する 系列 [ojn, ...., oj1] (但し，oji ∈ O)

その他の重要な概念

経路[n_i, ...,n_j]: ノー ドn_iが表す状態からはじめて，適当な操作の適用によりノード n_jが表す状態に到達出来ることを意味する．経路中のノード数 m とした場合，m-1 を経路の長さと言う．

操作コストc(o): 操作oのコスト(整数もしくは 実数)を求める関数．

経路コストC(p): 経路 p のコストを求める関数． 経路 p (=[n_i, ...,n_i+k] を実現する操作列を [o₁,o₂, ... ,o_k]とした場合， C(p) は以下のように定義される．

        k
C(p) =  Σc(oi)
       i = 1

8パズルの場合の解釈


状態集合: 可能な盤面

初期状態: 可能な盤面のうちの一つ．任意に与えられる．

目標状態: 整った状態

基本操作: 空白を上下左右のうちの一方向に動かす(高々4通り)

探索木


探索問題は状態をノード(node)，基本操作をエッジとするグラフによって表現可能．

---

...Return

• 講義ノートインデックス