定义明确的问题及解

时间：2022-02-11 理论教育版权反馈

【摘要】：（如果我们把每条道路视为代表着两个驾驶行动，每个行动各走一个方向，图 3.2 所示的罗马尼亚地图就可以被解释为一个状态空间图。在罗马尼亚问题中，目标状态集是一个单元素集合{In}。对于试图到达Bucharest的智能体，时间是一个基本要素，所以它的路径耗散可以是用公里数表示的路径长度。如图 3.2 所示，在罗马尼亚问题中的单步耗散用单步路程表示。上述元素定义了一个问题，可以把它们集合在一起成为单一的数据结构，作为问题求解算法的输入。

3.1.1 定义明确的问题及解

一个问题可以形式化地定义为四个组成部分：

• 智能体起始时的初始状态。例如，在罗马尼亚问题中我们的智能体的初始状态可以描述为In(Arad)。

• 对智能体可采纳的可能行动的描述。最常见的形式化[3]是使用一个后继函数。给定一个特殊状态 x，SUCCESSOR-FN(x)返回一个由有序对<action, successor>（<行动，后继>）组成的集合，其中每个行动都是状态x下的合法行动之一，每个后继都是应用行动后从状态x能达到的状态。例如，从状态In(Arad)开始，罗马尼亚问题的后继函数将返回集合：

{<Go(Sibiu), In(Sibiu)>, <Go(Timisoara), In(Timisoara)> , <Go(Zerind), In(Zerind)>}

总之，初始状态和它的后继函数隐含地定义了问题的状态空间——即从初始状态可以达到的所有状态的集合。状态空间形成一个图，其中节点是状态，节点之间的弧就是行动。（如果我们把每条道路视为代表着两个驾驶行动，每个行动各走一个方向，图 3.2 所示的罗马尼亚地图就可以被解释为一个状态空间图。）状态空间中的一条路径就是通过行动序列连接起来的一个状态序列。

• 目标测试，用来确定给定的状态是不是目标状态。有时候可能的目标状态集是非常明确的，测试只需要简单地检查给定的状态是否为目标状态集合中的状态之一。在罗马尼亚问题中，目标状态集是一个单元素集合{In(Bucharest)}。而有时候目标状态是由抽象性质来指定的，而不是一个显式的可枚举目标集。例如，在国际象棋中，目标是要达到一个被称为“将死”的状态，即对方的国王在己方的攻击下已经无路可逃。

• 路径耗散函数为每条路径分配一个数值化的耗散值。问题求解智能体选择能反映它自己的性能度量的耗散函数。对于试图到达Bucharest的智能体，时间是一个基本要素，所以它的路径耗散可以是用公里数表示的路径长度。在本章中，我们假设一条路径的耗散值可以被描述为沿该路径的每个动作的耗散值总和。采用行动a从状态x走到状态y所需要的单步耗散用c(x, a, y)表示。如图 3.2 所示，在罗马尼亚问题中的单步耗散用单步路程表示。我们假设单步耗散值是非负的[4]。

上述元素定义了一个问题，可以把它们集合在一起成为单一的数据结构，作为问题求解算法的输入。问题的解就是从初始状态到目标状态的路径。解的质量由路径耗散函数度量，而最优解是所有的解里路径耗散值最小的解。