第5章：随机最短路径问题——静态

章节概述

图上的最短路径问题既是一个重要的应用领域（出现在交通、物流和通信中），同时也是许多其他场景中出现的一类基本问题。最熟悉的最短路径问题是图 5.1 所示的经典确定性问题，我们需要找到从节点 1 到节点 11 的最佳路径，其中每条弧的通行成本是提前已知的。

在本章中，我们将从一个行驶时间已知且固定的最短路径问题开始。确定性版本将使我们能够演示一种使用贝尔曼方程做决策的特定方式。然后我们以一种非常具体的方式引入不确定性，从而演示一种被称为近似动态规划的求解策略。

叙述

你正在尝试创建一个导航系统，用于引导无人驾驶车辆在拥堵的网络中前往目的地。我们假设系统能够访问历史和实时的链路成本数据，并据此估计通过某条链路的成本的均值和方差。我们可以将此视为一个最短路径问题，其中我们看到的是分布而非实际成本，如图 5.2 所示。

我们将首先假设必须基于这些分布来决定通过哪条链路。在我们从 $i$ 通行到 $j$ 之后，我们就会得到该分布的一个样本实现。我们希望选择一条能使期望成本最小化的路径。

问题建模

我们对三个建模问题的回答如下：

• 度量指标： 我们希望最小化从旅行者的起点到指定目的地的期望行驶时间。
• 决策： 当旅行者位于特定节点 $i$ 时，他们需要决定应通行到哪个下游节点 $j$，最终到达目的地。
• 不确定性： 我们既考虑没有不确定性的确定性问题，也考虑行驶时间不确定、但会在旅行者决定通行某条特定链路之前刚好被揭示的版本。

基本模型

我们假设正尝试从节点 $q$ 出发，遍历图 5.2 所示的网络，最终到达目的地 $r$。

符号说明

最短路径问题建立在一个基本的动态规划递归之上。设 $\Ncal$ 为网络中所有节点的集合（节点 $1, 2, \ldots, 11$），$\Ncal^+_i$ 为可以从节点 $i$ 直接到达的所有节点的集合，$\Ncal^-_j$ 为与节点 $j$ 相连的所有节点的集合，$\Lcal$ 为网络中所有链路 $(i,j)$ 的集合，$c_{ij}$ 为通行链路 $(i,j)$ 的成本，其中假设 $j$ 属于集合 $\Ncal^+_i$。

设 $v_i$ 为从节点 $i$ 到目的地节点 11 的最小成本。对于所有节点 $i\in\Ncal$，值 $v_i$ 应满足

我们可以通过将 $v_{11}$ 初始化为零、并将所有其他值设为某个较大的数来执行方程 $\eqref{eq:shortestpathbellman1}$。如果我们对每个节点 $i$ 进行循环，并反复利用方程 $\eqref{eq:shortestpathbellman1}$ 计算 $v_i$，那么这些值 $v_i$ 将收敛到最优值。这是最短路径算法的一种效率非常低的版本。

看待我们网络的另一种方式是，假设每个节点 $i$ 都是一个状态 $S$，并设 $V_t(S_t)$ 为在”时间” $t$ 处于状态 $S_t$ 的价值。在我们的最短路径问题中，我们将用 $t$ 来索引从节点 1 到达 $S_t$ 所代表的节点途中已经经过的链路数量。

从一个状态（节点）$S_t$ 出发，假设我们做出一个称为”$x$”的决策，即决定通行由状态 $S_t$ 所对应节点发出的某条链路。我们可以将这一组决策记为 $\Xcal_s$，表示在状态 $S_t = s$ 下可以使用的决策 $x$。

接下来，设 $C(s,x)$ 为处于状态 $s$ 并选择决策 $x$ 的成本，这对应于我们上面网络中的链路成本 $c_{ij}$。最后，我们将使用一个”状态转移函数”，记为 $S^M(s,x)$，它告诉我们如果处于状态 $s$ 并采取行动 $x\in\Xcal_s$，将转移到哪个状态。

