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

7.9

 

A*

探索

■

239

A

I

図7-25　15 パズルの複雑な初期盤面

7.9.5

 変形

初期状態から前方に探索を進めるだけでなく、

Kaindl and Kainz

（

1997

）は、同

時に目標状態から後方へ探索するように拡張したアルゴリズムを提案している。こ

の方式は、初期の

AI

研究者によって、うまく動かないとして当初否定されたのだが、

Kaindl

と

Kainz

は、この方式を再度考慮すべきであると強力に論じている。

A*

探索

の強力な代替方式としては、反復深化（

IterativeDeepening

）

A*

、すなわ

ち

IDA*

がある（

Reinefeld, 1993

）。これは、ある固定したコスト内で、

深さ優先探

索

を順に展開していく。各反復段階で、その直前の結果に基づいてコストの限界を

増やす。見積もられたコストが、ヒューリスティックな値ではなく、実際の手に基

づいているので、

IDA*

は、

幅優先探索

や

深さ優先探索

単独よりもずっと効率的であ

る。

Korf

（

2000

）は、

IDA*

と組み合わせるとヒューリスティックな手法がどれだ

け強力になるかを、

15

パズルを例に記述している。これは、探索過程で

4

億以上の

盤面状態を評価することにより、ランダムな例を解いている。

A*

探索

は、最小コスト解を生成するが、探索空間が大きすぎて完了できない可能

性がある。

A*

探索

を強化して、このような巨大問題を解くためのアイデアとして、

次のようなものがある。

反復的深化

この状態探索戦略は、

深さ優先探索

を反復適用し、各段階ごとに深さ限

界を