ヒューリスティック関数

再び状態空間探索


定義

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/15パズルでは動かすタイルの数が最小となる系列．これはどのよう にすれば見つかるのか?

経路コストは実際の操作系列を与えなければ計算が出来ない．

では，全ての可能な操作系列に対して経路コストを計算しなければ， 経路コスト最小の解は見つからないのか?

探索途中のノードn_iのコスト


探索過程において発見されたノードn_iについて，初期ノード からそのノードn_iを経由して目標ノードに至る経路のコストを， ノードn_iのコストとよび，f(n_i)で表記する．

このとき，f(n_iは以下のように表現できる．

f(ni) = g(ni) + h(ni)

と書くことが出来る．ただし，g(n_i)は初期ノードn₀か らn_iまでの経路の最小コスト，h(n_i)はn_i から目標ノードまでの最小コスト．

g(n_i)の計算
探索の過程でn_iを展開している時はn₀から n_iまでの経路はわかるのでg(n_i)の値はコスト関数の 計算により求まる．

h(n_i)の計算
n_i以降のノードはまだ調べてないのでh(n_i)の値は計 算のしようがない．

ヒューリスティック関数


h(n_i)の値を厳密に求める代わりに，n_iがどのく らい目標状態ノードに近いか(どのくらい好ましいか)を数値化して表現したい．

別に言い方をすれば，ノードnの状態からゴール状態ま での最短経路の見積もりコストを求めたい．

この数値化する手法は，個々の問題に依存し，かつ発見的な知識を必要とし， よって定式化は難しく，多くの場合経験的な数値である．

このような知識をヒューリスティクス (heuristics: 発見的知識)と呼び，それにもとづき前述の h(n_i)の近似値を与えてくれる関数h'(n_i)をヒューリスティック関数と呼ぶ．ただし，h'の値は非負でなければならない．

ルーマニアの地図の例

また，ヒューリスティック関数を用いた探索戦略を発見的探索(heuristic search)，もしくは知識を用いた探索(informed search)と呼ぶ．

楽観的，もしくは許容的ヒューリスティック


ヒューリスティック関数が目標までの実際のコストを決して超えない値を返す場合，それは楽観的，もしくは許容的(admissible)ヒューリスティ クスという(A*探索で重要となる概念)．

---

...Return

• 講義の詳細