利用这些符号，我们可以将方程 $\eqref{eq:shortestpathbellman1}$ 重写为

其中 $S_{t+1} = S^M(s,x)$。我们可以通过设置 $V_T(s) = 0$（对于足够大的 $T$ 值，即我们在路径中可能经过的最大链路数）来执行方程 $\eqref{eq:shortestpathbellman2}$。由于我们设置的 $T$ 可能过大，我们必须在 $\Xcal_s$ 的选择集合中加入在时间 $T$ 停留在目的地节点的能力。然后我们设置 $t=T-1$，并对所有状态 $s$ 运行 $\eqref{eq:shortestpathbellman2}$。我们不断重复此过程，直到到达 $t=0$。当我们以这种方式运行系统时，时间索引 $t$ 实际上是计数我们已经经过了多少条链路。

方程 $\eqref{eq:shortestpathbellman2}$ 是所谓贝尔曼方程的确定性版本。在本章的其余部分，我们将展示如何使用贝尔曼方程来处理最短路径问题中的不确定性。

状态变量

在这个基本问题中，状态 $S_t=N_t$ 是我们经过 $t$ 次链路通行后所处的节点。人们容易想直接说旅行者位于节点 $N_t$，但正如我们在扩展部分所看到的，微小的改变会产生更丰富的状态变量，因此认识到旅行者的真实状态非常重要。

决策变量

我们将决策建模为在处于节点 $i$ 的情况下我们所通行到的节点 $j$。有一个庞大的研究群体致力于研究符合这一类别的问题，其中决策被表示为一个动作 $a$，当我们处于状态 $s$ 时，$a$ 取集合 $\Acal_s$ 中某个离散值。

一种方便的表示决策的方式是定义

在我们撰写目标函数时，这一符号将证明是有用的。

外源信息

在通行链路 $(i,j)$ 之后，我们观测到 $\chat_{tij}$，即第 $t$ 次通行期间从 $i$ 到 $j$ 所经历的成本（这只有在通行该链路之后才能观测到）。目前，我们将假设新的观测值 $\chat_{tij}$ 被存储在一个非常大的数据库中。然后我们可以利用这些数据来估计通行链路 $(i,j)$ 的平均成本 $\cbar_{ij}$（我们对 $\cbar_{ij}$ 排除索引 $t$，因为无论何时通行链路 $(i,j)$，这都是平均成本）。

转移函数

对于我们的基本图问题，如果我们做出决策 $x_{tij}=1$，状态 $N_t = i$ 将演化为状态 $N_{t+1} = j$。

目标函数

我们可以使用以下符号对成本进行建模：$\chat_{tij}$ 是从节点 $i$ 到节点 $j$ 通行成本的随机变量；$\cbar_{ij}$ 是通过对我们过往旅行成本数据库取平均计算得到的 $\chat_{tij}$ 期望值的估计值；$\sigmabar_{ij}$ 是我们使用历史数据计算得到的 $\cbar_{ij}$ 标准差的估计值。

我们假设，在看到随机成本 $\chat_{tij}$ 的实际值之前，我们必须决定从节点 $i$ 通行出去时选择哪条链路。这意味着我们必须使用对 $\chat_{tij}$ 的最佳估计来做出决策，即 $\cbar_{ij}$。

我们可以使用以下方式来写出我们的目标函数

但这一表述需要我们知道实现值 $\chat_{tij}$。相反，我们将使用期望值，从而得到

该问题的最优解会将所有 $x_{tij} = 0$ 设置为某值，这意味着我们得不到一条路径。因此，我们必须引入如下形式的约束

方程 $\eqref{shortestpathobjective1}$–$\eqref{shortestpathobjective5}$ 表示一个线性规划，当以这种方式写出问题时，有强大的软件包可以用来求解。然而，也存在利用问题结构的专门算法（通常简称为”最短路径算法”），能够产生极为快速的解。

