1-前言

为了应对大学院考试，我们来学习相关人工智能相关知识，并且是基于相关课程。使用课程为MIT的公开课。

通过学习，也算是做笔记，让自己更理解些。

2-课程链接

是在B站看的视频，链接如下：
https://www.bilibili.com/video/BV1dM411U7qK?spm_id_from=333.788.videopod.episodes&vd_source=631b10b31b63df323bac39281ed4aff3&p=4

3-具体内容解释说明

一、这节课在 AI 课程中的位置

课程顺序是这样的：

1️⃣ 目标树・规则推理
2️⃣ 探索（DFS / BFS / 束搜索）← 本节
3️⃣ 最优探索（Uniform Cost / A*）
4️⃣ 博弈探索（Minimax / α–β）

👉 这一节是：

从「逻辑推理」过渡到「在状态空间里怎么走」

---

二、什么是「探索（Search）」？

1️⃣ 一句话定义（考试版）

探索 = 在所有可能的状态中，按照某种策略寻找解的方法

三个核心要素：

• 状态（节点）
• 转移（边）
• 探索顺序（策略）

👉 不同探索方法，区别只在“先走哪条路”

---

三、深度优先探索（DFS）

1️⃣ 一句话理解

一路走到不能再走，再回头

---

2️⃣ 探索特征

• 用 栈（Stack） 思想
• 总是优先扩展“最深”的节点
• 不保证最短解

---

3️⃣ DFS 的优缺点（必考）

优点

• 内存消耗小
• 实现简单

缺点

• 容易走“死胡同”
• 可能找不到最优解
• 在无限深空间可能不结束

---

4️⃣ 什么时候用 DFS？

✔ 解很深
✔ 内存受限
✔ 只要“一个解”即可

📌 语法分析、回溯问题

---

四、宽度优先探索（BFS）

1️⃣ 一句话理解

先把近的都看完，再看远的

---

2️⃣ 探索特征

• 用 队列（Queue）
• 按“层”扩展节点
• 边权相同 → 一定找到最短路径

---

3️⃣ BFS 的优缺点（必考）

优点

• 保证最短路径（条件成立时）
• 一定能找到解（有限空间）

缺点

• 内存消耗大
• 分支多时爆炸

---

4️⃣ 什么时候用 BFS？

✔ 解在浅层
✔ 需要最短步数
✔ 状态空间不大

📌 迷宫、最少步数问题

---

五、束搜索（Beam Search）

1️⃣ 一句话理解

每一层只保留“看起来最有希望的 K 个”

---

2️⃣ 探索思想

• 类似 BFS
• 但每一层只保留 K 个节点
• 其余直接丢弃

👉 用“剪枝”换效率

---

3️⃣ 束宽（Beam Width）

• K 越大 → 越接近 BFS
• K 越小 → 越快但越容易错

⚠️ 不保证最优解

---

4️⃣ 束搜索的优缺点（必考）

优点

• 速度快
• 内存可控

缺点

• 可能丢掉正确解
• 结果依赖启发函数

---

5️⃣ 常见应用

📌 自然语言处理
📌 机器翻译
📌 序列生成

👉 工程中非常常见

---

六、三种探索的本质对比（考试最爱）

方法	顺序	内存	最优性
DFS	深度优先	小	❌
BFS	层次优先	大	✅（等权）
束搜索	启发保留	中	❌

---

七、和 A* 的关系（承上启下）

• DFS / BFS / Beam：“怎么走”
• A*：“怎么走得最好”

A* =
👉 BFS 的系统性
👉 + 启发式判断

---

八、入试怎么考你？

常见问法

• 哪种探索保证最短路径？
• 哪种方法内存消耗最小？
• 束搜索和 BFS 的区别？
• 为什么束搜索不能保证最优？

---

常见陷阱

❌ DFS 能找到最短路径
❌ 束搜索一定比 BFS 好
❌ BFS 内存占用小

---

九、一句话考试总结（背下来）

DFS 省内存但不保证解，
BFS 保证最短但耗资源，
束搜索用剪枝换效率。

---

4-课后练习（日语版本）

問題1（深さ優先探索）

深さ優先探索（Depth-First Search, DFS）に関する説明として最も適切なものはどれか。

選択肢

a. 常に最短経路を保証する探索方法である
b. 探索は階層ごとに行われ、キュー構造を用いる
c. 探索は可能な限り深く進み、行き止まりで戻る
d. 各ノードの評価関数に基づいて探索順序を決定する

---

問題2（幅優先探索）

幅優先探索（Breadth-First Search, BFS）に関する説明として正しいものはどれか。

選択肢

a. メモリ使用量は常に最小となる
b. 辺のコストが等しい場合、最短経路を見つけることができる
c. 無限に深い探索空間では必ず停止する
d. 探索順序はヒューリスティック関数に依存する

---

問題3（束探索）

束探索（Beam Search）に関する説明として適切なものはどれか。

選択肢

a. 探索の完全性と最適性を常に保証する
b. 深さ優先探索の一種であり、再帰的に探索を行う
c. 各段階で評価の高い一定数のノードのみを保持する
d. 探索中に全ての生成ノードを記憶する必要がある

---

問題4（探索手法の比較）

探索手法に関する記述のうち、正しいものはどれか。

選択肢

a. DFS は BFS より常に計算時間が短い
b. BFS は DFS に比べて一般にメモリ消費が大きい
c. 束探索は常に BFS より良い解を生成する
d. DFS、BFS、束探索はいずれも評価関数を必須とする

---

作答形式（立命館大学入試慣例）

問題1：
問題2：
問題3：
問題4：

5-课后答案解析（日语版本）

---

✅ 採点結果

問題	あなたの解答	正解	判定
問題1（DFS）	C	C	✅
問題2（BFS）	B	B	✅
問題3（束探索）	C	C	✅
問題4（比較）	B	B	✅

👉 4 / 4 完全正解

---

🔍 入試視点・超短コメント

問題1（DFS）

• **「深く進んで戻る」**を正確に言語化できている
• DFS 定義問題はこれで満点

問題2（BFS）

• **「等コストなら最短保証」**は立命館の超定番フレーズ
• ここを落とさないのは非常に重要

問題3（束探索）

• **「各段階で一定数のみ保持」**＝束探索の本質
• 最適性を保証しない点も正しく理解できている

問題4（比較）

• BFS はメモリを食うという基本比較が明確
• 迷いやすい問題だが判断が安定している

---

🧠 試験直前用・10秒暗記まとめ

DFS：深く・省メモリ・最適保証なし
BFS：浅く・最短保証（等コスト）・メモリ大
束探索：数を絞る・高速・保証なし

---

6-总结

知识一点点记录吧，最后应对考试，打下基础