重点:人工智能定义、人工智能研究内容(了解、理解即可)
一、知识的概念重点:知识的概念、知识的表示
知识是人们在长期的生活及社会实践中、在科学研究及实验中积累起来的对客观世界的认识与经验。 知识的形式:事实、因果关联 知识的特性:相对正确性(明确前提)、不确定性(真假之外)、可表示性(形式描述)、可利用性(学以致用)
练习题知识的概念![在这里插入图片描述](https://i-blog.csdnimg.cn/blog_migrate/a1541e8b4e5ff11ca6226b2ded01f83c.png)
· 状态:表示问题解法中每一步问题状况的数据结构 · 操作:状态变换的手段 · 状态空间:表示问题全部可能状态及其关系的图 · 状态空间的解:从初始状态到目标状态的操作算子序列
只按预定的控制策略进行搜索,在搜索过程中获得的中间信息不会用来改进控制策略。
每个节点的分支数为b,最浅解位于第s层,搜索空间共m层。
2.2.1 宽度优先搜索【队列】时间复杂度:O(b sb^sbs) 空间复杂度:O(b sb^sbs) 具有完备性、最优性
2.2.2 深度优先搜索【栈】时间复杂度:O(b mb^mbm) 空间复杂度:O( b m bmbm) 可能不具有完备性(图有环时需进行约束)、不具有最优性(最左的解)
2.2.3 一致代价搜索【优先队列】 解代价为C ∗ C^*C∗,边最小代价为εεε
时间复杂度:O(bC∗/εb^{C^*/ε}bC∗/ε) 空间复杂度:O(bC∗/εb^{C^*/ε}bC∗/ε) 具有完备性、最优性
练习题一致代价搜索的终止条件: 无信息搜索在搜索中加入了与问题有关的启发性信息,用于指导搜索朝着最有希望的方向进行,加速问题的求解过程并找到最优解。
2.3.1 贪婪搜索【优先队列】搜索策略: 拓展看起来离目标最近的节点 评估函数:f(n)=h(n)f(n)=h(n)f(n)=h(n)【h(n)h(n)h(n)表示从nnn节点到目标节点最佳路径的估计代价】
最坏情况下退化为DFS,时间复杂度为O(b mb^mbm) 空间复杂度:O(b mb^mbm)【存储所有节点的信息】 不具有完备性和最优性
2.3.2 A*搜索【优先队列】搜索策略: 避免拓展耗费已经很大的路径 评估函数:f(n)=g(n)+h(n)f(n)=g(n)+h(n)f(n)=g(n)+h(n)【g(n)表示初始节点到n节点的实际代价、h(n)表示估计代价】
可纳性 如果对任意节点 𝑛 𝑛n, h ( n ) ≤h ∗( n ) h(n)≤h^*(n)h(n)≤h∗(n)成立, 则启发式函数是可纳的(admissible), 其中,h ∗( n ) h^*(n)h∗(n)是结点 𝑛 𝑛n到目标状态的真实代价。定理:若h(n)h(n)h(n)可纳,则A*搜索算法具有最优性。
一致性(一致->可纳) 若对于任意节点 n nn和通过操作 a aa生成的后续节点n ′n'n′,则 h ( n ) ≤ c o s t ( n , a ,n ′) + h (n ′) h(n)≤cost(n,a,n')+h(n')h(n)≤cost(n,a,n′)+h(n′)成立,则启发式函数是一致的定理:若h(n)h(n)h(n)一致,则A*搜索算法具有最优性。
优势性 对于任意节点 nn n,可纳启发式函数h1 ( n )