然而，这种方法并未提供处理不确定性的方法。下面，我们将描述如何使用我们设计策略的语言来求解随机最短路径问题，这将为处理不确定性提供基础。

不确定性建模

对于我们的基本模型，我们仅使用点估计值 $\cbar_{ij}$，我们假设这只是先前观测值的平均值，这些观测值例如是通过带 GPS 功能的智能手机收集的旅行成本估计值。当估计值基于实地观测时，该方法被称为数据驱动方法，这意味着我们不需要不确定性模型——我们只需要观测它。

例如，设 $\cbar_{ij}$ 为我们当前对链路 $(i,j)$ 平均旅行成本的估计值，并假设我们刚刚观测到成本为 $\chat_{tij}$。我们可能会使用以下方式更新估计值

其中 $\alpha$ 是一个小于 1 的平滑参数（有时也称为学习率或步长）。

如果我们以这种方式更新估计值，那么这意味着估计的旅行时间向量 $\cbar$ 是动态变化的，尽管我们可能每天只更新一次，而不是在一次出行中更新。在我们的建模框架中，成本估计值向量 $\cbar$ 被包含在初始状态 $S_0$ 中。如果我们设 $n$ 为出行日的索引，那么我们将用 $\cbar^n$ 表示使用前 $n$ 天数据得到的成本估计值，这些估计值随后被保存在为第 $n+1$ 天规划时所用的初始状态 $S^n_0$ 中。

策略设计

我们对这个确定性问题的”策略”是一个将”状态”（即我们所在的节点）映射到一个动作（我们移动经过的链路）的函数。我们可以通过优化方程 $\eqref{shortestpathobjective1}$–$\eqref{shortestpathobjective5}$ 所表示的线性规划来求解这个问题，从而得到所有链路 $(i,j)$ 的向量 $x^\ast _{ij}$。我们可以将其视为一个函数，即给定状态（节点 $i$），我们选择一个动作，即使得 $x_{ij} = 1$ 成立的链路 $(i,j)$。我们可以将这一策略写成一个函数 $X^\pi(S_t)$，如下所示

或者，我们也可以像最初求解确定性最短路径问题那样，使用方程 $\eqref{eq:shortestpathbellman1}$ 求解贝尔曼方程。这将给我们一个值 $v_i$，即从每个节点 $i$ 到目的地节点 $r$ 的最小旅行成本。一旦计算出这些值，我们就可以使用以下策略做出决策

这意味着我们的”随机”最短路径问题可以像求解确定性问题一样求解。下面在我们的扩展部分中，我们将展示，只需稍作调整，情况就会发生显著变化。

策略评估

对于这个问题，策略评估并非必需，因为该策略是最优的。尽管我们的链路成本是随机的，但只要我们在做出决策之前对实际成本一无所知，最优决策就等价于求解一个确定性最短路径问题。这将是本书中我们最后一次见到这样的问题。

在扩展部分，我们将以一种能够引入一种被称为近似动态规划（也称为强化学习）的强大算法策略的方式来引入不确定性。

扩展 - 自适应随机最短路径

我们现在要改变做决策时可以使用的信息。在我们最初的随机最短路径问题中，我们假设必须在看到某条链路上的实际出行成本之前就选择要经过的下一条链路。现在假设我们是在观察到链路成本之后才做出决策，这意味着我们是使用实际成本 $\chat_{ij}$ 而不是其期望值（或均值）$\cbar_{ij}$ 来做决策。图 5.3 展示了这一点，其中位于节点6的出行者能够看到从节点6出发的各条链路上的实际成本（而不仅仅是关于分布的知识）。

如果我们暂且假设有人能够告诉我们值 $v_j$，即从节点 $j$ 到我们目的地节点 $r$ 的最小出行成本，那么选择下一个下游节点的最优策略可以写成

