
G検定受験note(10/25)【探索・推論①探索木②幅優先探索③深さ優先探索】
G検定の受験のためにつけた、文字通りのノートです。
Hermes Agent(Grok 4.7)に噛み砕いて解説してもらっています!(^^)v
AIは間違うので、活用は自己責任でお願いします!(^^;
探索・推論
探索は、答えを一行の条件で書けないとき、ありうる状態を順にたどることだ。迷路で、右か左かを人が全部書いていない。壁とゴールのルールだけがある。機械は、分かれ道を一つずつ試して、ゴールに着く道を見つける。
推論は、すでに持っている知識から、そこに書いていない結論を出すことだ。レシピに「砂糖はない」と書いてあれば、「この料理は甘くない」と言える。甘くない、とは材料欄に書いていない。持っている事実から、出てくる。
どちらも、知識やルールを書くのは人だ。機械は、その中をたどるか、そこから結論を出す。データから特徴を学ぶ話ではない。4つのレベルで言えば、2段目の古典的な人工知能だ。エアコンの if-then よりは進んでいる。スパムをデータから覚える段よりは、前だ。
探索木
芯は一つ。ありうる一手を、親子の木として残したものだ。答えの一覧ではない。
家を出たところを、根っこに置く。最初の角で右と左があるなら、枝は二本だ。右へ曲がったあとの場所が、子だ。その子の先で、また道が分かれる。ゴールや、行き止まりは、葉になる。迷路の地図そのものではない。右へ行った、左へ行った、という選択の記録だ。
壁のルールは、人が書く。機械は、その木をたどる。データから道を覚える話ではない。4つのレベルでは、2段目の古典的な人工知能だ。
ハノイの塔も、同じ形だ。円盤の今の置き方が、状態だ。一番上の円盤を、別の杭へ移すのが、一手だ。大きい円盤を、小さい円盤の上に置いてはいけない、がルールだ。ありうる置き方が、木になる。
決定木とは、別だ。探索木は、状態と一手の木だ。決定木は、データから答えを分ける木だ。問題が「状態を順にたどる」なら、探索木だ。
Exam Points
- 探索木は、開始状態を根にして、ルール上できる一手を枝、そのあとの状態を子にした木だ。
- 迷路の地図ではない。選択の記録だ。
- 合法な一手のルールは、人が書く。機械は、その中をたどる。
- ハノイの塔は、状態と一手で木になる例だ。
- 決定木と混ぜない。決定木は、データの分類に使う木だ。
幅優先探索
芯は一つ。今いる深さの分かれ道を、全部見てから、一つ先へ進む。一本の道を、先に奥まで行かない。
家の中を探すなら、1階の部屋を全部開けてから、2階へ上がる。右の廊下の奥へ、先に突っ込まない。今の階に、まだ見ていないドアがあるなら、そちらを先に開ける。
探索木では、根の子を、左から右へ全部見る。その子たちの子は、その次だ。浅い方を先に尽くす。だから、ゴールが浅いところにあれば、早く見つかる。手数の少ない道を探すときに、この順番が合う。未確認の枝を、たくさん覚えておくので、メモリは多く要る。
深さ優先探索は、別の順番だ。一本を、行き止まりまで先に降りる。今回の芯は、幅だ。深さは、次の一塊にする。
Exam Points
- 幅優先探索は、同じ深さの状態を全部調べてから、次の深さへ進む。
- 近い方、手数の少ない方を、先に見る。
- ゴールが浅いなら、早く見つかる。最短の手数を保証しやすい。
- 未確認の枝を広く覚えるので、メモリを多く使う。
- 深さ優先探索と混ぜない。深さは、一本を先に奥まで行く。
深さ優先探索
芯は一つ。一本の枝を、行き止まりまで先に降りる。同じ深さの枝を、先に全部は見ない。
家の中なら、1階の左のドアを開けたら、その奥の部屋、そのまた奥まで行く。行き止まりに着いてから、一つ戻って、隣のドアを試す。1階の全部を見てから2階へ、ではない。奥まで行って、戻る。この戻りが、バックトラックだ。
探索木では、左の子を選び、その左の子を選び、葉まで降りる。葉がゴールでなければ、一つ親へ戻って、まだ見ていない枝を試す。覚えているのは、今降りてきた一本と、戻り先だ。幅優先探索のように、同じ階の未確認を全部並べておかなくてよい。その代わり、ゴールが浅い右側にあっても、左の深い無駄道を先に歩き得る。手数の少なさを、この順番は保証しない。
幅優先探索は、今の深さを全部見てから次へ進む。深さ優先探索は、一本を先に尽くす。問題が「最短の手数」なら、幅の方が合いやすい。問題が「とにかく一本、奥まで確かめる」なら、深さだ。
Exam Points
- 深さ優先探索は、一つの枝を行き止まりまで進めてから、隣の枝へ戻る。
- 戻る操作を、バックトラックと呼ぶ。
- 同じ深さの状態を、先に全部は見ない。
- 未確認を広く並べないので、幅よりメモリを抑えやすい。最短の手数は、保証しない。
- 幅優先探索と混ぜない。幅は、同じ深さを全部見てから、一つ先へ進む。