一般动态规划问题的表述

Question

我想知道一般动态规划问题的目标函数是否总是可以像维基百科上的动态规划中那样被表述为每个阶段的动作和状态项之和？或者这只是一个特例，一般公式是什么？

---

编辑：

所谓“动态规划问题”，是指可以通过动态规划技术解决的问题。这类问题具有最优问题和最优结构的特性。

但对于我来说，有时很难识别此类问题，可能是因为我还没有习惯那种语言描述。当我看到Bellman方程的WIKI页面时，我确实觉得成本函数的数学表示会在某种程度上有所帮助。我怀疑总成本/收益函数始终可以表示为所有阶段的成本/收益的累积？而且这种累积可以是加法、乘法或其他形式？

当我发布我的问题时，我意识到更适合在一些更注重数学优化的地方讨论动态规划。但Stackoverflow.com上有很多关于计算机算法的讨论。因此，在这里提问并不不妥。

- Tim

---

@John：计算机科学和编程非常相关。问题很模糊，即使你知道这些术语的含义。 - Aryabhatta

@Moron：他在问链接中给出的动态规划公式是特殊情况还是所有动态规划解决方案的一般形式。 - BlueRaja - Danny Pflughoeft

@John：排序算法、贪心算法、动态规划算法都属于计算机科学范畴。我想任何标记为算法的问题现在都必须被关闭。 - Aryabhatta

@Thomas：与其无意义地纠缠于细节，不如推断出明显的预期含义：“那些可以通过动态规划解决的问题”。 - j_random_hacker

@John。你只是在挑出数字。有多少人能回答关于Algol的问题？或者Fortran III，或其他一些小众编程语言的问题？楼主从一个角度看待动态规划，并不意味着动态规划与编程无关。事实上，动态规划涉及的内容远不止“数学优化”，这个问题及其答案可能对其他程序员也有相关性。 - Aryabhatta

Answer 1

这并不是我想象中的任意优化问题（或动态规划算法）的描述方式。特别地，因子β^t看起来像是电气工程的技巧，程序员通常不需要这样做。更微妙的是，对于一个给定的问题，函数F可能并不总是显而易见的。

但是，将β设置为1，任何任意的目标函数都可以用这种方式来表达。通常，目标函数可以是初始状态和所有行动的任何函数；鉴于这样的函数，很容易定义一个函数F来插入到那个公式中。

我想这是否有用取决于具体问题。

- Jason Orendorff

---

谢谢，Jason！我就像你设置的一样忽略了βt。我将F解释为从一个阶段到下一个阶段的增益/成本。回想起来，我认为整体的成本/收益函数总是可以表示为所有阶段的成本/收益的累积？而这个累积可以是加法、乘法或其他什么形式？ - Tim

是的，你可以将目标函数分解成每个阶段的部分的许多方式。你引用的公式将其分解为加性部分；这样做的优点是它可以描述每个可能的目标函数。相反，你也可以将目标函数分解为每个阶段的因子，但并不是每个目标函数都可以这样做：如果任何一次移动将目标置于0，下一次移动将其置于1，则该第二次移动没有可能的F值。 - Jason Orendorff

Answer 2

在计算机科学中，动态规划是指将任何算法递归地分解为子问题，并在这个递归扩展中多次出现相同的子问题。一个简单的书例是，斐波那契数列可以使用动态规划来计算：

从通用递推式F(n) = F(n-1) + F(n-2)可以实现以下算法：

int fibonacci(n):
  if (n < 2): return 1
  else: return fibonacci(n-1) + fibonacci(n-2)

当然，这种方法并不高效，因为它会创建大量的递归调用，例如：

F(8) = F(7) + F(6) = [F(6) + F(5)] + [F(5) + F(4)] = ... 

因此，我们已经看到这个实现中 fibonacci(5) 被计算了两次。现在采用“动态规划”范式来“记忆化”或“缓存”结果，如下所示：

integer_map store;
int memofibo(n):
  if (n < 2) : return 1
  else if (store.find_key(n)): return store.find_value(n)
  else:
    int f = memofibo(n-1) + memofibo(n-2)
    store.set(n, f)
    return f

这个实现确保对于每个参数值n，递归步骤最多执行一次，因此它可以在O(n log n)的时间内计算第n个斐波那契数（假设具有标准的O(log n)关联数组“store”实现）。

从计算机科学的角度来看，您提供的链接是相同思想的运筹学/优化问题版本，但这个想法已经在通用计算机科学领域中抽象成为递归+记忆化模式。希望这能帮助消除一些疑惑。

- Antti Huima

---

谢谢，安蒂！我很感激你对实现细节的回复。是的，我同意这个问题更多地涉及运筹学和数学背景。 - Tim

Answer 3

各位，

这里有一个关注运筹学问题的新网站 here 但是由于流量较少，您可能无法很快得到好的答案。

发表个人看法：

对于那些关心适合在堆栈溢出上讨论的内容的人，请注意，算法是算法，不管谁声称它是其领域的一部分。 单纯形法，Djikstra's方法，分支限界法，拉格朗日松弛法，都是解决某些类型问题的算法或方法。 许多这些方法在两个领域中都被教授和应用，因此OR和CS之间的边界在这个领域中非常模糊。

例如（而且这是一个非常强有力的例子），MIT的本科课程包括以下所有内容 - 随机竞争算法，动态规划，贪婪算法，最小生成树，最短路径，Dijkstra算法，Bellman-Ford，线性规划，深度优先搜索，拓扑排序和所有对最短路径等其他主题。 在这种情况下，我会听从MIT的意见。

我喜欢 Stack Overflow，因为许多程序员在遇到优化问题时会意识到它，但通常他们只需要一点帮助来决定如何表达问题，甚至是问题的名称。

- Grembo