这里的问题在于，我们无法像之前那样使用方程 $\eqref{eq:shortestpathbellman1}$ 来计算 $v_j$。事实上，转变为在做决策之前先看到成本，这需要对我们的基本模型进行根本性的改变。

在我们的确定性模型，或静态随机模型中，经过”$t$”次转移之后的状态变量 $S_t$ 是出行者所在的节点 $i$。这是我们在那个时间点所需的全部信息。

在我们新的随机模型中，仅仅捕捉出行者所在的节点已经不够了。回想一下，我们之前将状态变量引入为”在时间 $t$ 从历史信息中得到的、用以从时间 $t$ 起对系统进行建模所需的全部信息。”稍后在第 7 章中，我们将给出更精确的定义，但目前这个说法就足够我们使用了。

我们新的随机最短路径问题引入了做决策所需的新信息：即出行者所在节点出发的各链路成本。我们将发现，引入两类状态变量会很方便：$N_t$，即系统的物理状态，它通常直接由决策所控制；以及 $I_t$，即我们做决策所需的其他信息。在我们的网络问题中，物理状态就是出行者所在的节点，而”其他信息”变量 $I_t$ 则捕捉从该节点出发的各链路上的成本，我们将其写作

假设在时间 $t$ 有 $N_t = i$。我们将在链路成本的下标中加入时间 $t$，这意味着我们将用 $\chat_{tij}$ 替代 $\chat_{ij}$，以表示在时间 $t$ 从 $i$ 到 $j$ 的成本。于是我们可以写作

为了看清这对我们之前求解最短路径问题的方法产生了什么影响，我们不妨重新审视一下我们最初在方程 $\eqref{eq:shortestpathbellman2}$ 中引入的贝尔曼方程，它变成了

其中 $S_{t+1}$ 由 $S_{t+1} = (N_{t+1}, I_{t+1})$ 给出，$N_{t+1}$ 是由我们的决策 $x$ 所产生的节点，因此如果 $x_{ij} =1$，那么 $N_{t+1} = j$；而 $I_{t+1}$ 是从节点 $N_{t+1}$ 观察到的成本，它取决于决策 $x_t$。如果 $x_t$ 将我们送往节点 $j$，使得 $N_{t+1} = j$，那么 $I_{t+1} = (\chat_{t+1,jk_1}, \chat_{t+1,jk_2}, \chat_{t+1,jk_3})$（假设从节点 $j$ 出发有三条链路）。

假设 $N_t = i$。成本函数 $C(S_t,x)$ 由下式给出

请记住，$S_t$（其中 $N_t = i$）包含了从 $i$ 出发、通往 $(i,j)$ 的链路的成本 $\chat_{tij}$，因此这些是已知的（并包含在 $S_t$ 中）。

方程 $\eqref{eq:shortestpathbellman5}$ 写起来容易，但由于现在我们的状态变量是一个向量（这使得状态的数量呈爆炸式增长），求解起来却很困难。我们将首先描述两个计算方面的挑战。然后，我们将引入后决策状态的概念来解决其中一个挑战。最后，我们将简要介绍一类被称为近似动态规划（但通常也被称为强化学习）的方法，用以应对第二个挑战。

计算方面的挑战

我们首先来识别两个计算方面的挑战：

• 下游节点 $N_{t+1}$（由决策 $x$ 所决定）出发的链路成本 $I_{t+1}$ 是未知的。换句话说，$I_{t+1}$ 在时间 $t$ 是一个随机变量，这意味着我们甚至无法计算 $V_{t+1}(S_{t+1})$。我们通过取期望来解决这个问题，写作

期望算子 $\E$ 应被视为对出行者到达节点 $N_{t+1}$（这是通过决策 $x$ 所决定的，$x$ 决定了 $N_{t+1}$）后可能遇到的各种链路成本取平均。

