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

234

■

7

章 

AI

における経路探索

7.9.3

 解

A*

探索

は、評価関数が最小のものを効率的に取り出し、特定の盤面状態のものが

存在するか効率的に判定できるような形でオープンな盤面状態を貯える。例7-8に、

Java

実装の例を示す。

例

7-8

 

A*

探索の実装

public Solution search(INode initial, INode goal) {

//

初期状態から始める。

int type = StateStorageFactory.PRIORITY_RETRIEVAL;

INodeSet open = StateStorageFactory.create(type);

INode copy = initial.copy();

scoringFunction.score(copy);

open.insert(copy);

//

ハッシュ表を用いて、既に訪問した状態を保持する。

INodeSet closed = StateStorageFactory.create(StateStorageFactory.HASH);

while (!open.isEmpty()) {

//

最小評価関数を持つ節点を取り除き、クローズ集合に移す。

INode best = open.remove();

//

目標状態に到達していたら終了する。

if (best.equals(goal)) { return new Solution (initial, best); }

closed.insert(best); ...