ダイクストラ法・BFS・A* を図で理解する課題（時間補習課題）
【学習目標】
この課題では次のことができるようになります。
- BFS（幅優先探索）の基本と動き方を説明できる
- ダイクストラ法の仕組みを理解できる
- A* が「何を追加したアルゴリズム」か説明できる
- 図を見て 3つの探索アルゴリズムを比較できる
- ゲーム開発での使い分けが説明できる
🔶【課題図（グラフ構造）】
(1) (1) (1)
[S] ------ [A] ------ [B] ------ [G]
\
\ (5)
\
[C]
\
\ (1)
\
[B]（同じB）- S：スタート
- G：ゴール
- 数字：その道を通るコスト
◆ ① BFS（幅優先探索）とは？（穴埋め）
BFS は、
スタートから （ ） の順に探索していくアルゴリズムで、
道のコストが （ ） ときに最短経路を見つけることができる。
選択肢：
- 近いノード
- 深さ
- 同じ
- バラバラ
◆ ② ダイクストラ法とは？（穴埋め）
ダイクストラ法は、
スタートからの （ ） を更新しながら、
（ ） が最も小さいノードを順に確定する方法である。
選択肢：
- 最短距離
- コスト
- 深さ
- 未確定ノード
◆ ③ A* アルゴリズムとは？（穴埋め）
A* は、ダイクストラ法に （ ） を追加した方法で、
より （ ） ゴールに到達することを目的としている。
選択肢：
- ヒューリスティック
- ランダム
- 早く
- 正確に
◆ ④ 図を見て考える：BFS / ダイクストラ / A* の動き
Q1. BFS はどのルートを最初に見つける？
BFS が最初に見つけるルートは （ ）
理由：__________________________________________________
Q2. ダイクストラ法が求める “最短経路” は？
- 経路：（ ）
- 合計コスト： （ ）
ヒント：
- S→A→B→G = 1+1+1 = 3
- S→C→B→G = 5+1+1 = 7
Q3. A* の式を完成させよう
A* の評価値 f(n) は次の式で求める：
f(n) = g(n) + h(n)
- g(n)：Sからそのノードまでの実コスト
- h(n)：ゴールまでの （ ）
選択肢：
- 予想距離（予想値）
- 完全一致する距離
- 乱数
◆ ⑤ BFSの理解を深める
追加Q1：BFS はどんな順番で探索を進める？
A と B どちらかを選んで、理由を書くこと。
- A：スタート地点から「近いノード」から順番に調べる
- B：コストが小さい道を優先して調べる
回答：A / B（理由：___________________________________）
追加Q2：図を使って BFS の探索順を書こう
例：S → A → B → C → G のように記述。
探索順：_____________________________________
追加Q3：なぜ BFS は「コスト同じのときだけ」最短経路を求められるのか？
穴埋め：
BFS は、道のコストがすべて （ ） とき、
スタートからの （ ） の順に探索するため、
最短経路が求まる。
選択肢：
- 同じ
- バラバラ
- 深さ（段階）
- 重さ
追加Q4：コストがバラバラのときに BFS が失敗する例
BFS はどちらを先に探索する？
- ルート1：S → A → B → G（合計3）
- ルート2：S → C → B → G（合計7）
回答：________________________________________
理由：______________________________________________________
追加Q5：ゲーム開発で BFS が役立つ場面は？
番号を選び、理由を書く。
- 敵から一定距離以内に逃げたいとき
- コストがバラバラのマップで探索したい
- 同じコストのタイルで広いマップを探索するとき
選んだ番号：___
理由：______________________________________
追加Q6：BFS の弱点
図のように“遠回りだが軽い道”があるとき、BFS はどんな失敗をするか？
回答：_______________________________________________
追加Q7：BFS を1行でまとめよ
「BFS は ________ を優先し、コストが ________ ときに最短経路を求められる」
追加Q8：BFS とダイクストラの共通点・相違点（穴埋め）
- 共通点：どちらも（ ）に沿って探索し、最終的に（ ）を求める
- 違い：BFS は（ ）が同じときに最短になるが、
ダイクストラ法は（ ）が0以上であれば最短を求められる
◆ ⑥ 3つのアルゴリズムの違いを1行ずつまとめよう
- BFS： 道のコストが （ ） とき、 _______ の順に探索する
- ダイクストラ法： コストが0以上なら _______ を必ず見つけられる
- A*： ヒューリスティックを使って _______ 探索する
◆ ⑦ ゲーム開発での使い分け
- 草原でコストが全部同じ
→ （ ）
理由：_________________________________________ - コストがバラバラの道（泥・坂・砂）
→ （ ）
理由：_________________________________________ - ゴール（敵の位置）が分かっている
→ （ ）
理由：_________________________________________
◆ ⑧ 最終まとめ（作文）
ダイクストラ法・BFS・A* の違いを、初心者にもわかるよう詳細に説明せよ。