更明确地写出来，假设 $x_t$ 将我们送往节点 $j$（这意味着 $x_{tij} = 1$），当我们到达时看到 $I_{t+1} = (\chat_{t+1,jk_1}, \chat_{t+1,jk_2}, \chat_{t+1,jk_3})$。我们是在时间 $t+1$ 到达节点 $j$ 时才得知这些成本的，但当我们在时间 $t$ 位于节点 $i$ 思考该怎么做时，这些成本仍是随机的。

• 状态空间——即使我们假设成本 $\chat_{t+1,j}$ 是离散的，状态空间也已经急剧增大。设想我们将成本离散化为20个取值的分箱。如果每个节点出发都有三条链路，那么我们的状态空间就从节点数量增长为原来的 $20 \times 20 \times 20 = 8,000$ 倍。

为了说明计算期望所面临的挑战，假设每个成本 $\chat_{t+1,jk}$ 可以取值 $c_1, c_2, \ldots, c_L$，对应概率为 $p_{jk}(c_{\ell})$。例如，$c_1$ 可能是1分钟，$c_2$ 可能是2分钟，依此类推。概率 $p_{jk}(c_{\ell})$ 就是 $\chat_{t+1,jk} = c_\ell$ 的概率。

现在假设决策 $x$ 将我们带到节点 $j$，之后我们面临在链路 $(j,k_1), (j,k_2)$ 或 $(j,k_3)$ 上出行的选择。我们将使用下式计算期望

坦率地说，方程 $\eqref{eq:shortestpathexpectation}$ 相当丑陋。那三重求和将很难计算。

使问题更加复杂的是状态空间的大小。要在方程 $\eqref{eq:shortestpathbellman6}$（或 $\eqref{eq:shortestpathbellman2}$）中使用贝尔曼方程，我们必须为每一个可能的状态 $S_t$ 计算 $V_t(S_t)$。当状态仅仅是一个节点时，这还不算太糟，即便节点数以千计（甚至数以万计）。然而，将信息变量 $I_t$ 加入状态之中，会使问题急剧变难。

为了说明这种增长有多快，设想每个成本变量 $\chat_{tij}$ 有20个可能的取值。这意味着 $I_t$ 有8,000种可能的取值。如果我们的网络有10,000个节点（即 $N_t$ 可以取10,000个值），那么 $S_t$ 现在可以取 $10,000 \times 8,000 = 80,000,000$ 个值。

这是我们首次窥见当状态变量变成一个向量时会发生什么。状态变量可能取值的数量呈指数级增长，这一过程通常被称为维度灾难。

使用后决策状态

对于这个问题，我们还没有山穷水尽。有一个技巧可以让我们克服这个特定问题中的维度灾难。方程 $\eqref{eq:shortestpathbellman6}$ 中贝尔曼方程的主要计算挑战在于期望算子，它无疑是求解序贯决策问题中最危险的一种记号。

在这种情形下（我们也将在其他情形中使用这些策略），我们将使用两种强有力的策略来克服这一问题。首先，我们引入后决策状态的概念，记作 $S^x_t$。后决策状态是我们做出决策之后、新信息到来之前系统所处的状态，这就是我们用 $t$ 对其进行索引的原因。

要理解决策前和决策后的状态，请回顾图 5.3。正如我们之前所见，我们的决策前状态（我们称之为”该状态”）$S_t$ 是

一旦我们做出了决策，我们仍处于节点6，但假设我们所做的决策是前往节点9。我们可以将物理后决策状态描述为 $R^x_t = 9$，我们也可以将其表述为”前往节点9”。然而，我们不再需要那些令人头疼的、由 $(\chat_{t+1,6,5}, \chat_{t+1,6,9}, \chat_{t+1,5,7}) = (12.7, 8.9, 13.5)$ 给出的关于节点6出发链路成本的观测值。这意味着我们的后决策状态是

利用后决策状态，我们将把贝尔曼方程分解为两个步骤。我们不再像在贝尔曼方程 $\eqref{eq:shortestpathbellman6}$ 中那样，从 $S_t$ 到 $S_{t+1}$ 再到 $S_{t+2}$，而是首先从决策前状态 $S_t$ 迈向决策后状态 $S^x_t$，为此我们将方程 $\eqref{eq:shortestpathbellman6}$ 改写为

