アルゴリズムクイックリファレンス 第2版

7.9

 

A*

探索

■

231

A

I

なぜなら、

g(n)

は、各盤面状態をその初期状態からの深さとともに記録していれば、

途中でも計算可能だからである。

h(n)

が、有望な盤面状態と有望でない盤面状態を

正確に区別できないなら、

A*

探索

は、既に記述した盲目探索より優れた性能を発揮

できない。しかし、適格（

admissible

）で効率的に計算可能な効果的

h(n)

を決定す

ることは難しい。必ずしも最適ではないが、実用的な解に到達する不適格な

h(n)

の

例が多数ある。

7.9.1

 入出力

アルゴリズムは、探索木の初期盤面状態と到達すべき目標状態から始まる。適格

な

h(n)

関数を持つ評価関数

f(n)

があるものと仮定する。このアルゴリズムは、初期

状態から目標状態への、最小コストに非常に近い近似解をとなる一連の手を返す（ま

たは、既存の資源ではそのような解が見つからなかったと宣言する）。

7.9.2

 文脈

図7-20の盤面から始める

8

パズルの例を用いて、

2

つの探索木の計算を図 7-21と

図7-22に示す。図7-21は、

Nilsson

（

1971

）が提案した

GoodEvaluator

関数

f(n)

を

用いる。図 7-22は、同じく

Nilsson

が提案した

WeakEvaluator

関数

f(n)

を用いる。

これらの評価関数についてはすぐ後で説明する。薄い灰色の盤面状態は、目標が見

つけられたときのオープンな集合を示す。

図7-20　A* 探索の開始盤面状態

232

■

7

章 

AI

における経路探索

A*

探索

[GoodEvaluator] ...