人工智能基础

第二章知识表示

第三章确定性推理

第四章搜索

搜索：通过适当的搜索算法在状态空间中搜索解答路径

问题求解系统：

知识贫乏搜索
知识丰富推理

搜索技术：

一般图搜索+启发式
与或图

推理技术：

基于归结归结反演
基于规则正向/逆向演绎推理

在哪里搜索就是“搜索空间”，又称为状态空间。

人工智能中大多数问题的状态空间在问题求解之前不是全部知道的

根据是否使用启发式信息分为：

盲目搜索：按预定的搜索策略进行搜索
启发式搜索：在搜索过程中加入了与问题有关的启发式信息加速问题的求解并找到最优解

问题的表示方式:

状态空间搜索
1. dfs 最深层扩展，死亡节点返回上层
2. bfs 扩展根节点的所有后继
与或图

评价标准：

完备：找到 1 个解
最优：找到最优解
时间复杂度
空间复杂度

一般图搜索

状态空间=可走的合法状态+操作算子

节点+有向弧+操作算子

open 表：待扩展节点
close 表：已被扩展节点

盲目搜索

改进：open 表的排列方式

	open 表	close 表
bfs	新节点放在尾部，作为队列使用，先进先出，横向发展
dfs	新节点放在头部，作为栈使用，后进先出，纵向发展

bfs 优缺点：

完备性最优性通用图搜索
时空复杂度高

dfs 优缺点：

空间小
不完备不最优

有界深度优先搜索：dfs+深度限制

迭代加深搜索：dfs+自动更新的深度限制

b：分支数
d: 解深度
m: 树深度
l: 深度限制

	bfs	dfs	dfs plus	dfs pro max
时间	$b^{d}$	$b^{m}$	$b^{l}$	$b^{d}$
空间	$b^{d}$	bm	bl	bd
最优	是	否	否	是
完备	是	否	l>d 是	是

启发式搜索

A

评价函数：f(n)=g(n)+h(n)

g(n): s 到 n 代价，如深度

h(n): 扩展节点需要的代价

相较于一般图增加排序操作

A*

搜索算法的可采纳性：满足最优性，能找到最短路径

A*满足可采纳

评价函数：f*(n)=g*(n)+h*(n)

h(n)尽可能靠近 h*(n) ——A 算法的关键

在 A 算法中，规定 h(n)≤h*(n); 经如此限制以后的 A 算法就是 A* 算法。

h(n)接近 h*(n)的程度——衡量启发式函数的强弱：

h(n)<h*(n)且差距较大时，OPEN 表中节点排序的误差较大， h(n)过弱，产生较大的搜索图；
h(n)>h*(n)，h(n)过强，A 算法失去可采纳性，不能确保找到最短解答路径；
h(n)=h*(n)是最理想的， OPEN 表中节点排序没有误差，可以确保产生最小的搜索图，搜索到最短解答路径；

h(n)=0 = bfs
g(n)=0 = dfs 爬山法

与或图搜索

问题规约：复杂问题简单化

根节点：
叶节点：
终节点：一定是叶节点，一组叶节点

解图纯粹是一种“与”图

解图代价: 以 C(n) 指示节点 n 到终节点集合解图的代价，并令 K 连接的代价就为 K, 则

c(n) = 0 终节点
c(n) = k + c(n1) + …… k 连接节点

能解节点：

终节点是能解节点；
若节点 n 有一 K-连接指向子节点 n1，n2，…nk,且这些子节点都是能解节点，则 n 是能解节点；

不能解节点

非终节点的叶节点是不能解节点；
若节点 n 的每一个 K-连接都至少指向一个不能解节点，则 n 是不能解节点。

AO*

与或图中搜索的是解图，不是解答路径

f(n) = h(n)

h(n) 解图代价最小估计

G’-被选中的待扩展局部解图 open 表
LGS-待扩展局部解图集； close 表
n0-根节点，即初始状态节点；
n-被选中的待扩展节点；
fi(n0)-第 i 个待扩展局部解图的可能代价。

	A*	AO*
解	解答路径	解图
扩展	open 表中 f(n)最小	代价最小的局部解图
f(n)	g(n)+h(n)	h(n)
存	LGS	open+close

博弈

博弈树

博弈树的“与”节点和“或”节点是逐层交替出现的

析取取最小，合取取最大

α-β 过程

MAX 节点的 α 值永不下降；
MIN 节点的 β 值永不增加。

第五章不确定推理

主观贝叶斯

cf

对 H 的信任增长度等于对非 H 的不信任增长度。
对 H 的可信度与对非 H 的可信度之和等于 0。
可信度不是概率

当证据 E 肯定为真时：CF(E)=1；
当证据 E 肯定为假时：CF(E)=-1；
当证据 E 一无所知时：CF(E)=0。

证据

bel

第二章 知识表示

第三章 确定性推理

第四章 搜索