AI第1次ブーム「探索・推論」①

AIの探索・推論の仕組み・動向について。

全体像

1. 迷路（探索木）
2. ハノイの塔
3. ロボットの行動計画
4. ボードゲーム
5. モンテカルロ法

迷路（探索木）

迷路のような問題を、まずは「コンピュータで処理できるような形式に変換する」必要があります。

1. 行き止まりと分岐に記号を付与する
2. 迷路の枠を外す

そうすると、上記のような形式になります。

これを上から順番に並べていくと、「ツリー構造」になり、突き詰めると「場合分け」ということになり、この場合分けを探索していくことによりいずれゴールにたどりつくということです。

この場合の探索の手法としては、以下が考えられます。

ハノイの塔

「ハノイの塔」というパズルを解いていきます。

まずは「コンピュータで処理できるような形式に変換する」必要があるため、それぞれの部品に「１」「２」「３」「P」「Q」「R」と記号を付与します、

そうすることで、「探索木」のようにツリー上の「場合分け」をすることができ、解いていくことができるようになります。