一般动态规划问题的表述

这不是我描述任意优化问题(或动态编程算法)的方法。特别是β因子 ^T 看起来像是一个程序员通常不会想要的电子工程黑客。更微妙的是,它似乎并不总是显而易见的功能 f 是针对给定问题的。

但是是的,把β设为1和任意的目标函数 可以 以这种方式制定。一般来说,目标函数可以是初始状态的任何函数以及所采取的所有操作;给定这样一个函数,很容易定义一个函数。 f 插入那个公式。

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

计算机科学 动态规划 表示在递归展开中多次出现相同的子问题时,按照递归地将其拆分为子问题的方式构建任何算法。一个简单的书籍例子,斐波那契数可以使用动态编程计算:

根据一般的递归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)] = ... 

在这里我们已经看到斐波那契(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)时间(假设标准o(log n))计算关联数组“store”的第n个fibonacci数。

因此,从计算机科学的角度来看,你提供的链接是同一想法的运筹学/优化问题版本(将问题划分为子问题),但是这个想法在实践中被抽象为通用计算机科学领域的递归+记忆化模式。我希望这有助于清除一些云。

乡亲们,

有一个新的(ish)网站专注于运筹学问题 here 但是那里的交通量很小,可能不会很快给你一个好的答案。

肥皂盒时间:

对于那些想讨论什么适合堆栈溢出的人来说,让我们注意一个算法是一个算法,不管谁声称它是他们领域的一部分。单纯形法、Djikstra方法、分枝定界法、拉格朗日松弛法都是求解某些类型问题的算法或方法。其中许多都在这两个领域中教授和应用,因此OR和CS之间的边界在这一领域非常模糊。

例如,麻省理工学院的算法专业本科生课程包括以下所有内容:随机竞争算法、动态规划、贪婪算法、最小生成树、最短路径、Dijkstra算法、Bellman Ford、线性规划、深度优先搜索、拓扑排序和所有对sho其他主题中的测试路径。在这种情况下,我会服从麻省理工的。

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