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

7.6

 探索木

■

219

A

I

インタフェース

INodeSet

は、

INode

集合の基盤実装を抽象化する。アルゴリズ

ムによっては、

INode

オブジェクトのキューを要求するが、スタックや平衡二分木

を用いるものもある。クラス

StateStorageFactory

を用いて適切に構成すれば、提

供された演算で、アルゴリズムは

INode

集合の状態を操作できる。インタフェース

IMove

は、手が盤面状態をどう操作するかを定義する。手のクラスが具体的にどう

なるかは、問題によって決まり、探索アルゴリズムは、実装の詳細を気にしなくて

よい。

プログラミングの観点からは、探索木での経路探索アルゴリズムの核心は、例

7-5に示すインタフェース

ISearch

の実装にある。これによって、解が得られれば、

その解に至る手順を構築することができる。

例

7-5

 探索木経路発見の共通インタフェース

/*

*

初期状態に対して、最終状態に至るまでの解を返す。

*

経路が見つからないなら、

null

を返す。

*/

public interface ISearch {

Solution search (INode initial, INode goal);

}

盤面の初期状態と目標状態とが与えられると、

ISearch

実装は解を表す経路を計

算する。解が見つからなければ

null

を返す。ゲーム木との違いを明らかにするため、

探索木の節点には、盤面状態（

board state

）という用語を使う。

7.6.1

 経路長のヒューリスティック関数

盲目探索ア