有信息搜索

• 13 min read • 2429 words
Tags: Search
Categories: Introduction to Artificial Intelligence

有信息搜索

1. 有信息搜索概念

在无信息搜索中,我们会从起始点开始、展开当前边界的所有可能后继状态。但是这样的搜索效率很低,会导致进行很多没必要的搜索。如果我们了解了当前环境的信息、对当前的空间的搜索方向有一定概念,就可以显著提高性能、快速到达目标。

2. 启发式搜索

启发式函数是实现到目标状态距离的核心驱动力——它们是接收一个状态作为输入并输出相应估计值的函数

  • 我们通常希望启发式函数是到目标剩余距离的下界,因此启发式函数通常是松弛问题(原问题的某些约束已被移除)的解。

松弛问题(Relaxed Problem):是指通过移除或放宽原问题中的某些约束,从而得到的一个更简单、更容易解决的新问题,然后尝试将这个新问题的解带入原问题。

有了启发式函数,我们很容易在我们的Agent中实现逻辑,使其在决定执行哪个动作时“偏好”扩展那些估计离目标状态更近的状态。

3. 贪婪搜索

贪婪搜索总是选择具有最低启发式值的边界节点进行扩展,这对应于它认为最接近目标的状态。

贪婪搜索的操作与UCS相同,使用优先队列作为边界表示。不同之处在于,贪婪搜索使用启发式值的形式估计的前向成本来分配优先级,而不是使用计算出的后向成本(到状态路径中边权重的总和)。

贪婪搜索不保证在存在目标状态时能找到它,也不是最优的,特别是在选择了非常糟糕的启发式函数的情况下。它通常在不同场景下的行为相当不可预测,可能从直接走向目标状态到像一个被错误引导的DFS一样探索所有错误的区域。

4. A*搜索

A*搜索总是选择具有最低估计总成本的边界节点进行扩展,其中总成本是从起始节点到目标节点的整个成本。

就像贪婪搜索和UCS一样,A* 搜索也使用优先队列来表示其边界。同样,唯一的区别是优先级选择的方法。A*将UCS使用的总后向成本(到状态路径中边权重的总和)与贪婪搜索使用的估计前向成本(启发式值)相加作为总成本

给定一个适当的启发式函数,A*搜索既是完备的也是最优的。之后我们会证明这个结论。

5. 启发函数的可采纳性

a.a.相关概念

我们首先用以下定义重新表述用于确定UCS、贪婪搜索和A*中优先队列排序的方法:

  • g(n)g(n) - UCS计算的总后向成本函数。
  • h(n)h(n) - 贪婪搜索使用的启发式值函数,或估计的前向成本。
  • f(n)f(n) - A*搜索使用的表示估计总成本的函数。f(n)=g(n)+h(n)f(n) = g(n) + h(n)

可采纳性约束规定,一个可采纳的启发式函数估计的值既不是负数,也不应该高于实际值。定义h(n)h^(n)为从给定节点n到达目标状态的真实最优前向成本,我们可以将可采纳性约束数学地表述如下:

n,0h(n)h(n)\forall n, 0 \le h(n) \le h^(n)   

基于A*的启发式函数,我们提出如下的定理:

theorem:theorem: 对于给定的搜索问题,如果启发式函数hh满足可采纳性约束,那么在该搜索问题上使用A*树搜索将产生最优解。

proof:proof: 假设在给定搜索问题的搜索树中存在两个可达目标状态:一个最优目标AA和一个次优目标BB

由于AA是最优目标,我们有:

g(A)<g(B)g(A) \lt g(B)

对于目标节点,其真实前向成本为0,有:

h(A)=h(B)f(A)<f(B)h(A)=h(B) \Rightarrow f(A) \lt f(B)

我们取AA的一个祖先节点nn,通过引入这个祖先节点来证明在边界拓展过程中,最优路径是AA而不是BB

由于nnAA的祖先节点,并且hh是可采纳的,从起点到nn的总代价与nnAA的估计代价不会超过从起点到AA的真实代价:

f(n)=g(n)+h(n)g(a)+h(a)f(n)f(A)f(n) = g(n) + h(n) \leq g(a) + h(a) \Rightarrow f(n) \leq f(A)

从而有:

f(n)f(B)f(n) \le f(B)

所以BB不可能比AA或者其祖先更早拓展,我们的启发式函数不会优先搜索次优解

引入节点nn是为了找一个节点来比较AABB谁更值得拓展,因为AABB并不在同一边界,无法直接比较,所以我们引入了一个中间节点来比较。

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)

注意,如果选择的启发式函数不满足可采纳性约束的话,我们就需要运行重复访问某一状态、并且采用比较真实代价的方式来判断是否需要更新节点代价,此时启发式函数只起到引导搜索方向的作用。