其中 $V^x_t$ 是处于后决策状态 $S^x_t$ 的价值。请注意，我们不再有期望算子，因为按照构造，后决策状态包含了一个给定的决策 $x_t$（例如”前往节点9”），但不包含新的信息（那才是随机的部分）。请注意，在这种情形下，后决策状态 $S^x_t$ 仅仅由节点构成，这意味着它比 $S_t$ 简单得多。

但我们还没有完全脱离困境。我们仍然需要计算 $V^x_t(S^x_t)$，这需要用到

因此，我们仍然必须计算那个期望，而且它并没有变得更容易。假设我们的决策 $x$ 是前往节点 $j$（这意味着 $x_{ij}=1$），并令 $\chat_{t+1,j} = (\chat_{t+1,jk},~k\in\Ncal^+_j)$ 为从节点 $j$ 出发的链路成本集合。我们下一个决策前状态 $S_{t+1}$ 将是

现在假设我们有一种方法可以对 $\chat_{t+1,j}$ 的可能取值进行抽样。我们可以基于历史链路成本观测数据库来实现这一点，也可以基于过去的数据构建一个概率分布并从中抽样。假设我们要以迭代的方式来完成这项工作，令 $\chat^n_{t+1,ij}$ 为从 $i$ 到 $j$ 的链路成本的第 $n$ 个样本。我们可以利用这种基于抽样的策略，构造出期望值的一个估计，而非精确值。这将在下一节中完成。

近似动态规划

使用后决策状态变量解决了在寻找最优决策 $x_t$ 时计算期望的问题，但我们仍然要面对处理庞大状态空间的问题。为此，我们将转向一类被广泛称为近似动态规划的方法，在该方法中，我们用一个近似值来替代后决策值函数 $V^x_t(S^x_t)$。

我们将构造近似值 $\Vbar^x_t(j)$，用以表示处于节点 $j$ 的价值，其中

令 $\Vbar^{x,n}_t(j)$ 为在观察到 $n$ 个样本之后，我们对 $\E \lbrace V_{t+1}(S_{t+1})\vert S^x_t\rbrace $ 的近似值。构建这一近似值的一种方法是使用处于节点 $j$ 的价值的样本。设想我们将沿着网络向前推进，利用从先前迭代中得到的近似值 $\Vbar^{x,n-1}_t(S^x_t)$，以及抽样得到的成本 $\chat^n_{tij}$ 来做决策。我们可以利用下式获得处于状态 $S_t$ 的价值的一个抽样估计

然后我们将利用 $\vhat^{x,n}_t(i)$（即处于状态 $S_t$ 的价值，该状态既包含节点 $i$，也包含从节点 $i$ 出发的所有 $j$ 对应的成本 $\chat^n_{tij}$）来更新先前的后决策状态 $S^x_{t-1}$，为此我们使用

这里，$\alpha_n$ 被称为平滑因子或学习率，但出于技术上的原因，它也被称为”步长”。我们可以使用一个常数，比如 $\alpha_n = .1$ 或 $.05$，但一种常见的策略是使用一个递减的公式，如

其中 $\theta^\alpha$ 是一个可调参数。举例来说，如果我们设定 $\theta^\alpha = 1$，就会得到 $\alpha_n = 1/n$。在这种情况下，可以验证方程 $\eqref{eq:vhatsmoothing}$ 是对值 $\vhat^n_t(i)$ 进行平均。而在实践中，这个公式对于这个问题很可能效果不佳，因为步长下降得太快了。

我们暂停一下，来指出使用后决策状态 $S^x_t$ 的两个优势：

