# ダイクストラ法・BFS・A* を図で理解する課題（時間補習課題）

## 【学習目標】

この課題では次のことができるようになります。

- BFS（幅優先探索）の基本と動き方を説明できる
- ダイクストラ法の仕組みを理解できる
- A\* が「何を追加したアルゴリズム」か説明できる
- 図を見て 3つの探索アルゴリズムを比較できる
- ゲーム開発での使い分けが説明できる

---

# 🔶【課題図（グラフ構造）】

```
(1)        (1)        (1)
   [S] ------ [A] ------ [B] ------ [G]
     \
      \ (5)
       \
       [C]
         \
          \ (1)
           \
           [B]（同じB）
```

- S：スタート
- G：ゴール
- 数字：その道を通るコスト

---

# ◆ ① BFS（幅優先探索）とは？（穴埋め）

BFS は、  
<span style="white-space: pre-wrap;">スタートから </span>****（ ）****<span style="white-space: pre-wrap;"> の順に探索していくアルゴリズムで、</span>  
<span style="white-space: pre-wrap;">道のコストが </span>****（ ）****<span style="white-space: pre-wrap;"> ときに最短経路を見つけることができる。</span>

選択肢：

- 近いノード
- 深さ
- 同じ
- バラバラ

---

# ◆ ② ダイクストラ法とは？（穴埋め）

ダイクストラ法は、  
<span style="white-space: pre-wrap;">スタートからの </span>****（ ）****<span style="white-space: pre-wrap;"> を更新しながら、</span>  
****（ ）****<span style="white-space: pre-wrap;"> が最も小さいノードを順に確定する方法である。</span>

選択肢：

- 最短距離
- コスト
- 深さ
- 未確定ノード

---

# ◆ ③ A\* アルゴリズムとは？（穴埋め）

<span style="white-space: pre-wrap;">A\* は、ダイクストラ法に </span>****（ ）****<span style="white-space: pre-wrap;"> を追加した方法で、</span>  
<span style="white-space: pre-wrap;">より </span>****（ ）****<span style="white-space: pre-wrap;"> ゴールに到達することを目的としている。</span>

選択肢：

- ヒューリスティック
- ランダム
- 早く
- 正確に

---

# ◆ ④ 図を見て考える：BFS / ダイクストラ / A\* の動き

## Q1. BFS はどのルートを最初に見つける？

<span style="white-space: pre-wrap;">BFS が最初に見つけるルートは </span>****（ ）****  
理由：\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_

---

## Q2. ダイクストラ法が求める “最短経路” は？

- 経路：****（ ）****
- <span style="white-space: pre-wrap;">合計コスト： </span>****（ ）****

ヒント：

- 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からそのノードまでの実コスト
- <span style="white-space: pre-wrap;">h(n)：ゴールまでの </span>****（ ）****

選択肢：

- 予想距離（予想値）
- 完全一致する距離
- 乱数

---

# ◆ ⑤ BFSの理解を深める

## 追加Q1：BFS はどんな順番で探索を進める？

A と B どちらかを選んで、理由を書くこと。

- A：スタート地点から「近いノード」から順番に調べる
- B：コストが小さい道を優先して調べる

****回答：A / B（理由：\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_）****

---

## 追加Q2：図を使って BFS の探索順を書こう

例：S → A → B → C → G のように記述。

****探索順：\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_****

---

## 追加Q3：なぜ BFS は「コスト同じのときだけ」最短経路を求められるのか？

穴埋め：

<span style="white-space: pre-wrap;">BFS は、道のコストがすべて </span>****（ ）****<span style="white-space: pre-wrap;"> とき、</span>  
<span style="white-space: pre-wrap;">スタートからの </span>****（ ）****<span style="white-space: pre-wrap;"> の順に探索するため、</span>  
最短経路が求まる。

選択肢：

- 同じ
- バラバラ
- 深さ（段階）
- 重さ

---

## 追加Q4：コストがバラバラのときに BFS が失敗する例

BFS はどちらを先に探索する？

- ルート1：S → A → B → G（合計3）
- ルート2：S → C → B → G（合計7）

****回答：\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_****  
理由：\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_

---

## 追加Q5：ゲーム開発で BFS が役立つ場面は？

番号を選び、理由を書く。

1. 敵から一定距離以内に逃げたいとき
2. コストがバラバラのマップで探索したい
3. 同じコストのタイルで広いマップを探索するとき

****選んだ番号：\_\_\_****  
理由：\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_

---

## 追加Q6：BFS の弱点

図のように“遠回りだが軽い道”があるとき、BFS はどんな失敗をするか？

****回答：\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_****

---

## 追加Q7：BFS を1行でまとめよ

「BFS は \_\_\_\_\_\_\_\_ を優先し、コストが \_\_\_\_\_\_\_\_ ときに最短経路を求められる」

---

## 追加Q8：BFS とダイクストラの共通点・相違点（穴埋め）

- 共通点：どちらも（ ）に沿って探索し、最終的に（ ）を求める
- 違い：BFS は（ ）が同じときに最短になるが、  
    ダイクストラ法は（ ）が0以上であれば最短を求められる

---

# ◆ ⑥ 3つのアルゴリズムの違いを1行ずつまとめよう

- ****BFS：****<span style="white-space: pre-wrap;"> 道のコストが </span>****（ ）****<span style="white-space: pre-wrap;"> とき、 \_\_\_\_\_\_\_ の順に探索する</span>
- ****ダイクストラ法：****<span style="white-space: pre-wrap;"> コストが0以上なら \_\_\_\_\_\_\_ を必ず見つけられる</span>
- ****A\*：****<span style="white-space: pre-wrap;"> ヒューリスティックを使って \_\_\_\_\_\_\_ 探索する</span>

---

# ◆ ⑦ ゲーム開発での使い分け

1. 草原でコストが全部同じ  
    <span style="white-space: pre-wrap;">→ </span>****（ ）****  
    理由：\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_
2. コストがバラバラの道（泥・坂・砂）  
    <span style="white-space: pre-wrap;">→ </span>****（ ）****  
    理由：\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_
3. ゴール（敵の位置）が分かっている  
    <span style="white-space: pre-wrap;">→ </span>****（ ）****  
    理由：\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_

---

# ◆ ⑧ 最終まとめ（作文）

****ダイクストラ法・BFS・A\* の違いを、初心者にもわかるよう詳細に説明せよ。****

---

---