主页 > 周刊

人工智能——无信息搜索(盲目搜索)

时间:2019-10-05 来源:一起做游戏

摘要

本章旨在讲清楚:1)搜索问题如何形式化;2)树搜索,图搜索,及算法评估;3)一些搜索策略:宽度优先,一致代价,深度优先,深度受限,迭代加深,双向搜索。


前言

这一章说的是Agent,但是是搜索Agent,所以主要讲的是各种搜索算法(search algorithms)。


这篇文章的意义在于哪里呢? 

1)向大家展示如何形式化定义一个搜索问题,又如何去求解; 

2)通过讲述各种盲目搜索算法,帮大家梳理无信息搜索的脉络。


不多说了,得进入正题了。


一、形式化一个搜索问题

1.1 问题的定义 

用5个组件形式化定义一个search problem: 

1)initial state 初始状态 

2)Actions 行动 

3)transition model 转移模型 

4)goal test 目标测试 

5)path cost 路径耗散


前三个直接定义了问题的状态空间(问题的解决方案通常就在这个状态空间里面)。


上述五个元素即定义了一个问题,通常把它们组织在一起成为一个数据结构,并以此作为问题求解算法的输入。


1.2 问题的解(solution)的定义

A solution to a problem is an action sequence that leads from the initial state to a goal state.


即:一个问题的解是:一个行动序列(注意:agent是能够通过感知环境,进行思考,然后采取行动的,所以这篇文章的题目叫搜索Agent)。


那最优解是什么呢? 

答:解的质量由路径耗散函数度量,所有解里路径耗散最小的解即为最优解。


1.3 为什么要搜索算法?

因为状态空间太大啦。比如,8数码问题有362,880(排列组合,A89=362,880)个状态,15数码问题有A1516=20922789888000个状态,24数码就更加更加大了。


所以我们需要搜索算法(相当于一种求解模式吧,比那种“无头苍蝇”式的随便找解的 是要好得多的。)来在巨大状态空间中求解。


二、如何通过搜索求解呢(主要讲树搜索和图搜索)?

以罗马尼亚问题(即:如何从罗马尼亚的Arad走到Bucharest)为例,可能的行动序列(即问题的解)从搜索树中根节点的初始状态出发:连线表示行动,节点表示状态空间中的状态(该问题总共20个地点,故有20个状态)。搜索的过程就是从初始状态节点不断扩展节点(状态),指导goal test检测到达到目标为止。


那么,如何选择将要扩展的状态,对应的就是搜索策略(图搜索,树搜索)了。这里给出图搜索和树搜索的非形式化描述: 

解释:对于树搜索,先从初始节点开始扩展,初始化边缘(frontier,即待扩展的叶节点的集合),如果边缘为空,就失败呗(因为没有能够扩展的节点了,自然GG),否则,从边缘中选择一个叶节点并且并且把它从边缘移除,如果这个叶节点包含目标状态,那就返回对应的解。否则,扩展这个叶节点,并且把扩展出来的节点放到边缘中(不断探索可能的解)


对于图搜索,基本和树搜索一样,但是图搜索有一个额外的处理重复状态的过程。(需要:初始化一个explored set,如果这个叶节点被探索过了,就丢到explored set中;如果这个叶节点的扩展子节点也被探索过了,那就不加到frontier)


2.2 搜索的数据结构

注意:树搜索和图搜索都是在“树”这一个数据结构上进行的,所以搜索算法需要一个数据结构来记录搜索树的构造过程。


所以对树中每个节点n,定义如下数据结构


n.state:状态

n.parent:父节点

n.action:父节点生成该节点时采取的行动

n.path-cost:代价,从初始节点到该节点的路径消耗,也叫g(n)

具体实现的时候,要用到 

1)用队列来存放节点(FIFO,LIFO,优先级队列) 

2)用哈希表存放已扩展节点表 (实现的好的话,插入和查找操作的时间消耗是常数)


2.3 问题求解算法的性能

四个方面:


完备性(当问题有解时,这个算法能否保证找到解)

最优性(搜索策略能否找到最优解)

时间复杂度(找到解要花多长时间) 也叫搜索代价

空间复杂度(在执行搜索的过程中需要多少内存) 

总代价=搜索代价+内存使用(空间复杂度)


三、无信息搜索(盲目搜索)策略

这些搜索策略是以节点扩展的次序来分类的(宽度优先,一致代价,深度优先,深度受限,迭代加深,双向搜索)。


3.1 宽度优先搜索 breadth-first search (BFS)

宽度优先搜索是一般图搜索算法的一个实例,每次总是扩展深度最浅的节点,这可以通过将边缘组织成FIFO队列来实现(即,新节点加入到队列尾,浅层的老节点会在深层节点之前被扩展)。


性能:是完备的(只要有解,肯定能搜到。当然,前提是最浅的目标节点处于一个有限深度d,分支因子b也是有限的)BFS找到的永远是最浅的目标节点,但不一定最优,只有当路径代价是基于节点深度的非递减函数时,BFS是最优的(最常见情况是所有行动要花费相同的代价)。 

