G検定 第2章|人工知能をめぐる動向

探索アルゴリズム(幅優先探索と深さ優先探索)

迷路の解き方にも、性格があるの?

会話で読んで3分

探索木幅優先探索深さ優先探索ブルートフォースハノイの塔

♪この章の曲三度目の正直ブーム!

サビで覚えて、下の会話で回収

#1ちがうのは、調べる順番

ミコ

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

シオン

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

シオン

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

ルナ

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

シオン

…たとえとしては、悪くない。

探索問題を決める4つの情報
  1. 1初期状態(スタート)
  2. 2オペレータ(とれる行動)
  3. 3ゴール検査(ゴールかどうかの判定)
  4. 4経路コスト(道のりの重さ)

#2幅優先探索:近いところから全部

シオン

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

ミコ

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

ルナ

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

シオン

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

ミコ

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

シオン

…弱点はメモリ。調べる途中の候補を全部覚えておくから、深い問題では足りなくなる。

#3深さ優先探索:1本の道を奥まで

シオン

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

ルナ

一途…♡ ルナのタイプ

シオン

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

ミコ

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

シオン

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

ルナ

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

ミコ

それ、ルナのことじゃん!

幅優先探索と深さ優先探索
幅優先探索深さ優先探索
調べ方近い順に一段ずつ1本の道を奥まで
最も浅い答え必ず見つかる見つかるとは限らない
メモリたくさん使う少なくてすむ
候補の並べ方キュー(先に入れた順)スタック(後に入れた順)

#4「最短」って、何の最短?

ミコ

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

シオン

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

ミコ

え、距離じゃないの!?

ルナ

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

シオン

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

シオン

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

ルナ

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

ミコ

円盤3枚なら、最短7手! 覚えた!

ミコのメモ(自分あて)

試験デンデン! 1問だけ

必要なメモリが少なくてすむ一方で、最初に見つかる答えが最短とは限らない探索のしかたは?

※ 出題範囲を参考にしたオリジナル問題です

この記事の出典

ここでの「最短」は、1手ごとのコストがすべて同じ(手数で測る)場合の話です。

G検定(JDLA ジェネラリスト検定)のシラバス2024(第1.4版)をもとにした非公式の学習コンテンツです。JDLAとは関係ありません。 登場人物は架空のキャラクターです。

第2章のレッスン

  1. 第1次AIブーム(推論・探索の時代)
  2. 第2次AIブームとエキスパートシステム
  3. 探索アルゴリズム(幅優先探索と深さ優先探索)
  4. 知識表現(意味ネットワークとオントロジー)
  5. 機械学習と第3次AIブーム
  6. ディープラーニングの登場