♪この章の曲三度目の正直ブーム!
サビで覚えて、下の会話で回収
#1ちがうのは、調べる順番

今日は「探索」のやり方! 迷路を解く順番にも、種類があるの?

…ある。代表は「幅優先探索」と「深さ優先探索」。

…どちらも、ありえる道を漏れなく調べるやり方。ちがうのは、調べる順番。

デートコースを全部ちょっとずつ回るか、1つを極めるか、みたいな?♡

…たとえとしては、悪くない。
- 1初期状態(スタート)
- 2オペレータ(とれる行動)
- 3ゴール検査(ゴールかどうかの判定)
- 4経路コスト(道のりの重さ)
#2幅優先探索:近いところから全部

…幅優先は、スタートに近いところから、一段ずつ全部見ていく。

1手で行ける場所を全部、次に2手で行ける場所を全部…ってこと?

ルナも、まわりのお店を近い順に全部のぞく派♡

…そう。だから、いちばん浅い(手数が少ない)ゴールを必ず見つける。

最短が見つかるなら、最強じゃん!

…弱点はメモリ。調べる途中の候補を全部覚えておくから、深い問題では足りなくなる。
#3深さ優先探索:1本の道を奥まで

…深さ優先は、1本の道を行けるところまで進む。行き止まりなら、1つ戻って別の道。

一途…♡ ルナのタイプ

…覚えておく候補が少ないから、メモリは少なくてすむ。

じゃあ、深さ優先の弱点は?

…最初に見つけたゴールが、最短とは限らない。道が無限に続くと、戻ってこないことも。

一途すぎて、帰ってこない…重い♡

それ、ルナのことじゃん!
| 幅優先探索 | 深さ優先探索 | |
|---|---|---|
| 調べ方 | 近い順に一段ずつ | 1本の道を奥まで |
| 最も浅い答え | 必ず見つかる | 見つかるとは限らない |
| メモリ | たくさん使う | 少なくてすむ |
| 候補の並べ方 | キュー(先に入れた順) | スタック(後に入れた順) |
#4「最短」って、何の最短?

じゃあ、地図の道案内も、幅優先なら最短ルート?

…幅優先の「最短」は、手数がいちばん少ない、という意味。

え、距離じゃないの!?

近道だと思ったら遠回り…恋もそう♡

…道の長さがバラバラなら、長さ(経路コスト)を考える、別の探索のしかたが要る。

…ちなみに、力まかせに全部試すやり方は「ブルートフォース」とも呼ぶ。

「ハノイの塔」も、こうやって探索で解けるのよね♡

円盤3枚なら、最短7手! 覚えた!
ミコのメモ(自分あて)
- 幅優先探索=スタートに近い順に一段ずつ調べる既読
- 幅優先は最も浅い答えを必ず見つけるがメモリを食う既読
- 深さ優先探索=1本の道を奥まで進み、だめなら戻る既読
- 深さ優先は省メモリだが、最短とは限らない既読
試験デンデン! 1問だけ
必要なメモリが少なくてすむ一方で、最初に見つかる答えが最短とは限らない探索のしかたは?
1本の道を奥まで進む深さ優先探索は、覚えておく候補が少なくメモリが少なくてすむが、最初のゴールが最短とは限らない。幅優先探索は最も浅い答えを必ず見つけるがメモリを多く使う。Mini-Max法はゲームで相手の最善手も考えて手を選ぶ方法、モンテカルロ法はランダムな試行をくり返して評価する方法。
※ 出題範囲を参考にしたオリジナル問題です
この記事の出典
- 北海道大学OCW「知能情報処理 探索(2)しらみつぶしの探索」(幅優先・深さ優先の性質)
- 総務省「令和6年版 情報通信白書」第1〜3次AIブームと冬の時代(探索・探索木)
- Wikipedia「Breadth-first search」
- JDLA「G検定とは」(シラバス)
ここでの「最短」は、1手ごとのコストがすべて同じ(手数で測る)場合の話です。
G検定(JDLA ジェネラリスト検定)のシラバス2024(第1.4版)をもとにした非公式の学習コンテンツです。JDLAとは関係ありません。 登場人物は架空のキャラクターです。