はじめに
G検定では、AI・機械学習の知識だけでなく、探索アルゴリズムや理論に関する用語の意味も正確に理解していることが求められます。
また、「幅優先探索（BFS）」と「深さ優先探索（DFS）」は、ITパスポート試験のテクノロジ系・アルゴリズム分野でも出題される重要用語です。
中でも「幅優先探索」や「深さ優先探索」は、多くの受験者が混同しやすい項目です。
今回は、このような混乱を解消するために、AIを活用した教育ソング「幅優先と深さ優先探索のうた」を制作しました。
音楽のリズムに合わせて用語の意味を覚えることで、楽しく効率的に学習できます。
AIを活用した楽曲制作
この楽曲は、歌詞の生成を生成AI（ChatGPT）で行い、曲自体の制作はAI作曲ツール（Suno AI）を用いて作成されました。
タイトル・歌詞の紹介
曲タイトル
幅優先と深さ優先探索のうた
歌詞
幅優先探索は浅く広く 階層ごとに探索する
深さ優先探索は深く一直線 行けるところまで進んでく
幅優先近い順 レベル順で探してく
キューを使って順番に 最短経路必ず見つける
深さ優先スタック使う 行き止まりなら一つ前へ
探索進めるメモリ効率よい 最短経路は保証なし
幅優先はメモリたくさん 最短経路に向いている
深さ優先経路長い 深さ優先はメモリ効率がよい
幅優先探索浅く広く 幅優先は最短経路
深さ優先探索深く一直線 深さ優先はメモリ効率がよい
楽曲の視聴
以下のプラットフォームで楽曲を視聴できます。
- YouTube
- Suno AI
幅優先と深さ優先探索のうた（Suno AI）
歌詞の解説
幅優先探索は浅く広く / 階層ごとに探索する
幅優先探索（BFS）は、ノードの階層ごとに横に広がるように探索を行います。
近くのノードを優先して処理するため、「浅く広く」という特徴になります。
探索はキュー（FIFO）構造で管理されます。
幅優先近い順 / レベル順で探してく
BFSでは、スタート地点からの距離が近い順にノードを探索していきます。
各階層（レベル）を1段ずつ探索していくため、「レベル順の探索」とも呼ばれます。
キューを使って順番に / 最短経路必ず見つける
幅優先探索は、キュー（Queue）という構造を用いて、先に入れたノードを先に取り出す（先入れ先出し）方法で探索を管理します。
この特性により、グラフにおける最短経路を必ず見つけることができます。
例：ノード \( u \) からノード \( v \) に距離1で移動するときの更新式は
\(d[v] = d[u] + 1
\)
深さ優先スタック使う / 行き止まりなら一つ前へ
深さ優先探索（DFS）は、ノードをできるだけ深く辿り、行き止まりに達したら直前のノードに戻って別の道を探索する手法です。
この「戻る」処理は、スタック（LIFO＝後入れ先出し）を使って管理します。
再帰関数でもこの処理が実現できます。
探索進めるメモリ効率よい / 最短経路は保証なし
DFSでは、探索中に保持する情報が少ないためメモリの使用量が少なくて済みます。
これが「メモリ効率が良い」と言われる理由です。
ただし、最短経路を探すわけではないため、近道を見逃す可能性があります。
幅優先はメモリたくさん / 最短経路に向いている
幅優先探索では、各階層のすべてのノード情報を一度に保持する必要があり、メモリ消費量が多いです。
しかし、その分最短経路を正確に導き出せるというメリットがあります。
深さ優先経路長い / メモリ効率がよい
DFSは深く進みすぎて遠回りになる場合があり、実際にたどる経路が長くなることがあります。
その一方で、一度に記憶しておく情報が少ないため、メモリの節約には優れています。
楽曲に込めたメッセージ
この楽曲には、単なる暗記ではなく、「意味と構造を音楽で体に覚えさせる」という意図があります。
試験中に思い出せるよう、定義文やキーワードを歌詞そのままの形で記憶に定着させる構成にしました。
アルゴリズムの学習においては、図解やコードと並行して「言語的に定義を言える」ことも重要です。
まとめ
「幅優先探索」と「深さ優先探索」はG検定でも頻出の概念です。
それぞれの特徴を音楽のリズムに乗せて覚えることで、混同せず正確に定義を選べるようになることを目指しました。
AIによる作曲・作詞の力を活用し、より楽しく・効率よく学べる学習方法として、ぜひ活用してみてください。
コメント