メディア チェック 2002/07/10ニュースリリース資料付録「探索問題についての解説」 一般向け解説 人工知能における探索問題 簡単な例として， 2 行 2 列からなる箱根細工の問題について考えてみましょう。図のように，赤・青・黄の 3 個の駒が置かれており，空白が 1 個あるとします。左の状態から出発して右の状態に到達するためには，どの駒をどのような順番で動かせばよいでしょうか。 次の図におけるレベル 0 の状態すなわち頂点が，出発の状態です。もし黄色の駒を下へ動かすとレベル 1 の左の状態となり，もし赤を右へ動かすとレベル 1 の右の状態となります。ここに，レベル数は，出発の時点から駒を動かした手数をあらわします。以下，同じ要領で駒を一手ずつ動かしたときの到達可能な状態を調べます。 レベル 3 は，三手動かしたときに到達可能な状態ですが，このうち左から 3 番目の状態は，最終目標の状態になっています。したがって，出発状態から初めて，最初に黄
