有信息搜索
有信息搜索
1. 有信息搜索概念
在无信息搜索中,我们会从起始点开始、展开当前边界的所有可能后继状态。但是这样的搜索效率很低,会导致进行很多没必要的搜索。如果我们了解了当前环境的信息、对当前的空间的搜索方向有一定概念,就可以显著提高性能、快速到达目标。
2. 启发式搜索
启发式函数是实现到目标状态距离的核心驱动力——它们是接收一个状态作为输入并输出相应估计值的函数。
- 我们通常希望启发式函数是到目标剩余距离的下界,因此启发式函数通常是松弛问题(原问题的某些约束已被移除)的解。
松弛问题(Relaxed Problem):是指通过移除或放宽原问题中的某些约束,从而得到的一个更简单、更容易解决的新问题,然后尝试将这个新问题的解带入原问题。
有了启发式函数,我们很容易在我们的Agent中实现逻辑,使其在决定执行哪个动作时“偏好”扩展那些估计离目标状态更近的状态。
3. 贪婪搜索
贪婪搜索总是选择具有最低启发式值的边界节点进行扩展,这对应于它认为最接近目标的状态。
贪婪搜索的操作与UCS相同,使用优先队列作为边界表示。不同之处在于,贪婪搜索使用启发式值的形式估计的前向成本来分配优先级,而不是使用计算出的后向成本(到状态路径中边权重的总和)。
贪婪搜索不保证在存在目标状态时能找到它,也不是最优的,特别是在选择了非常糟糕的启发式函数的情况下。它通常在不同场景下的行为相当不可预测,可能从直接走向目标状态到像一个被错误引导的DFS一样探索所有错误的区域。
4. A*搜索
A*搜索总是选择具有最低估计总成本的边界节点进行扩展,其中总成本是从起始节点到目标节点的整个成本。
就像贪婪搜索和UCS一样,A* 搜索也使用优先队列来表示其边界。同样,唯一的区别是优先级选择的方法。A*将UCS使用的总后向成本(到状态路径中边权重的总和)与贪婪搜索使用的估计前向成本(启发式值)相加作为总成本。
给定一个适当的启发式函数,A*搜索既是完备的也是最优的。之后我们会证明这个结论。
5. 启发函数的可采纳性
相关概念
我们首先用以下定义重新表述用于确定UCS、贪婪搜索和A*中优先队列排序的方法:
- - UCS计算的总后向成本函数。
- - 贪婪搜索使用的启发式值函数,或估计的前向成本。
- - A*搜索使用的表示估计总成本的函数。。
可采纳性约束规定,一个可采纳的启发式函数估计的值既不是负数,也不应该高于实际值。定义为从给定节点n到达目标状态的真实最优前向成本,我们可以将可采纳性约束数学地表述如下:
基于A*的启发式函数,我们提出如下的定理:
对于给定的搜索问题,如果启发式函数满足可采纳性约束,那么在该搜索问题上使用A*树搜索将产生最优解。
假设在给定搜索问题的搜索树中存在两个可达目标状态:一个最优目标和一个次优目标。
由于是最优目标,我们有:
对于目标节点,其真实前向成本为0,有:
我们取的一个祖先节点,通过引入这个祖先节点来证明在边界拓展过程中,最优路径是而不是。
由于是的祖先节点,并且是可采纳的,从起点到的总代价与到的估计代价不会超过从起点到的真实代价:
从而有:
所以不可能比或者其祖先更早拓展,我们的启发式函数不会优先搜索次优解
引入节点是为了找一个节点来比较和谁更值得拓展,因为和并不在同一边界,无法直接比较,所以我们引入了一个中间节点来比较。
6. 简单实现
我们在原有的Problem
抽象类中添加h
方法作为启发式函数:
class Problem(ABC):
...
def h(self, state):
return 0 # the default is plain heuristics
然后将不同策略的优先级函数作为参数传入:
class PriorityQueueFrontier(Frontier):
def __init__(self, priority_function):
self.heap = []
self.priority_function = priority_function
self.counter = 0
然后实现对应的优先级函数即可:
def ucs_priority(node, problem):
"""UCS: g(n)"""
return node.path_cost
def greedy_priority(node, problem):
"""greedy search: h(n)"""
return problem.h(node.state)
def astar_priority(node, problem):
"""A*: f(n) = g(n) + h(n)"""
return node.path_cost + problem.h(node.state)
注意,如果选择的启发式函数不满足可采纳性约束的话,我们就需要运行重复访问某一状态、并且采用比较真实代价的方式来判断是否需要更新节点代价,此时启发式函数只起到引导搜索方向的作用。