【疑問】幅優先探索と深さ優先探索、どっちが速いん？ハノイの塔とSTRIPSも出てきて混乱【G検定】

第1次AIブームの「探索」って、具体的には何をしてたん？
幅優先と深さ優先の違いも、どっちを使えばええかも分からん

前提のおさらい。第1次ブーム（1950年代後半〜1960年代）は、迷路やパズルのようにルールとゴールがはっきりした問題を、手順を探索して解いた時代

＞＞1
探索では、スタートから選べる手を枝分かれさせた「探索木」を作る
迷路なら、分かれ道のたびに枝が分かれて、ゴールの地点が見つかるまで木をたどる

＞＞3
幅優先探索は、スタートに近い段から順に、同じ深さを全部調べてから次の深さへ進む
深さ優先探索は、1本の枝を行けるところまで進んで、行き止まりなら1つ戻って別の枝へ

＞＞4
で、どっちがええの？

＞＞5
一長一短
幅優先：浅い順に調べるから、最短の手順が必ず見つかる。ただ、途中の段をすべて覚えておくからメモリをたくさん使う
深さ優先：今たどっている枝だけ覚えればいいからメモリは少なくて済む。ただ、最初に見つかった答えが最短とは限らない

＞＞6
メモリをたくさん使うって、どれくらい？

＞＞7
1つの点から3本ずつ枝が出るとすると、深さ $d$ の段にある点の数は

深さ5なら

幅優先はその段を全部覚えて進む。深さ優先は今たどっている5個ほどで済む

ハノイの塔も探索の例でよく出る
3本の棒と大きさの違う円盤があって、小さい円盤の上に大きい円盤は置けない。全部を別の棒に移す

＞＞9
円盤が $n$ 枚のとき、最小の手数を $T(n)$ とすると、上の $n-1$ 枚をよけて、いちばん大きい円盤を動かして、また $n-1$ 枚を戻すから

これを解くと

3枚なら $2^3-1=7$ 手、10枚なら $1023$ 手

＞＞10
枚数が1枚増えるだけで手数がほぼ倍か。第1次ブームが現実の問題で行き詰まったのも分かる気がする

＞＞1
シラバスで一緒に出てくるのがプランニング
ロボットの行動計画を、「前提条件」「行動」「結果」の組み合わせで書いて、ゴールまでの行動の並びを探索する考え方

＞＞12
STRIPS はそれ？

＞＞13
そう。STRIPS はスタンフォード研究所（SRI）のファイクスとニルソンが1971年の論文で示したプランニングのシステム
「箱を押す」なら、前提条件は「ロボットが箱の横にいる」、結果は「箱の位置が変わる」のように書く

SHRDLU も同じころ
テリー・ウィノグラードがMITで1968〜1970年に作ったシステムで、積み木の世界を英語の命令で動かせた
「赤い積み木を青い箱に入れて」みたいな指示を理解して、画面上の積み木を動かす

＞＞15
積み木の世界の中だけで動く、っていうのがまさにトイ・プロブレムやな

＞＞16
世界が小さくて決まりがはっきりしてるから、探索とプランニングでうまくいく。現実の世界はそうはいかない、というのが冬の時代につながる