1.人工智能中的问题求解

  • 解:是一个达到目标动作的序列。
  • 过程:寻找该动作,称其为搜索。
  • 问题形式化:给定一个目标,决定要考虑的动作与状态。
  • 为何搜索:对于某些NP完和NP难问题,只能通过搜索来解决。
  • 问题求解智能体:是一种基于目标的智能体,通过搜索来解决问题。

2.相关术语

  • 状态空间:可以形式化地定义为——初始状态、动作和转换模型。
  • 图:状态空间形成一个图,其中节点表示状态、链接表示动作
  • 路径:状态空间的一条路径是由一系列动作连接的一个状态序列。

3.问题形式化的5个要素

  • 初始状态:智能体出发时的状态。
  • 动作:描述智能体可执行的动作。
  • 转换模型:描述每个动作在做什么。
  • 目标测试:确定一个给定的状态是否为目标状态。
  • 路径代价:每条路径所分配的一个数值代价。

4.搜索算法

一种通用的搜索算法

screenShot.png

该frontier(也称为open list):一种数据结构,用于存储所有的叶节点。

在frontier上扩展结点的过程持续进行,知道找到一个解或者没有其它状态可扩展。

一种通用的图搜索算法

screenShot.png

该explored(也称为closed list):一种数据结构,用于记忆每个扩展结点。

explored和frontier中的结点可以被丢弃。

5.无信息搜索

定义:无信息搜索也被称为盲目搜索。该术语(无信息、盲目的)意味着该搜索策略没有超过问题定义提供的状态之外的附加信息。

所有能做的就是生成后继结点,并且从区分一个目标状态或一个非目标状态。

所有的搜索策略是由节点扩展的顺序加以区分。这些搜索策略是:宽度优先、深度优先以及一致代价搜索。

无信息搜索的策略评价

一种无信息搜索是通过选择结点扩展的顺序来定义的。

其策略可按照如下特性来评价:

  • 完备性。是否总能找到一个存在的解。
  • 时间复杂性:花费多长时间找到这个解。
  • 空间复杂性。需要多少内存。
  • 最优性:是否总能找到最优的解。

时间复杂性和空间复杂性用如下术语来衡量:

  • b–搜索树的最大分支因子。
  • d–最浅的深度。
  • m–搜索树的最大深度。

宽度优先搜索

搜索策略:扩展最浅的未扩展节点。

实现方法:使用FIFO(先进先出)队列,即新的后继结点放在后面。

screenShot.png

宽度优先搜索不能解决指数复杂性问题,小的分支因子除外。

一致代价搜索

搜索策略:扩展最低代价的未扩展节点。

实现方法:队列,按路径代价排序,最低优先。

screenShot.png

深度优先搜索

搜索策略:扩展最深未扩展节点。

实现方法:使用LIFO队列,把后继节点放在队列的前端。

-深度受限搜索

若状态空间无限,深度优先搜索就会发生失败,这个问题可以用一个预定的深度限制得到解决。

缺点:

如果我们选择l < d,即最浅的的目标在深度限制之外,这种方法就会出现额外的不完备性。

如果我们选择l > d,深度受限搜索也不是最优的。

screenShot.png

-迭代加深搜索

它将深度优先和宽度优先的优势相结合,逐步增加深度限制反复运行直到找到目标。

它以深度优先搜索相同的顺序访问搜索树的节点,但先访问节点的累积顺序实际是宽度优先。

screenShot.png

-双向搜索

它同时进行两个搜索:一个是从初始状态向前搜索,而另一个则从目标向后搜索。当两者在中间相遇时停止。

screenShot.png

该方法可以通过一种剩余距离的启发式估计来导向。

-无信息搜索树策略评价

screenShot.png

6.有信息搜索

有信息搜索也被称为启发式搜索,这类策略采用超出问题本身定义的、问题特有的知识,因此能够找到比无信息搜索更有效的解。

一般方法使用如下函数的一个或两者:

评价函数,记作f(n),用于选择一个节点进行扩展。

启发式函数,记作h(n),作为f的一个组成部分。

-最佳优先搜索

搜索策略:一个节点被选择进行扩展是基于一个评价函数,f(n)。大多数的最佳优先搜索算法还包含一个启发式函数,h(n)。

实现方法:与一致代价搜索相同。然而,最佳优先搜索使用f(n)代替g(n)来整体优先队列。

启发式函数h(n):从节点n到目标状态的最低路径估计代价。

特例:贪婪搜索、A*搜索

贪婪搜索

搜索策略:试图扩展最接近目标的节点。

评价函数:f(n) = h(n)

它仅使用启发式函数对节点进行评价。

迭代加深A搜索*

  • 它是迭代加深深度优先搜索的变种,从A*搜索算法借鉴了这一思想,即使用启发式函数来评价到目标的剩余代价。

它是一种深度优先搜索算法,内存使用率低于A*算法。但是,不同于标准的迭代加深搜索,它集中于探索最有希望的节点,因此不会去搜索树任何处的同样深度。

比较:

  • 迭代加深深度优先搜索:使用搜索深度作为每次迭代的截止值。
  • 迭代加深A*搜索:使用信息更丰富的评价函数,f(n) = g(n) + h(n)

g(n):到达该节点的代价 h(n):该节点到目标的估计代价