• 在优化选择某节点的输出链路时，我们不再需要处理期望算子（参见方程 $\eqref{eq:vhatsinglepass}$）。
• 对值函数 $\Vbar^{x,n}_t(S^x_t = i)$ 进行近似要简单得多，因为后决策状态 $S^x_t$ 现在只是一个标量，这比一个高维函数要容易估计得多。

方程$\eqref{eq:vhatsinglepass}$的一个挑战在于，我们需要为$\Vbar^{x,0}_t(i)$提供初始值。一个自然的选择是求解该问题的确定性版本，将成本$\chat_{tij}$设为其均值的估计值，然后获得从每个节点到目的地所产生成本的初始估计。

另一种方法是使用估计值$\Vbar^{x,n-1}(i)$来做决策，使用

决策$i^n_t = x^n_t(i)$根据抽样成本$\chat^n_{tij}$以及从节点$j$到目的节点$r$所需成本的估计值$\Vbar^{x,n-1}_t(j)$，给出节点$i$之后的下一个节点。当我们到达$r$时，我们得到了一条完整的路径，由如下节点组成

我们还得到了整条路径上的抽样成本$\chat^n_{t,i^n_t,i^n_{t+1}}$。假设该路径上有$T$条链路。然后我们从$\vhat^n_T(r) = 0$开始沿路径反向遍历，计算

然后我们将这些估计值用于方程$\eqref{eq:vhatsmoothing}$中的平滑处理过程。

这一过程是近似动态规划（也称为强化学习）的一种形式。更确切地说，它是一种前向近似动态规划，因为它是通过随时间向前推进而进行的。我们已经用方程$\eqref{eq:vhatsinglepass}$展示了一种纯前向遍历过程，它只需要对网络进行单次遍历；同时也用方程$\eqref{eq:vhatdoublepass}$展示了一种双向遍历过程，即先沿图向前遍历以模拟决策，再向后遍历以更新处于每个状态的价值。

这种方法对于复杂的决策前状态具有很强的鲁棒性。例如，我们不需要关心每个节点可能有多少条外出链路，因为我们利用了决策后状态变量相当简单这一事实（在本例中，它仅仅是我们所处的节点）。

我们学到了什么？

• 这是我们第一次（也是唯一一次）遇到能够为序贯决策问题找到最优策略的问题。尽管我们是在一个随机网络上进行优化，但旅行者在经过某条链路之前并不会提前获得关于该链路的任何信息，这意味着他必须基于期望成本做出选择。
• 由于基本模型可以简化为一个确定性最短路径问题，我们可以对其进行最优求解，这是能够最优求解基础问题的一个罕见例子（事实上，这是本书中唯一一次出现这种情况）。
• 接下来我们引入了这样一个维度：成本在旅行者经过该链路之前就已经揭示出来。我们对该问题进行了重新表述，说明状态变量现在变得更加复杂，包括旅行者所在的节点以及该节点外出链路的成本。这个问题不再能够用动态规划精确求解。
• 我们引入并描述了一种近似动态规划算法，该算法利用决策后状态变量的概念，消除了贝尔曼方程中所包含的期望运算，并将状态空间重新简化为仅包含节点集合。
• 这是一个VFA策略的例子。由于我们无法精确计算值函数，因此无法保证它是最优策略。

习题

复习题

1. 在最初的随机最短路径问题中，我们只有在经过某条链路之后才能观察到其实际成本，请解释为什么这个问题可以精确地作为一个简单的确定性最短路径问题来求解。
2. 对于我们在选择移动方向之前就能观察到某条链路实际成本的版本，请给出决策前状态变量和决策后状态变量。
3. 在方程$\eqref{eq:vhatsmoothing}$中，我们使用处于状态$S_t$的抽样值$\vhat^{x,n}_t(i)$来更新由$\Vbar^{x,n}_{t-1}(i)$给出的前一个决策后状态的估计值。请构造一个小的数值示例来说明这个方程。

问题求解题

