[微机原理与系统设计-从入门到入土] 输入输出IO
2026/1/12 20:57:29
![]()
一、核心概念（填空/选择高频）
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)
扩展顺序：
初始：A (h=5h=5)
扩展A：B (h=4h=4), C (h=4h=4) → 选B（假设按字母顺序）
扩展B：D (h=2h=2)
扩展D：F (h=1h=1)
扩展F：G (h=0h=0)
扩展顺序：A → B → D → F → G
（2）A* 搜索扩展顺序：
评价函数：f(n)=g(n)+h(n)f(n)=g(n)+h(n)
扩展过程：
A: f=0+5=5f=0+5=5
扩展A：B (2+4=62+4=6), C (3+4=73+4=7) → 选择B（f值最小）
扩展B：D (6+2=86+2=8)
扩展C：E (8+3=118+3=11)
扩展D：F (8+1=98+1=9)
扩展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）
五、复习建议
重点掌握：
A* 算法的工作流程与最优性条件
贪婪搜索与 A* 的对比
启发函数的定义与设计原则
动手练习：
画搜索树，模拟 A* 扩展过程
理解闭表与图搜索的实现逻辑
联系实际：
A* 常用于路径规划（如游戏AI、机器人导航）
启发式思想在后续章节（如强化学习、神经网络）中也有体现
第三章 搜索求解1 - 启发式搜索 · 模拟练习题
一、填空题（每空1分）
启发式搜索使用辅助信息（也称为________函数）来引导搜索方向，减少搜索范围。
贪婪最佳优先搜索的评价函数 f(n)=f(n)= ________。
A* 算法中，f(n)=f(n)= ________ + ________。
若启发函数 h(n)h(n) 永远不大于从当前节点到目标节点的真实代价，则称该启发函数具有________性。
在图搜索中，为了避免环路，使用一个集合记录已扩展节点的状态，称为________表。
搜索算法的两个重要评价指标是________性和________性。
树搜索可能陷入________问题，而图搜索通过记录已访问状态来避免该问题。
在A* 算法中，若 h(n)=0h(n)=0，则 A* 退化为________算法。
二、选择题（每题2分）
以下哪种搜索算法总是优先扩展当前离目标“最近”的节点，而不考虑已走路径的代价？
A) A* 搜索
B) 广度优先搜索
C) 贪婪最佳优先搜索
D) 深度优先搜索A* 算法保证能找到最优解的条件是？
A) 启发函数 h(n)h(n) 可采纳
B) 启发函数 h(n)h(n) 单调
C) 启发函数 h(n)h(n) 恒为正
D) 图搜索模式开启以下哪种情况可能导致贪婪最佳优先搜索陷入局部最优？
A) 启发函数值过大
B) 启发函数值过小
C) 启发函数值与真实代价无关
D) 启发函数值总是等于真实代价在A* 搜索中，若启发函数 h(n)h(n) 恒为0，则算法等价于：
A) 广度优先搜索
B) 深度优先搜索
C) 迪杰斯特拉算法
D) 蒙特卡洛树搜索以下哪项不是图搜索相对于树搜索的优势？
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
请回答：
使用贪婪最佳优先搜索，写出从 A 到 K 的扩展顺序（每次扩展一个节点）。
使用A* 搜索，写出从 A 到 K 的扩展顺序，并写出每次扩展时各节点的 f(n)=g(n)+h(n)f(n)=g(n)+h(n) 值。
两种算法是否都找到了最优路径？最优路径是什么？代价是多少？
参考答案
一、填空题
启发
h(n)h(n)
g(n)g(n), h(n)h(n)
可采纳
闭
完备，最优
循环（或无限循环）
迪杰斯特拉（或Dijkstra）
二、选择题
C
A
C
C
C（图搜索不保证最优，需要启发函数可采纳才保证）
三、计算题
贪婪最佳优先搜索扩展顺序：A → D → E → K
*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
最优路径：A → D → E → K，总代价 = 3 + 12 + 3 = 18
贪婪搜索找到的路径：A → D → E → K，代价18（与最优一致，但不总是保证最优）
A* 搜索保证最优，路径同上。
如果你需要更多练习题，或希望我为你生成其他章节的复习材料，请告诉我！