问题求解Agent
有一些问题无法通过单独的行动得出解，需要行动序列达到目标，则需要使用搜索法。
搜索：寻找能够达到目标的行动序列
无信息搜索：算法除了问题定义本身没有任何其他信息。
有信息搜索：利用给定的知识引导能够更有效地找到解。
问题形式化：在给定目标下确定需要考虑哪些行动和状态的过程。
抽象：除去细节的过程被称为抽象。如果执行解中的每个行动比原始问题中的容易，那么这种抽象是有用的。
问题形式化
一个问题形式化由下面5个组成部分组成
- 初转状态
在罗马尼亚问题中，初始状态为In(Arad) - 描述可能的行动
- 给定一个状态s，ACTIONS(s)返回在状态s下可以执行的动作集合。称这些状态读s是可用的。
在罗马尼亚问题中，考虑状态In(Arad)，可应用的行动为：（ { Go(Sibiu) , Go(Timisoara) , Go(Zerind)} ） - 转移模型（对每个行动的描述）
用函数RESULT(s,a)描述：在状态s下执行行动a后到达的状态。 - 目标测试
确定给定的状态是否是目标状态。
在罗马尼亚问题中，目标状态集是一个单元素集合{In(Bucharest)} - 路径耗散
此函数位每条路径赋一个耗散值，即边加权。行动a从状态s走到s’的单步耗散用c(s, a, s’)表示
可以看出，由初始状态、行动和转移模型就定义了问题的状态空间，即从初始状态可以到达的所有状态的集合。
问题实例
玩具问题：滑块问题，八皇后问题，Knuth
现实世界问题：TSP，VLSI布线，机器人导航，自动装配
吸尘器问题 （玩具问题）
状态：由Agent位置和灰尘位置确定，世界状态有n*2的n次方，有n个位置，而且是有或没有灰尘
初始行动：任何状态都能被设计成初始状态
行动 ：行动有3个：左、右、吸
转移模型：最左边不能再左，最右边不能再右
目标测试：检测所有位置是否干净
路径消耗：路径耗散值为1，因此整个路径的耗散值是路径中的步数
通过搜索求解（树搜索、图搜索）
罗马尼亚状态空间图如下：（从Arad到Bucuresti）
边缘（开结点表）：在任一给定时间点，所有待扩展的叶节点的集合；
探索集（closed表）：记录每个已扩展过的结点。
一般的树搜索和图搜索算法的非形式化描述：
树搜索
树搜索中有冗余路径
（ frontier：已生成未拓展；closed：已拓展）
图搜索
避免探索冗余路径的方法是牢记曾经走过的路。图搜素在树搜索算法上增加了一个参数：探索集（closed表）：记录每个已扩展过的结点。新生成的结点若于已经生成的某个结点相匹配的话，即是在探索集或是边缘集中，那么它将被丢弃而不是加入到边缘集中。
下图是罗马尼亚问题的图搜索过程：
图搜索只需三步即可到达目标：
图搜索的一个特点：边缘将状态空间图分成了已探索区域和未被探索区域，因此从初始状态出发至任一未被探索状态的路径都不得不通过边缘中的结点。
搜索算法基础
一个解是一个行动，搜索算法考虑各种可能的行动序列
n.STATE : 对应状态空间中的状态
n.PARENT : 搜索树种产生该结点的结点
n.ACTION : 父结点生成该结点时所采取的行动
n.PATH-COST: 代价，一般用 g(n) 表示，指从初始状态到该结点的路径消耗
队列
- FIFO队列：先进先出
- LIFO队列：栈，后进先出
- 优先级队列：根据函数计算最高优先级，具有最高优先级的队列出队
问题求解算法的性能
评价性能的标准
- 完备性：是否保证找到解
- 最优性：找到的解是否最优
- 时间复杂度：找到解需要多少时间
- 空间复杂度：在执行搜索过程中需要多少内存
复杂度的表达
- b：分支引子 任何节点的最多后继数
- d：深度 目标节点的最浅深度 根节点到目标节点的步数
- m：状态空间中任何路径的最大长度
评价搜索有效性—搜索代价，通常由时间复杂度和空间复杂度决定
无信息搜索策略（盲目搜索）
无信息搜索（盲目搜索）：除了问题定义中提供的状态信息外没有任何附加信息的搜索。
当搜索空间较大并且不知道解所在深度时，迭代加深的深度优先搜索是首选的无信息搜索方法。
宽度优先搜索（广度优先搜索）（BFS）
a) 概念：先扩展根结点，接着扩展根结点的所有后继，每次总是扩展深度最浅的结点，然后再扩展它们的后继。
b) 评价：
- 完备的（分支因子b有限时）；
- 最优的（如果路径代价是基于结点深度的非递减函数，比如step cost保持是1，则是最优的）；
- 时间复杂度
如果目标检测是在选择扩展的结点时:O(b^d)
如果选择要扩展的结点在结点生成时才检测，那么目标结点到之前深度d时已经被扩展，此时为O(b^(d+1)) - 空间复杂度 O(b^d) ，有 O(b^(d-1) )个结点在搜索集中，O(b^d)个结点在边缘集中。
默认：Time and space complexity is 1+b+…+b^d =O(b^d)
- 使用FIFO队列实现
一个简单二叉搜索树的搜索过程：
一致代价搜索（Uniform-cost Search）
每一步的行动代价都相等时，BFS是最优的。因为它总是选择先扩展深度最浅但是未扩展的结点。
a) 概念：扩展的是路径消耗g(n)最小的结点n（g(n)指从初始状态到该结点的路径消耗 ）。
这可以通过将边缘结点按路径代价g值进行排序的队列来实现
b) 评价：
- 完备的（如果每一步代价都大于等于某个小的正值常数）；
- 最优的；
- 时间复杂度和空间复杂度在最坏情况均比宽度优先搜索大（因为可能搜索一些对结果无用的树，一致代价搜索可能会检查目标深度所有结点看谁的代价小，在这种情况下一致搜索在深度d无意义地做了更多的工作）。
c)特点（和BFS的区别）
- 将边缘结点按路径代价g值进行排序的队列来实现
- 目标检测应用于结点被选择拓展时，而不是在结点生成的时候
- 如果边缘中的节点有更好的路径到达该节点，则会引入一个测试
例子：考虑下图（初始状态S，目标状态G）
树搜索
图搜索
深度优先搜索(DFS)
a) 概念：总是扩展搜索树的当前边缘结点集（叶节点）中最深的结点。
b) 评价：
- 完备性：避免冗余路径和重复状态的图搜索，在有限空间中是完备的，但树搜索的DFS则不完备，有可能陷入死循环中。在无限状态空间中，则均可能陷入死循环中
- 最优性：无论基于图搜索还是树搜索的DF算法都不是最优的
- 时间复杂度O(b^m)受限于状态空间的规模（可能是无限的）；
m:叶子结点的最大深度
b:分支因子
d:目标结点的最浅深度 - 空间复杂度O(bm)（只需要存储一条从根结点到叶结点的路径，以及该路径上每个结点的所有未扩展的兄弟结点）；
c) 变形——回溯搜索：空间复杂度O(m)（每次只产生一个后继而不是生成所有后继，每个被部分扩展的结点要记住下一个要生成的结点）；
d)使用LIFO队列实现（栈）
深度受限搜索(Depth Limited Search:DLS)
a) 概念：在深度优先搜索基础上设置界限l来避免无限状态空间深度优先搜索失败的问题（深度为l被当作没有后继对待）。
b) 评价：
- 完备的(l大于d)|不完备的(l小于d，则最浅的目标结点搜索不到)；
- 不是最优的；
- 时间复杂度O(b^l)；
- 空间复杂度O(bl)；
深度优先搜索可以看作是特殊的深度受限搜索，其深度l=∞
深度受限搜索可以通过修改一般的树搜索或图搜索算法来实现。
迭代加深的深度优先搜索(Iterative Deepening Search:IDS)
定义：不断地增大深度限制，不断执行深度受限搜索。当深度界限达到d，即最浅的目标结点所在深度时，就能找到目标。
性能：
- 完备性：分支引子b有限时完备
- 最优性：路径代价是节点深度的非递减函数时最优
- 空间复杂度：O(bd)
d: the depth of the shallowest goal node
问题：当深度为3时，有多少个结点被生成？
双向搜索(Bidirectional search)
定义：同时运行两个搜索，一个从初始状态向前搜索，另一个从目标状态向后搜索，目标检测是检查两个方向的边缘结点集是否相交，如果交集不为空就找到了解。
理由是b(d/2)+b(d/2)要比b^d小很多。
性能：
- 完备性：分支引子有限时完备
- 最优性：不一定是最优的
- 时空复杂度：O(b^(d/2))
难点：如何向后搜索，部分问题可以向后搜索，但有些问题向后搜索会使得分子引子很大。
有信息的搜索策略（启发式搜索）
有信息搜索：使用问题本身的定义之外的特定知识进行搜索
评估函数f(n):代价估计
最佳优先搜索的图搜索的实现与一直代价搜索类似，不过最佳优先是根据f值而不是g值进行优先级队列排队的
启发式函数（heuristic function）：h(n) = 结点n到目标结点的最小代价路径的代价估计值。若n是目标结点，则h(n)=0
- f(n)：经过结点n的最小代价解的估计代价（有可能略小于真实代价）
- g(n)：到达此结点已经花费的真实代价
- h(n)：从该结点到目标结点所花代价
evaluation function f(n)
- f(n) = g(n) ，Uniform Cost 一直代价搜索
- f(n) = h(n)，Greedy Best-First 贪婪最佳优先搜索
- f(n) = g(n) + h(n)，A*搜索
贪婪最佳优先搜索
定义：在每一步扩展时，都试图扩展离目标最近的结点。只用启发信息，f(n)=h(n)
评价
- 完备性：不一定能找到解，容易钻进离目标节点近的死胡同。
- 最优性：不一定是最优的，因为其贪婪地每次都寻找离目标结点最近的结点
- 时空复杂度：罗马尼亚例子中，直线距离启发式hSLD均很小，O(h)，只搜索一条路径；但最坏情况下，O(b^m)，m是搜索空间的最大深度
A*搜索：缩小总评估代价
定义：f(n) = g(n) + h(n)，每次都选择扩展f(n)最小的结点，在扩展时检测是否到达目标
f(n):经过结点n的最小代价解的估计值
算法与一致代价搜索类似，除了A*使用g+h而不是g
若启发式函数h(n)满足特定条件:A*搜索既是完备的也是最优的。
保证最优性的条件：
- 可采纳性：h(n)是一个可采纳启发式(admissible)，从不会高估到达目标的代价。例如直线距离启发式。
- 一致性（单调性）：若对于每一个结点n和通过任一行动a生成的n的每个后继结点n’，从结点n到达目标的代价估计满足：h(n) <= c(n, a, n1) + h(n1)，即满足三角不等式,则称h(n)是一致的(Consistent)
A*算法的最优性
A*算法有如下性质：
如果h(n)是可采纳的，那么A*的树搜索版本是最优的；
如果h(n)是一致的,那么么A*的图搜素版本是最优的；
存储受限的启发式搜索
将迭代加深的思想用在启发式算法中。迭代加深A*算法，IDA*算法。
原来的迭代加深算法截断值是搜索深度，现在改为f代价(g+h)。
递归最佳优先搜索（RBFS）
- 定义：f_limit记录次优路径的f值，如果当前后继节点的f值均大于f_limit就暂缓探索该节点，将其后继节点f的最小值代替该节点的f，转而探索次优节点，并重复以上步骤。
- 优点：仅用线性内存
- 缺点：内存使用过少，导致有很多节点被重复扩展，冗余路径也会带来复杂度的指数级增长
内存受限A*(MA*)简化内存受限A*(SMA*)
- 定义：探索最佳叶子节点直到内存耗尽，丢弃当前f最大节点，并添加新节点。
- 权衡时空复杂度成为算法探索的最终目的
启发式函数
对于八数码问题的启发式函数有两个常用的，两个启发式函数都没有超过实际的解代价
- h1=不在位置上的棋子数，最大为8
- h2=所有棋子到其目标位置的距离合（水平距离+垂直距离），最大值在20左右
启发式的精确度对性能的影响
启发式的设计对有效分支因子的值有影响。
有效分支因子b*： N+1 = 1 + b* + (b*)^2 + … + (b*)^d，所得b*越小算法性能越好；
一般来说启发式使用值更大的函数是更好的。
从松弛问题出发设计可采纳的启发式
松弛问题：减少了行动限制的问题，状态空间是原有状态空间的超图，多了很多边。
意义：一个松弛问题最优解的代价，是原问题的可采纳启发式。
生成：通过去掉经过形式化的原问题的一个或几个条件可以形成松弛问题。
最优松弛问题：可以比较生成的松弛问题的最优解的代价，选择最大的最优解代价的松弛问题。
除此之外还可以通过从子问题除法设计可采纳的启发式和从经验中得到启发式等。
总结
本章介绍了在确定性的、 可观察的、静态的和完全可知的环境下,Agent 可以用来选
择行动的方法。在这种情况下,Agent可以构造行动序列以达到目标;这个过程称为搜索。
-
在Agent可以开始搜索解之前, 必须对目标和良定义的问题加以形式化。
-
一个问题由五个部分组成:初始状态,行动集合,转移模型描述这些行动的结果,目标测试函数和路径代价函数。问题的环境用状态空间表示。状态空间中从初始状态到达目标状态的路径是一个解。
-
搜索算法将状态和行动视为原子:不考虑它们可能包含的内部结构。
-
一般的TREE-SEARCH算法会考虑所有的可能来寻找一个解;GRAPH-SEARCH算法则考虑避免冗余路径。
-
搜索算法的从完备性、最优性、时间复杂度和空间复杂度等方面来评价。复杂度依赖于状态空间中的分支因子b,和最浅的解的深度d。
-
无信息搜索方法只能访问问题的定义。 基本算法如下:
宽度优先搜索总是扩展搜索树中深度最浅的结点。算法是完备的,在单位代价的情况下是最优的,但是具有指数级别的空间复杂度。
一致代价搜索扩展的是当前路径代价g(n)最小的结点,对于一般性的步骤代价而言算法是最优的。
深度优先搜索扩展搜索树中深度最深的结点。它既不是完备的也不是最优的,但它具有线性的空间复杂度。
深度受限搜索在深度优先搜索上加了深度限制。
迭代加深搜索在不断增加的深度限制上调用深度受限搜索直到找到目标。它是完备的,在单位代价的情况下是最优的, 它的时间复杂度可与宽度优先搜索比较,具备线性的空间复杂度。
双向搜索可以在很大程度上降低时间复杂度,但是它并不是总是可行的并且可能需要太多的内存空间。 -
有信息搜索可能需要访问启发式函数h(n)来估算从n到目标的解代价。
- 一般的最佳优先搜索算法根据评估函数选择扩展结点。
- 贪婪最佳优先搜索扩展h(n)最小的结点。它不是最优的,但效率较高。
- A*搜索扩展 f(n)=g(n)+h(n)最小的结点。如果 h(n)是可采纳的(对于TREE-SEARCH)或是一致的(对于 GRAPH-SEARCH),A*算是完备的也是最优的。它的空间复杂度依然很高。
- RBFS(递归最佳优先) 和SMA*(简单内存受限A*)是鲁棒的、最优的搜索算法,它们使用有限的内存;只要时间充足,它们能求解 A*算法因为内存不足不能求解的问题。
- 启发式搜索算法的性能取决于启发式函数的质量。好的启发式有时可以通过松动间
题的定义来构造,将子问题的解代价记录在模式数据库中,或者通过对问题类的经验学习得到
9.以下结论成立：
a. When all step costs are equal, g(n) ∝ depth(n)（正比 ）, so uniform-cost search reproduces breadth-first search.
(depth(n):d(n)，即结点深度)
b. Breadth-first search is best-first search with f (n) = depth(n); depth-first search is best-first search with f (n) = −depth(n); uniform-cost search is best-first search with f (n) = g(n).
c. Uniform-cost search is A ∗ search with h(n) = 0.
点击拨打：