1. 一位旅行者需要从节点1到节点11穿越图 5.4 所示的图。每条链路能够被通行都对应一个概率，如图中所示（这些概率是事先已知的）。当旅行者到达节点$i$时，她能够看到从节点$i$出发的哪些链路（如果有的话）是可以通行的。如果没有链路可以通行，则本次行程失败并终止。目标是选择一条路径，使这些概率的乘积最大化，但她只能在可用的链路上行进。
   1. 为该问题描述一个恰当的状态变量（附带符号说明）。
   2. 假设旅行者按照路径 1-2-6 到达节点6，并看到链路 6-9 和 6-10 可用（但 6-8 不可用）；她的（决策前）状态是什么？我需要的是你在(a)部分给出的状态变量的具体数值。
   3. 假设旅行者能够移动到节点9，并决定这样做。做出该决策后的决策后状态是什么？
   4. 写出贝尔曼方程，用下游决策前状态来刻画沿路径 1-2-6 到达后所处决策前状态的价值。请数值计算沿 1-2-6 到达并观察到 6-9 和 6-10 可用（但 6-8 不可用）后所处状态的价值。

   

2. （本题适用于上文的自适应随机最短路径扩展。）请通过回答以下问题，写出为决策后状态拟合值函数近似所涉及的步骤：
   1. 写出决策前状态和决策后状态。如果网络有$N$个节点，且每条链路上的成本被离散化为20个取值（假设任一节点最多有$L$条外出链路），那么决策前和决策后状态空间的大小分别是多少？
   2. 给出计算$\vhat^n_t(i)$的方程。这是处于决策前状态的估计值，还是处于决策后状态的估计值？请解释。
   3. “时间”索引$t$指的是什么？
   4. 给出更新处于决策后状态价值的更新方程。
   5. 为什么我们需要处于决策后状态的价值，而不是决策前状态的价值？
3. 图 5.5 展示了一位Uber司机可能面临的选择。在节点1处，她可以在行程(2-4)和(3-5)之间进行选择。假设行程至少需要15分钟，并且行程预期需在10分钟内得到服务，否则将会流失。这意味着从节点6、7、8出发的行程只有在(2-4)和(3-5)这两个行程本应完成之后才会变得已知。

   

   假设我们的司机先选择了(3-5)，然后选择了(7-10)。完成(7-10)之后，她必须在返回家之前先前往一个充电站为电池充电（假设她会选择成本最低的充电站）。 每次移动旁边标注了她能获得多少收入（用$c_{ij}$表示），当为顾客提供服务时该值为正，当空车移动时该值为负。当然，她的目标是在整个班次中实现利润最大化。 我们司机的状态就是她所在的位置（节点编号）或她正前往的节点编号，以及在该时刻已知的、与她的决策相关的任何其他可用信息。
   1. 假设她最初位于节点1，她的（决策前）状态是什么？在决定接受行程(3-5)之后，她的决策后状态是什么？
   2. 设$s_1$为完成行程(3-5)之后的（决策前）状态。设$\vhat_1(s_1)$为处于状态$s_1$的价值。$\vhat_1(s_1)$是多少？
   3. 设$s^x_0$为$s_1$之前的前一个决策后状态，设$\vhat^x_0(s^x_0)$为处于$s^x_0$的价值。$\vhat^x_0(s^x_0)$是多少？
   4. 就计算策略而言，使用决策后状态相较于决策前状态在计算上有什么优势？请用一句话回答。

编程题

以下习题使用位于tinyurl.com/sdagithub上的Python模块StochasticShortestPath_Static。

1. （本题适用于上文的自适应随机最短路径扩展。）目前，该算法在求解扩展中的修改后问题时，使用固定的平滑因子来估计值函数近似。请实现如下的递减步长： $$ \alpha_n = \frac{\theta^{step}}{\theta^{step} + n-1}. $$ 将该Python模块针对$\theta^{step} = (1, 5, 10, 20, 50)$运行100次迭代，并从收敛速度和最终解两方面比较其表现。你会选择哪一种？