幅優先探索と深さ優先探索の違い|第1次AIブームをG検定向けに解説
どーも、りけーこっとんです。
「幅優先探索と深さ優先探索、どっちがメモリを食うんだっけ?」「STRIPSとSHRDLU、名前が似ていて覚えられない」
このような、G検定の第1次AIブームの範囲で手が止まっている方はいないでしょうか?
この記事では、第1次AIブームの中心だった「探索・推論」を解説します。
探索木の用語、幅優先探索と深さ優先探索の違い、プランニングとSTRIPS、SHRDLUまで、試験で比べて問われるところを表にまとめました。
(2026年10月更新:G検定の現行シラバス(2024年第6回から適用)に合わせて内容を見直しました。)
この記事の要点
- 第1次AIブームは1950年代後半〜1960年代。探索・推論で迷路やパズルを解けるようになった
- 幅優先探索は最短経路が見つかるがメモリを多く使う。深さ優先探索はメモリが少なくて済むが最短とは限らない
- STRIPSはプランニング(自動計画)を「前提条件・行動・結果」で記述する言語
- SHRDLUはテリー・ウィノグラードが作った、積み木の世界を言葉で操作するシステム
手元に公式テキストが1冊あると、この記事で扱う用語をシラバスの言葉づかいのまま確かめられます。
深層学習教科書 ディープラーニング G検定(ジェネラリスト)公式テキスト 第3版
JDLA(日本ディープラーニング協会)監修の公式テキスト。用語の意味を正確に確かめたいときの辞書がわりになります。
|
|
この記事は、現行シラバスでは第2章「人工知能をめぐる動向」の「探索・推論」の範囲です(シラバスはJDLAの公式ページで確認できます)。G検定の範囲全体を一覧で見たい方はG検定チートシートもどうぞ。
この記事では、文字の装飾を次の3段階にそろえています。試験直前は赤太字だけ拾い読みしても要点がつかめます。
- 赤太字(超重要):試験で正解を決める決め手。年号・人物・数字・違いのポイント
- 青色マーカー+太字(重要):用語の定義。「〇〇とは」の一文
- 太字(覚えておきたい):あわせて覚えたい関連用語や覚え方
- これから勉強を始める方は → G検定とは?合格ライン・難易度・勉強法で、まず試験の全体像と勉強の進め方をつかめます
- 用語をサッと確かめたい方・試験当日が近い方は → G検定カンペ(チートシート)の分野別の用語一覧から、各解説記事にすぐ飛べます
- 紙で手元に置きたい方は → G検定カンペの印刷用PDF(無料・A4・15ページ)をダウンロードできます
第1次AIブームとは|推論・探索の時代
第1次AIブームとは、1950年代後半から1960年代にかけて、AIが急速に注目された期間のことです。
1956年のダートマス会議がその発端です。
機械によって、人間が考えるような問題(迷路やパズル、定理の証明など)を解けるようになったことが、ブームのきっかけのようですね。このときの中心技術が「探索」と「推論」でした。
しかし、第1次ブームの人工知能は複雑な問題は解けず、簡単な問題しか解けませんでした。
そこで、1970年代には注目度合いが衰えてしまったと言われています(最初の「冬の時代」)。ダートマス会議についてはAIの歴史の記事で解説しています。
探索木とは
探索木とは、問題を解く途中の状態を、木の枝のように場合分けして表したものです。
例えば迷路なら、分かれ道に来るたびに「右に行く」「左に行く」と枝分かれしていきますよね。この枝分かれを図にすると、次のような形になります。
木みたいに見えることから「探索木」と覚えると、覚えやすいでしょうか。簡単にそれぞれの用語だけ説明しますね。
| 用語 | 意味 |
|---|---|
| 節(ノード) | 図の○の部分全て。1つ1つの状態(迷路なら分かれ道)を表す |
| 根 | 探索木の一番上の節。スタートの状態 |
| 枝(エッジ) | 節同士をつないでいる線。1回の行動(右に進む、など)を表す |
| 葉 | 最下層の節。図で言うと一番下の○ |
| 親 | ある節から見て1つ上の節。上の図なら18は15と21の親 |
| 子 | ある節から見て1つ下の節。上の図なら15と21は18の子 |
探索とは、この木を根からたどって、ゴールの節を見つけることです。たどり方には大きく次の2種類があります。
なお、上の図のように「小さければ左、大きければ右」とデータを並べた木は二分探索木と呼ばれ、データを素早く探すための仕組みです。
G検定で問われる探索木は、迷路のような「状態の場合分け」の方なので、区別しておきましょう。
幅優先探索と深さ優先探索の違い
深さ優先探索とは
深さ優先探索とは、「根」から行けるところまで深く進み、行き止まりになったら1つ戻って別の枝を探すやり方です。
例えば図のD5が正解のデータだとしましょう。図で言うと、まず左端の「葉」まで一気に進んで探索します。
間違っていれば、1つ戻ってその隣の「葉」を探索。さらにその次へ…。
このように深さを優先して順番に正解を探していく、といったイメージでしょうか。
今たどっている道筋だけ覚えておけばよいので、メモリが少なくて済むのが長所です。
ただし、たまたま深い方から探すので、最短の解とは限らないのが短所です。
幅優先探索とは
幅優先探索とは、根に近い階層から順に、同じ深さの節をすべて調べてから次の階層へ進むやり方です。
同じく図のD5が正解のデータだとしましょう。最初に「根」の1つ下にある全てのノードを探索し、次にその1つ下の階層の全てのノードを探索…というように、木の横幅を優先して探していきます。
浅い階層から順に調べるので、最短の解が必ず見つかるのが長所です。ただし、途中の節をすべて覚えておく必要があるので、メモリを多く使うのが短所です。
比較表:メモリと最短経路
G検定では、この2つの長所・短所を入れ替えたひっかけがよく出ます。表で整理しておきましょう。
| 比べるところ | 幅優先探索 | 深さ優先探索 |
|---|---|---|
| 進み方 | 浅い階層から横に全部 | 行けるところまで縦に深く |
| 最短の解 | 必ず見つかる | 見つかるとは限らない |
| メモリ | 多く使う | 少なくて済む |
| 向いている問題 | 最短経路を知りたいとき | メモリが限られるとき・解がどこかにあればよいとき |
覚え方は「幅は広く浅く・全部覚えるから重いけど確実」「深さは一本道・身軽だけど遠回りかも」です。
プランニングとSTRIPS
プランニング(自動計画)とは、ロボットの行動計画を、前提条件・行動・結果の組み合わせで作ることです。
手順としては次のように行われるようです。
- シミュレーションなどを通して現状を認識する
- 問題点を分析する
- 問題を達成するための戦略、行動順序を具体化する
このようにして、人間が解く問題を機械に解かせようとした感じですね。ロボットがどう動くのかをあらかじめ計画(プランニング)しておく、という言葉通りの意味です。
STRIPSとは
STRIPSとは、プランニング(自動計画)を記述できる言語のことです。
1971年にスタンフォード研究所で開発されました。この言語は次の3つで構成されます。
- 前提条件
- 行動
- 結果
上記3つの組み合わせを入力することで、1つの動作を定義する自動計画を記述できるようです。
例えば「サルが台に上ってバナナを取る」という例を考えてみましょう。
この場合「結果」は「サルがバナナを取る」ですね。
「前提条件」は「Xにサルがいて、Yにバナナがあって、Zに台がある」といった、最初の状態がどうなっているのかを表します。
「行動」は「サルが台の所に行く⇒台をバナナの所に持ってくる⇒…」のように、具体的にどう行動することで「結果」が得られるか、です。
この言語に触発されて、PDDL(Planning Domain Definition Language)という言語も1998年に開発されたようですね。
ここまでの勉強で「やっぱり独学は難しい…」と思っているのであれば、実際に手を動かして学べる講座で一歩先に進むのも一つの手です。
SHRDLUとは
SHRDLUとは、英語で指示を出すと、画面の中の「積み木の世界」を操作できる、人工知能初期の研究開発プロジェクトのことです。
テリー・ウィノグラードが、1968〜1970年ごろにMITで開発しました(ウィノグラードは後にスタンフォード大学の教授になりますが、SHRDLUを作ったのはMIT時代です)。
「赤いブロックを緑の箱の上に置いて」のように自然言語で指示すると、プランニングを使って積み木を動かせたようです。
言葉の理解と行動計画を組み合わせた点が画期的でした。
STRIPSとSHRDLUは名前が似ていますが、STRIPSは言語、SHRDLUは積み木を操作するシステム、と区別しておきましょう。
第1次AIブームが終わった理由(トイ・プロブレム)
第1次AIブームのAIが解けたのは、迷路やパズルのようなトイ・プロブレム(おもちゃの問題)だけでした。
ルールとゴールがはっきりしていて、場合分けの数も限られている問題ですね。
ところが現実の問題は、考えるべき要素が多すぎて、探索木が爆発的に大きくなってしまいます。
「もっと色んな事ができるようになると思ったのに大したことないな…」という失望感から、第1次AIブームは終わってしまったようです。
トイ・プロブレムの代表例ハノイの塔はハノイの塔とモンテカルロ法の記事、ゲームAIの探索(ミニマックス法など)はミニマックス法とαβ法の記事で解説しています。
G検定での問われ方|探索・推論の早見表
現行シラバスの「探索・推論」のキーワードを一言でまとめておきます。この記事で扱っていない用語は、リンク先の記事で詳しく解説しています。
| 用語 | 一言でいうと | 詳しい解説 |
|---|---|---|
| αβ法 | Mini-Max法で、調べても結果が変わらない枝を刈り込んで探索を速くする方法 | 解説記事 |
| Mini-Max法 | 自分は得点を最大化、相手は最小化すると仮定して最善手を選ぶ探索方法 | 解説記事 |
| SHRDLU | 1970年頃テリー・ウィノグラードが開発。積み木の世界を英語の指示で動かしたシステム | この記事 |
| STRIPS | 自動計画(プランニング)の記述方法。「前提条件・行動・結果」の組で表す | この記事 |
| 探索木 | 場合分けを木の形で表し、ゴールまでの道筋を探す方法 | この記事 |
| ハノイの塔 | 円盤を別の柱に移すパズル。探索木で解ける代表的なトイ・プロブレム | 解説記事 |
| 幅優先探索 | 浅い階層から順に全部調べる探索。最短経路が必ず見つかるがメモリを多く使う | この記事 |
| 深さ優先探索 | 行けるところまで深く進み、行き止まりで戻る探索。メモリは少ないが最短とは限らない | この記事 |
| ブルートフォース | 考えられる手をしらみつぶしに全部試す力技の方法 | 解説記事 |
| モンテカルロ法 | ランダムなシミュレーションを大量に行って評価値を求める方法。囲碁AIの盤面評価で使われた | 解説記事 |
よくある質問
Q. 幅優先探索と深さ優先探索、最短経路が必ず見つかるのはどちら?
幅優先探索です。浅い階層から順に調べるので、最初に見つかった解が最短になります。そのぶん途中の節をすべて覚えるので、メモリを多く使います。
Q. STRIPSとSHRDLUの違いは?
STRIPSはプランニング(自動計画)を「前提条件・行動・結果」で記述する言語です。SHRDLUはテリー・ウィノグラードが作った、英語の指示で積み木の世界を操作するシステムです。
Q. 第1次AIブームはいつ頃ですか?
1956年のダートマス会議をきっかけに、1950年代後半から1960年代にかけて起こりました。トイ・プロブレムしか解けないことが分かり、1970年代に下火になりました。
よくある質問の内容までスラスラ答えられたら、次は問題形式で解いてみるのがおすすめです。選択肢を見比べると、どこで引っかけられるのかが分かってきます。
徹底攻略ディープラーニングG検定ジェネラリスト問題集 第3版
分野ごとの問題と解説がまとまった問題集。記事で覚えた用語を、本番と同じ選択式で解いて確かめられます。
|
|
まとめ
- 第1次AIブームは1950年代後半〜1960年代。探索・推論が中心だった
- 探索木は、問題を解く途中の状態を木の形に場合分けしたもの
- 幅優先探索は最短の解が見つかるがメモリを多く使う。深さ優先探索はその逆
- STRIPSはプランニングの言語、SHRDLUは積み木の世界を言葉で操作するシステム
- トイ・プロブレムしか解けなかったことが、第1次AIブームが終わった理由
次は、第1次AIブームの続きとして、ゲームAIの探索手法「ミニマックス法」と「αβ法」をミニマックス法の記事で解説していきます。覚える内容が多いですが、りけーこっとんも頑張ります!
G検定の試験範囲をまとめて見直したい方は、シラバスの全キーワードを一行でまとめたG検定チートシートをどうぞ。分野ごとに読み進めたい方はG検定の解説記事一覧からどうぞ。
お子さんと一緒にAIを学びたい方には、親子で生成AIの使い方を学べる講座もあります。
G検定の勉強で身につけた知識は、データ分析やAI関連の仕事でそのまま使う土台になります。データ系の求人は職種名がバラバラで自分では探しにくいので、どんな求人があるのかを一度眺めておくと、次に学ぶべきことがはっきりしてきます。
20代で未経験からIT職を目指す方、すでに経験があってフリーランスの案件を探したい方は、それぞれ専門のサービスを使うと探す手間が省けます。



