墨尔本大学COMP90054-AI-Planning课程：搜索策略与最优化

"这是一份来自The University of Melbourne的COMP90054-AI-Planning课程的重点笔记，主要涵盖了人工智能领域中的搜索算法、规划策略以及启发式函数等相关知识点，对于学习者准备考试非常有帮助。" 在人工智能的路径规划问题中，搜索算法扮演着至关重要的角色。本笔记首先提到了两种常见的搜索算法——统一成本搜索（uniform-cost search）与贪婪最佳优先搜索（greedy best-first search）。统一成本搜索基于Dijkstra算法，它的目标是找到从起点到单个目标点的最短路径，而非到达所有点的最短路径。这一算法在空间需求上相对较小，使用优先级队列，并且随着搜索的进行逐渐填充。相比之下，Dijkstra算法则是寻找从根节点到图中每个节点的最短路径，初始时优先级队列会将所有节点以无限成本添加进去。 搜索状态（search states）与世界状态（world states）之间的区别在于，回归规划（regression planning）从目标状态开始逆向工作，寻找到达初始状态的路径，每个搜索状态可能包含一组世界状态。而在进展规划（progression planning）中，搜索状态与世界状态是等价的。笔记还强调了节点生成（node-generation）与节点扩展（node-expansion）的概念，指出节点扩展在计算时间复杂度上更高，因为它涉及生成更多的后代节点。 启发式函数（heuristic function）在搜索算法中用于估计剩余成本（remaining cost, h*），它提供了一个解决方案存在的保障，即如果从某个状态存在解决方案，则该状态的启发式函数值h(s)小于无穷大。启发式函数的性质、盲目搜索与启发式搜索之间的关系，以及它们在时间和空间复杂度上的差异也是笔记中的重要内容。 盲目搜索（如广度优先搜索Breadth-First Search, BFS）是一种系统性的无信息搜索，其时间复杂度为O(b^d)，其中b是分支因子，d是深度。BFS使用队列存储节点，并保证完备性，即使存在循环也能找到路径，但不保证最优解。启发式搜索（或称为知情搜索）则依据启发式信息，通常能在更少的步骤中找到解决方案，但可能需要更多的内存空间。 这些笔记内容深入浅出地介绍了人工智能中规划与搜索的基本概念，对于理解和掌握AI中的路径规划策略具有很高的价值。