一、核心概念（填空/选择高频）

1. 搜索算法基础

• 搜索算法的形式化描述：状态、动作、状态转移、路径/代价、目标测试

• 搜索树的概念：从初始状态出发，扩展后继节点，直到找到目标

• 搜索算法的评价指标：

  • 完备性、最优性

  • 时间复杂度、空间复杂度

• 两种搜索框架：

  • 树搜索：允许重复访问状态，可能陷入循环

  • 图搜索：使用闭表存储已扩展状态，避免环路

2.启发式搜索

• 启发式搜索的定义：利用辅助信息（启发函数） 指导搜索，减少搜索范围

• 启发函数 h(n)：估计从当前节点到目标节点的代价

• 评价函数 f(n)：用于节点扩展优先级排序

• 常见启发式搜索算法：

  • 贪婪最佳优先搜索：f(n)=h(n)

  • *A 算法**：f(n)=g(n)+h(n)，其中 g(n)是从起点到当前节点的实际代价

  • A* 的最优性条件：启发函数 h(n)必须满足可采纳性（不高于真实代价）

• A* 与贪婪搜索的区别：A* 考虑了已付出代价，避免“贪心短视”

---

二、算法特征与对比（易出选择题）

算法	评价函数 f(n)	是否最优	是否完备
贪婪最佳优先搜索	h(n)	否	否
A* 搜索	g(n)+h(n)	是（若 h(n) 可采纳）	是

• A* 的时间复杂度与空间复杂度：取决于启发函数的质量

• 贪婪搜索可能陷入局部最优

• 启发函数设计原则：越接近真实代价，搜索效率越高

---

三、典型例题与考点（可出计算或简答）

1. 计算题示例（类似选择题4）

• 给出一个城市图，给出各节点 g(n)g(n) 和 h(n)h(n) 值，要求：

  • 写出贪婪最佳优先搜索的扩展顺序

  • 写出 A* 搜索的扩展顺序

  • 判断是否找到最优路径

2. 简答题示例

• 解释为什么 A* 算法比贪婪搜索更优？

• 什么是“可采纳启发函数”？为什么 A* 需要它来保证最优性？

• 图搜索与树搜索的根本区别是什么？闭表的作用是什么？

三、典型例题与考点 · 答案与解析

1. 计算题示例（附答案）

题目：
给出如下城市图，各节点间的实际代价 g(n)g(n) 和启发函数值 h(n)h(n) 如下表所示（起点为 A，目标为 G）：

节点	前驱节点与路径代价 g(n)g(n)	h(n)h(n)
A	0	5
B	A→B=2	4
C	A→C=3	4
D	B→D=4	2
E	C→E=5	3
F	D→F=2, E→F=3	1
G	F→G=2	0

要求：
（1）写出贪婪最佳优先搜索从 A 到 G 的节点扩展顺序。
（2）写出 A 搜索* 从 A 到 G 的扩展顺序，并写出每一步的 f(n)=g(n)+h(n)f(n)=g(n)+h(n)。
（3）判断两种算法是否都找到了最优路径，并给出最优路径的代价。

---

答案与解析：

（1）贪婪最佳优先搜索扩展顺序：

• 评价函数：f(n)=h(n)f(n)=h(n)

• 扩展顺序：

  1. 初始：A (h=5h=5)

  2. 扩展A：B (h=4h=4), C (h=4h=4) → 选B（假设按字母顺序）

  3. 扩展B：D (h=2h=2)

  4. 扩展D：F (h=1h=1)

  5. 扩展F：G (h=0h=0)

扩展顺序：A → B → D → F → G

（2）A* 搜索扩展顺序：

• 评价函数：f(n)=g(n)+h(n)f(n)=g(n)+h(n)

• 扩展过程：

  1. A: f=0+5=5f=0+5=5

  2. 扩展A：B (2+4=62+4=6), C (3+4=73+4=7) → 选择B（f值最小）

  3. 扩展B：D (6+2=86+2=8)

  4. 扩展C：E (8+3=118+3=11)

  5. 扩展D：F (8+1=98+1=9)

  6. 扩展F：G (11+0=1111+0=11)

扩展顺序：A → B → C → D → F → G

（3）最优路径判断：

• 最优路径应为：A → B → D → F → G

• 总代价：2+4+2+2=102+4+2+2=10

• 贪婪搜索找到的路径：A → B → D → F → G，代价10 → 找到最优路径（本题巧合）

• A* 搜索找到的路径：A → B → D → F → G，代价10 → 找到最优路径（保证最优）

✅ 结论：本题中两种算法都找到了最优路径，但贪婪搜索不保证总是最优，A* 在启发函数可采纳时保证最优。

---

2. 简答题示例 · 答案

（1）解释为什么 A* 算法比贪婪搜索更优？

A* 算法在评价函数中同时考虑 “已付出代价” g(n) 和 “估计剩余代价” h(n)，即 f(n)=g(n)+h(n)。
而贪婪最佳优先搜索只考虑 h(n)，即只关注“距离目标有多近”，不考虑“已经走了多远”。
因此，A* 能避免贪婪搜索可能导致的“短视行为”，即在局部最优附近徘徊而错过全局更优路径，从而在启发函数 h(n) 可采纳的情况下保证找到最优路径。

---

（2）什么是“可采纳启发函数”？为什么 A* 需要它来保证最优性？

• 可采纳启发函数 是指启发函数 h(n) 对任意节点 n，其值都不大于从 n 到目标节点的真实代价 h∗(n)，即 h(n)≤h∗(n)。

