电话

020-88823568

电子科技大学人工智能期末复习笔记(一):搜索问题

标签: 欧亿体育 2024-02-12 

目录

前言

人工智能历史

搜索问题

什么是搜索问题?

不知情搜索算法(Uninformed Search) 

一些重要概念

深度优先搜索(DFS)

广度优先搜索(BFS) 

代价敏感搜索(CCS) 

代价一致搜索(UCS) 

知情搜索算法(Informed Search) 

启发式搜索(Heuristics Search) 

贪心搜索(Greedy Search) 

A*搜索

图搜索(Graph Search) 

例题

实验:A*算法解决八数码问题

对抗搜索

零和游戏(Zero-sum Games)

极小化极大算法(Minimax Algorithm)

Alpha-Beta剪枝算法(Alpha-Beta Pruning) 

例题


前言

本复习笔记基于李晶晶老师的课堂PPT与复习大纲,供自己期末复习与学弟学妹参考用。


人工智能历史

简要了解即可。 


搜索问题

什么是搜索问题?

一个搜索问题包括一个状态空间,一个后续函数(包括动作,成本),一个开始状态和一个目标状态。

状态空间:当前“世界”所处的状态所有可能性的集合,假设整个状态空间是一段视频,那么状态就是视频的某一帧截图,它就是组成状态空间的一种可能。

后续函数:搜索问题的核心,它决定了代理下一步的动作是什么,也就是通过搜索算法来得出当前状态下如何决策是最符合预期的。后续函数中的参数必然含有动作和成本等协助判断的重要条件,通过这些条件就可以比对出当前状态下最好的决策。

解决方案:搜索问题的目标,是指将开始状态转换为目标状态的一系列操作(计划)。

计算状态空间的大小

将所有可能的环境/动作全部相乘。

很好理解,总状态空间就是代理位置、食物数量、敌人位置、代理方向四个因素来决定,而代理位置有120种可能,每一颗食物有存在/不存在两个状态,所以是2^30种可能,敌人有两个,一共有12种位置,所以敌人位置就有12^2种可能,代理的朝向有四种,就是4种可能。所以总状态空间的大小就是将它们相乘即可。 

状态空间图与决策树

搜索树中的每个节点都是状态空间图中的一个完整路径,两者都可以按需构建,还可以互相转化,例如根据状态空间图绘制决策树。

例:将图示状态空间图转化为决策树

我们引入两个列表:open_list 与 closed_list ,分别表示当前正在搜索的节点和已经搜索完毕的节点。open_list 初始只有起始状态S节点,而 closed_list 初始是空的。