假设每个状态都有b个后继状态,解的深度为d,那么时间复杂度就是O(bd)O(bd),空间复杂度也是O(bd)O(bd)。这种指数级的复杂度就太大了。 

(一般而言,指数级别复杂度的搜索问题不能用无信息的搜索算法求解,除非是规模很小的实例)


3.2 一致代价搜索 Uniform-cost search (UCS)

一致代价搜索扩展的是路径消耗g(n)(从初始状态到当前状态的路径耗散)最小的节点n。(可以通过将边缘节点组织成按g值排序的队列来实现)


一致代价搜索和宽度优先搜索的区别:1)目标检测应用于节点被选择扩展时,而不是在节点生成的时候。原因:一致代价搜索希望在替换代价更小的节点后再确认解;2)如果边缘中的节点有更好的路径到达该节点,那么会引入一个测试。


性能:是最优的。如果每一步的代价都大于等于某个小的正常数,那么就是完备的。


一致代价的复杂度较高:O(b^(1+[C∗/e])),其中C∗是最优解的代价,每个行动的代价至少为e,所以最坏情况下,这个复杂度要比BFS的复杂度b^d大的多。(因为一致代价搜索在探索包含代价大的行动之前,经常会探索代价小的行动步骤所在的很大的搜索树)


当所有单步耗散都相等时,复杂度变为b^(d+1)。这种情况下,由于一致代价搜索和BFS的第一个区别,一致代价搜索会在深度d上做更多无用功(因为他是在选择节点的时候才判断是不是目标达到)。


3.3 深度优先 depth-first search (DFS)

深度优先总是扩展搜索树的当前边缘节点集 中最深的节点(搜索直接推到最深层)。如果最深层节点扩展完了,就回溯到下一个还有未扩展节点的深度稍浅的节点。


DFS使用LIFO队列(最新生成的节点最早被扩展),而且要调用自己的递归函数来实现DFS算法。(有深度界限的递归深度优先搜索算法)

性能: 

DFS的搜索效率严重依赖于使用的是图搜索还是树搜索。 

如果是图搜索(避免了重复状态和冗余路径),那么DFS在有限状态空间就是完备的。 

如果是树搜索,则不完备,因为会出现死循环(DFS算法本身是没有explored set的)。


不是最优的。


复杂度:时间复杂度受限于状态空间的规模,为:O(b^m),m是任一节点的最大深度。这比d(最浅解的深度)要大的多。 

但是空间复杂度很给力,为O(bm)。所以DFS在AI的很多领域成为工作主力。


此外,还有一种变形叫做回溯搜索(backtracking search):每次只产生一个后继而不是生成所有后继,每个被部分扩展的节点要记住下一个要生成的节点。这样,内存只需要O(m)而不是O(mb)。


3.4 深度受限

设置界限l来避免DFS在无限状态空间下搜索失败的尴尬情况。即,深度为l的节点被当做最深层节点(没有后继节点)来对待。


3.5 迭代加深的深度优先算法 iterative deepening search(IDS)

IDS = DFS + BFS。 

可以说是结合了宽度优先和深度优先的优点了:1)空间复杂度:O(bd) (和DFS一样);2)在分支因子有限时完备,在路径待机时节点深度的非递减函数时最优(和BFS一样)。


3.6 双向搜索

一个从初始状态开始搜,一个从目标状态开始搜,当边缘有交集,就说明找到了解。


好处:如果两个都用BFS,那么复杂度就变成了 

O(bd/2)+O(bd/2)O(bd/2)+O(bd/2),这肯定是要远远小于O(bd)O(bd)的。所以说减小了复杂度。


四、总结

写的有点累,因为知识点很多,而且我觉得也很难讲清楚。毕竟这些知识都是“硬知识”,如果要讲的非常生动,我觉得可能就不是我一上午(花了3个小时)能做完的事情了。


所以当然还是有点遗憾的,我也希望讲的各种生动形象,但是如果真要生动形象的话,这一章里面每一个知识点拿出来,都可以洋洋洒洒一大篇锦绣文章。我觉得可以做到,但是时间的确不允许。以后有机会,会重点将一些有针对性的知识点。


但是这篇文章的意义在于哪里呢? 

1)向大家展示如何形式化定义一个搜索问题,又如何去求解; 

2)通过讲述各种盲目搜索算法,帮大家梳理无信息搜索的脉络。(直接放在文章开头是不错的选择)


所以还是有些价值的。希望以后能够不断进步,写出更好的文章。


参考文献

[1] StuartJ.Russell, PeterNorvig, 诺维格,等. 人工智能:一种现代的方法[J]. 2013. 

[2] 人工智能 一种现代的方法(第3版). https://blog.csdn.net/weixin_39278265/article/details/80906740 




微信号:ywcclzy