• A* 需要可采纳启发函数来保证最优性，因为如果 h(n) 高估了真实代价，可能会导致算法优先扩展一个实际代价较高的路径，从而错过最优解。可采纳性保证了 A* 在扩展节点时不会错过更优路径，从而在完备性和最优性之间取得平衡。

---

（3）图搜索与树搜索的根本区别是什么？闭表的作用是什么？

• 根本区别：
  树搜索允许重复访问同一状态，可能导致无限循环；
  图搜索使用闭表（closed set） 记录所有已扩展过的状态，避免重复扩展，从而防止环路和重复搜索。

• 闭表的作用：
  闭表存储所有已被扩展的节点状态，当新生成的节点状态已在闭表中时，该节点不会被再次加入开放表（open list），从而节省存储空间、提高搜索效率，并避免算法陷入无限循环。

---

四、与试卷中其他章节的关联点

• MiniMax 与 Alpha-Beta 剪枝（对抗搜索）与启发式搜索同属“搜索求解”章节

• 蒙特卡洛树搜索中 UCB 算法的“探索与利用”思想，与启发式搜索中的“启发引导”有相似之处

• *A 算法**在试卷中常与“评价函数 f(n)=g(n)+h(n) 结合出题（填空题16）

---

五、复习建议

1. 重点掌握：

   • A* 算法的工作流程与最优性条件

   • 贪婪搜索与 A* 的对比

   • 启发函数的定义与设计原则

2. 动手练习：

   • 画搜索树，模拟 A* 扩展过程

   • 理解闭表与图搜索的实现逻辑

3. 联系实际：

   • A* 常用于路径规划（如游戏AI、机器人导航）

   • 启发式思想在后续章节（如强化学习、神经网络）中也有体现

---

第三章 搜索求解1 - 启发式搜索 · 模拟练习题

一、填空题（每空1分）

1. 启发式搜索使用辅助信息（也称为________函数）来引导搜索方向，减少搜索范围。

2. 贪婪最佳优先搜索的评价函数 f(n)=f(n)= ________。

3. A* 算法中，f(n)=f(n)= ________ + ________。

4. 若启发函数 h(n)h(n) 永远不大于从当前节点到目标节点的真实代价，则称该启发函数具有________性。

5. 在图搜索中，为了避免环路，使用一个集合记录已扩展节点的状态，称为________表。

6. 搜索算法的两个重要评价指标是________性和________性。

7. 树搜索可能陷入________问题，而图搜索通过记录已访问状态来避免该问题。

8. 在A* 算法中，若 h(n)=0h(n)=0，则 A* 退化为________算法。

---

二、选择题（每题2分）

1. 以下哪种搜索算法总是优先扩展当前离目标“最近”的节点，而不考虑已走路径的代价？
   A) A* 搜索
   B) 广度优先搜索
   C) 贪婪最佳优先搜索
   D) 深度优先搜索

2. A* 算法保证能找到最优解的条件是？
   A) 启发函数 h(n)h(n) 可采纳
   B) 启发函数 h(n)h(n) 单调
   C) 启发函数 h(n)h(n) 恒为正
   D) 图搜索模式开启

3. 以下哪种情况可能导致贪婪最佳优先搜索陷入局部最优？
   A) 启发函数值过大
   B) 启发函数值过小
   C) 启发函数值与真实代价无关
   D) 启发函数值总是等于真实代价

4. 在A* 搜索中，若启发函数 h(n)h(n) 恒为0，则算法等价于：
   A) 广度优先搜索
   B) 深度优先搜索
   C) 迪杰斯特拉算法
   D) 蒙特卡洛树搜索

5. 以下哪项不是图搜索相对于树搜索的优势？
   A) 避免重复访问状态
   B) 减少存储开销
   C) 保证找到最优解
   D) 防止无限循环

---

三、计算题（10分）

假设有如下城市路径图，节点间连线上的数字表示实际路径代价，表格中给出了各节点到目标节点 K 的启发函数值 h(n)h(n)：

text

城市图：
A → B (5)
A → D (3)
B → E (10)
D → E (12)
D → F (9)
E → K (3)
F → K (8)

启发函数 h(n)：
A: 15, B: 10, D: 12, E: 3, F: 8, K: 0

请回答：

1. 使用贪婪最佳优先搜索，写出从 A 到 K 的扩展顺序（每次扩展一个节点）。

2. 使用A* 搜索，写出从 A 到 K 的扩展顺序，并写出每次扩展时各节点的 f(n)=g(n)+h(n)f(n)=g(n)+h(n) 值。

3. 两种算法是否都找到了最优路径？最优路径是什么？代价是多少？

---

参考答案

一、填空题

1. 启发

2. h(n)h(n)

3. g(n)g(n), h(n)h(n)

4. 可采纳

5. 闭

6. 完备，最优

7. 循环（或无限循环）

8. 迪杰斯特拉（或Dijkstra）

二、选择题

1. C

2. A

3. C

4. C

5. C（图搜索不保证最优，需要启发函数可采纳才保证）

三、计算题

1. 贪婪最佳优先搜索扩展顺序：A → D → E → K

2. *A 搜索扩展顺序**：

   • 初始：A (0+15=15)

   • 扩展A：B (5+10=15), D (3+12=15)

   • 扩展D：E (15+3=18), F (12+8=20)

   • 扩展B：E (15+3=18)

   • 扩展E：K (18+0=18)
     顺序：A → D → B → E → K

3. 最优路径：A → D → E → K，总代价 = 3 + 12 + 3 = 18

   • 贪婪搜索找到的路径：A → D → E → K，代价18（与最优一致，但不总是保证最优）

   • A* 搜索保证最优，路径同上。

---

如果你需要更多练习题，或希望我为你生成其他章节的复习材料，请告诉我！