求解过程:(这里其实使用了广度优先搜索

open_list closed_list 备注
0 S null 起始状态
1 d,e,p S 分解起始节点S
2 b,c,e,p S,d 依次分解S的子节点d,e,p
3 b,c,r,h,p S,d,e 依次分解S的子节点d,e,p
4 b,c,r,h,q S,d,e,p 依次分解S的子节点d,e,p
5 a,c,r,h,q S,d,e,p,b 依次分解d的子节点b,c
6 a,r,h,q S,d,e,p,b,c 依次分解d的子节点b,c
7 a,f,h,q S,d,e,p,b,c,r 依次分解e的子节点r,h
8 a,f,q S,d,e,p,b,c,r,h 依次分解e的子节点r,h(h的子节点p,q都已搜索过)
9 a,f S,d,e,p,b,c,r,h,q 分解p的子节点q(q没有子节点)
10 f S,d,e,p,b,c,r,h,q,a 依次分解剩余节点a,f(a没有子节点)
11 G S,d,e,p,b,c,r,h,q,a,f 依次分解剩余节点a,f(f搜索到了目标节点G)
12 null S,d,e,p,b,c,r,h,q,a,f,G G进入了closed_list,搜索结束。


不知情搜索算法(Uninformed Search) 

一些重要概念

完备:如果有解,一定能找到

最优:保证能找到代价最小的路径

时间复杂度:算法中的基本操作的执行次数,为算法的时间复杂度

空间复杂度:空间复杂度算的是变量的个数

深度优先搜索(DFS)

从上到下,从左到右

边缘节点是后进先出的堆栈形式

有限状态空间中,DFS是完备的

DFS不是最优的  (它只能找到解,在一定条件下也并不保证代价最小)

广度优先搜索(BFS) 

从左到右,从上到下

边缘节点是先进先出的队列形式

有限状态空间中,BFS是完备的

在动作未加权时,BFS是最优的

补充:迭代深化(Iterative Deepening)是旨在将DFS和BFS的优势结合在一起,既然BFS能够找到最浅的(最优的)解,而DFS可能会先找到较深的解,因此我们可以限制深度,先限制DFS的深度为3去搜索,如果没有找到就用最大深度为4的DFS去找,以此类推......这样就可以找到最浅的解从而节约算力。

  

为什么?明明多次迭代,为何反而节约算力?这是因为大量的计算通常在更深层,我们在浅层多次迭代不会影响太多时间/空间复杂度。 

代价敏感搜索(CCS) 

如下图,如果使用上述方法,无论是DFS,BFS抑或是迭代深化,都只能得到经过节点最少的路径,但是如果每个动作标明代价(加权)的话,经过最少节点的路径就不一定是最优解了。因此,上述方法并不能在代价敏感搜索当中得到最优解,只能通过进一步计算,算出代价从而选出代价最小的路径来实现。

 如上图,一共能找到两条路径:SderfG,SerfG。然而代价却分别是3+2+2+2+2=11和9+2+2+2=15,反而是经过节点较多的SderfG为最优解!

代价一致搜索(UCS) 

优先扩展代价最小的节点

(类似Dijkstra算法)

它是完备的且最优的

但缺点是每个方向都可能扩展,且不知道目标的确切方向会显得盲目(不知情搜索/Uninformed Search是这样的)

【解决方法:将UCS和Greedy(贪心算法)结合起来形成A*算法...下文会讲到】


知情搜索算法(Informed Search) 

如上图,知情搜索算法要讲解的分别为:启发式搜索,贪心搜索,A-star搜索,图搜索。

启发式搜索(Heuristics Search) 

一个启发式是:

▪一个函数,估计一个状态与目标的距离

▪为一个特定的搜索问题设计

▪例子:曼哈顿距离,欧氏距离

如图,10+5就是曼哈顿距离:横坐标之差与纵坐标之差的和;11.2是欧氏距离:直线距离。

这样的函数就叫作启发式函数,记作h(x)。 

贪心搜索(Greedy Search) 

优先扩展当前状态下最优的节点 

与UCS不同,UCS只考虑当前代价,而Greedy考虑了距离终点的距离。

它不是最佳的!通常它只考虑了距离而非代价,贪心算法的优劣很大程度上取决于启发式函数h(x)。 

A*搜索

A*搜索综合了UCS和Greedy,有两个评估函数g(x)与h(x),而A*搜索的决策取决于f(x)=g(x)+h(x),综合考虑了前驱因素与后继因素。

A*是完备且最优的。当f(x)=g(x)+0时就找到了最优解。

【但这里有一个大前提】:那就是估计节点到终点的距离时(h(x))一定要小于等于实际中s点到终点的距离才行,这叫做可采纳的试探(Admissible Heuristics)

 例如下图:

因此,提出一个可接受的启发式方法是A*算法的需要解决的重要内容(实际上上文提到过的曼哈顿距离和欧氏距离就是很好的启发式方法)。 

总结:

1. A*用前驱和(估计的)后继成本来决策;

2. A*在可接受的启发式方法下是最优的;

3. 启发式设计是关键所在,常用于宽松问题(Relaxed Problems)

图搜索(Graph Search) 

一种在图中寻找路径的方法。