人工智能

前言

姚期智《人工智能》学习记录。

第二章 搜索

一、几个概念

1、三大类搜索算法：单智能体搜索、局部搜索、多智能体对抗搜索
2、单智能体搜索针对单个智能体环境中的决策问题。它的搜索策略有两种基本方式：盲目搜索（无信息搜索策略）和启发式搜索（有信息引导搜索策略）
3、局部搜索是一种考虑如何在当前的解附近找到一个更优的解，从而逐步向最优解移动的方法。
4、多智能体对抗搜索主要存在于多个智能体竞争环境中。每一个智能体都需要考虑其他智能体的决策带来的影响，因而导致了博弈问题和对抗搜索的产生。

二、搜索问题的要素

1、状态空间S：所有可能的状态集合，而状态表示问题中考虑系统所处的状态。
2、初始状态s₀：描述系统的起始状态。
3、动作空间A：智能体所有可执行的状态集合。对于每个状态s，用A(s)描述在该状态下可用的动作集合。
4、转移函数T(s,a)：在状态s下执行动作a后系统达到的状态。
5、损耗函数c(s,a,s’)：在状态s下执行动作a后达到的状态s’的损耗。
6、目标测试函数G(s)：判断给定的状态s是否为目标状态。目标状态s可能是一个集合而不是单个状态。搜索在系统中到达其中一个目标状态后结束。

系统从初始状态到目标状态的一系列动作为一个解。解的好坏由路径上的总损耗度量，取得最小总损耗的解称为最优解。

三、搜索算法基础

1、搜索中重要的数据结构：图、树、队列。
2、图分为无向图和有向图。有向图中，到达一个节点的有向边数为该节点的入度，从一个节点出发的有向边数为该节点的出度。
3、图的路径：一个节点通向另一个节点所经过的边的序列；
4、图的路径长度：一个节点到另一个节点所经过边的总数量或所有经过边的权重之和；
5、连通图：如果一个无向图中任意两个节点之间都存在路径则为连通图；
6、强连通图：如果一个有向图中任意两个节点之间都存在路径则为强连通图。
7、树由节点和边构成，①每个节点只有一个父节点；②只存在一个根节点，它没有父节点。
8、树的高度或深度由树中节点的最大层次决定。
9、队列常用的三种形式：①先进先出队列(queue)；②优先级队列(priority queue)，队列中的元素按照某种函数计算的优先级排列，高优先级的元素先出队；③后进先出队列(堆栈stack）。

总结

刚开始……