动态规划：实例、变体与简化方法
1. 离散确定性优化
离散优化问题可通过将每个可行解分解为一系列决策或控制，转化为动态规划（DP）问题。不过，这种转化常因状态数量呈指数级增长，导致DP计算难以处理。但它也为近似DP方法的应用提供了可能，如滚动算法等。
旅行商问题
旅行商问题是一个经典的调度模型。给定N个城市以及每对城市之间的旅行时间，目标是找到一条最短的旅行路线，使旅行商恰好访问每个城市一次并返回起点。
为将该问题转化为DP问题，可构建一个图，其节点为k个不同城市的序列，对应第k阶段的状态。初始状态x0是某个选定的起始城市。一个k - 城市节点通过添加一个新城市转变为(k + 1) - 城市节点，成本为这(k + 1)个城市中最后两个城市之间的旅行时间。每个N - 城市序列都与一个人工终端节点t相连，连接成本为序列中最后一个城市到起始城市的旅行时间。
通过DP算法可得到从每个节点到终端状态的最优成本。然而，节点数量随城市数量N呈指数级增长，这使得对于大规模的旅行商问题，DP求解变得不可行。因此，通常会采用基于DP的近似方法来处理此类问题。
对于一般的离散优化问题：
[
\begin{cases}
\min G(u) \
\text{s.t. } u \in U
\end{cases}
]
其中U是有限的可行解集合，G(u)是成本函数。假设每个解u有N个分量，即(u = (u_1, \ldots, u_N))。可将该问题视为一个顺序决策问题，依次选择分量(u_1, \ldots, u_N)。由解的前k个分量组成的k - 元组((u_1, \ldots
