1. 搜索在人工智能中的核心地位作为人工智能领域最基础也最重要的技术之一搜索算法构成了智能系统决策能力的骨架。我在准备国科大高级人工智能课程期末考试时发现搜索这一章节的内容既基础又关键值得专门整理成系统的复习笔记。搜索技术本质上是一种系统化的信息探索方法它通过定义状态空间和转移规则寻找从初始状态到目标状态的有效路径。这种思想不仅存在于传统的路径规划问题中也渗透到了现代AI的各个分支——从博弈树的构建到神经架构搜索从推荐系统的候选集生成到自动定理证明搜索的身影无处不在。2. 搜索问题形式化定义2.1 基本要素解析一个标准的搜索问题可以形式化为五元组(S, A, T, C, G)S状态集合表示系统可能处于的所有情况A动作集合描述状态间可能的转移方式T转移函数T(s,a)→s 定义执行动作后的状态变化C代价函数通常记为c(s,a,s)衡量特定转移的代价G目标状态集合即需要到达的状态在实际应用中我们常用状态空间图来表示这个问题框架。图中的节点对应状态边对应动作边的权重反映转移代价。这种可视化表示对于理解搜索过程特别有帮助。2.2 关键指标评估评价搜索算法性能时我们主要关注三个维度完备性当解存在时算法是否能保证找到解最优性算法是否能找到代价最小的解时间复杂度执行所需的时间或计算资源空间复杂度算法运行过程中需要存储的信息量这些指标之间往往存在trade-off实际应用中需要根据具体场景进行权衡。例如在实时性要求高的场景可能牺牲最优性换取速度而在安全关键系统中则更看重完备性和最优性。3. 经典搜索算法精要3.1 无信息搜索策略3.1.1 广度优先搜索(BFS)BFS系统地逐层扩展节点使用队列数据结构实现。它的显著特点是完备性在状态空间有限时具有完备性最优性当所有动作代价相同时能找到最优解复杂度时间空间都是O(b^d)b为分支因子d为解深度提示BFS在解较浅时效率高但当解深度较大时内存消耗会急剧增加。3.1.2 深度优先搜索(DFS)DFS沿着一条路径深入探索直到尽头再回溯尝试其他分支通常用栈或递归实现完备性在有限无环状态空间中完备最优性不保证找到最优解复杂度时间O(b^m)空间O(bm)m为最大深度3.1.3 一致代价搜索(UCS)UCS通过优先扩展路径成本最低的节点来保证最优性使用优先队列按g(n)到达n的总成本排序完备且最优但效率取决于成本分布复杂度时间空间均为O(b^(1⌊C*/ε⌋))C*为最优解成本3.2 启发式搜索算法3.2.1 A*搜索A*结合了UCS和启发式函数h(n)使用f(n)g(n)h(n)作为评估函数当h(n)是可采纳的不高估实际成本时A*具有最优性当h(n)是一致的满足三角不等式时A*效率更高常用的启发式函数包括曼哈顿距离、欧几里得距离等3.2.2 启发式函数设计原则好的启发式函数需要在准确性和计算成本间取得平衡可采纳性保证最优性更高的h(n)值不违反可采纳性通常带来更好性能可以通过松弛原问题减少限制条件来获得可采纳启发式从子问题解构造启发式如模式数据库4. 搜索优化与实践技巧4.1 内存优化策略迭代加深结合DFS的空间效率和BFS的完备性适用于大状态空间双向搜索同时从初始状态和目标状态搜索减少搜索空间分支限界利用当前最优解剪枝不可能更优的分支4.2 启发式搜索实现细节使用斐波那契堆等高效优先队列实现对h(n)进行缓存以避免重复计算当状态空间巨大时考虑使用近似算法或随机化搜索4.3 实际应用案例路径规划机器人导航、游戏AI调度问题任务分配、资源调度组合优化背包问题、旅行商问题定理证明逻辑推理、自动推导5. 考试重点与常见题型分析根据历年考题和课程重点搜索部分的考查通常集中在以下几个方面5.1 算法性质判断题给定场景判断算法是否完备/最优比较不同算法的适用场景分析特定启发式函数的性质5.2 算法执行模拟题手动执行若干步搜索算法如A*绘制搜索树并标注评估值跟踪优先队列/栈/队列的状态变化5.3 启发式设计题为特定问题设计可采纳的启发式证明启发式的可采纳性或一致性分析启发式对搜索效率的影响5.4 复杂度分析题计算特定场景下的时空复杂度比较不同算法的复杂度特征分析分支因子、解深度等参数的影响6. 典型问题解析与避坑指南6.1 启发式一致性误区很多同学容易混淆可采纳性和一致性。记住所有一致的启发式都是可采纳的但可采纳的启发式不一定是一致的一致性要求h(n)≤c(n,a,n)h(n)比可采纳性更强6.2 图搜索与树搜索区别图搜索需要维护已探索集closed set以避免重复这会增加空间复杂度但防止重复工作树搜索可能陷入循环但在无限状态空间中有意义6.3 动态环境下的搜索考试可能考察动态变化的环境D*算法等增量式搜索方法如何重用之前的搜索信息实时搜索与规划的结合7. 现代AI中的搜索技术演进虽然我们主要复习了经典搜索算法但了解其在现代AI中的发展也很重要7.1 局部搜索与优化爬山法、模拟退火、遗传算法适用于大规模状态空间的近似求解放弃完备性和最优性换取效率7.2 蒙特卡洛树搜索(MCTS)结合树搜索与随机采样的强大方法在AlphaGo等系统中表现突出特别适合博弈等具有随机性的场景7.3 深度学习与搜索的结合用神经网络学习启发式函数神经架构搜索(NAS)自动设计网络结构将搜索空间编码为潜在表示在准备这类前沿内容时重点理解经典方法如何与新技术结合而不是死记硬背具体实现。考试通常考察的是对核心概念的迁移理解能力。
