3

我想知道一般动态规划问题的目标函数是否总是可以像wiki 上的动态规划那样制定，其中目标函数是每个阶段的动作和状态项的总和？或者这只是一个特例，一般的表述是什么？

编辑：

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

但至少对我来说，有时很难识别出这样的问题，也许是因为我还没有习惯这种口头描述。当我遇到贝尔曼方程的 WIKI 页面时，我确实觉得成本函数的数学公式会有所帮助。我怀疑整体成本/收益函数总是可以表示为所有阶段的成本/收益的累积？累积可以是加法或乘法还是其他？

当我发布我的问题时，我确实意识到在更面向数学优化的某个地方讨论动态编程更合适。但是在 Stackoverflow.com 上有很多关于计算机算法的讨论。所以我也不觉得在这里问我的问题不合适。

4

3 回答 3

2

这不是我描述任意优化问题（或动态规划算法）的方式。特别是，因子 β t看起来像是程序员通常不想要的电气工程技巧。更微妙的是，对于给定问题，函数F的含义似乎并不总是很明显。

但是，是的，将 β 设置为 1，任何任意目标函数都可以这样表示。通常，目标函数可以是初始状态和所采取的所有动作的任何函数；给定这样一个函数，很容易定义一个函数F来插入该公式。

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

于 2010-02-13T17:21:44.613 回答
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 '。

所以从计算机科学的角度来看，您提供的链接是相同思想的运筹学/优化问题版本（将问题划分为子问题），但该思想在实践中已抽象为通用计算机领域中的这种递归+记忆模式科学。我希望这有助于清除一些乌云。

于 2010-02-13T18:23:35.993 回答
1

伙计们，

这里有一个专注于运筹学问题的新（ish）网站，但那里的低流量可能无法很快为您提供一个好的答案。

肥皂盒时间：

对于那些关心什么是适合堆栈溢出的争论的人，让我们注意算法是一种算法，无论谁声称它是他们领域的一部分。单纯形法、吉克斯特拉法、分支定界法、拉格朗日松弛法，都是解决某些类型问题的算法或方法。其中许多都是在这两个领域中教授和应用的，因此 OR 和 CS 之间的边界在该领域非常模糊。

例如（并且是一个非常强大的例子）麻省理工学院的算法本科课程包括以下所有内容 - 随机竞争算法、动态规划、贪心算法、最小生成树、最短路径、Dijkstra 算法、Bellman-Ford、线性规划、深度优先搜索、拓扑排序和全对最短路径等主题。在这种情况下，我将遵从麻省理工学院。

我喜欢堆栈溢出，因为许多程序员在遇到优化问题时会认出它，但通常他们只需要一点帮助来决定如何制定问题，甚至问题的名称是什么。

于 2010-02-17T20:18:20.733 回答