dynamic programming 啥意思

小时候学习编程，学到动态规划，就是dynamc programming, 虽然也能学到想法然后自己写程序 但是从来的不明白 这个东西 “动态”在哪里 “规划”在哪里。这个名字就是莫名其妙的。直到长大后进入英语语境以及数理知识接触的比较多了 突然有一天才恍然大悟。当然这其实也是中文翻译的问题。programming 当然指的是编程，而 dynamic 在数理里面指的是 系统状态 （一般基于时间）的动态的变化。比如数学里的动力系统 (dynamical system) 和 物理里的动力学 （dynamics). 很简单的一个 dynamics  的例子就是 下一时刻的速度是这一时刻速度加加速度的累积  v(t+1) = v(t） + a(t) * dt。这个方程描述的就是系统速度的dynamics。这类型的方程把t 离散化后就是 n+1的状态可以由n的状态推演表达出来。很多编程题目的解答 归结于这样一个由n-1的结果推演n的结果的过程 f(n) = F(f(n-1)) 这就类似于一种离散的dynamic。于是基于这种推演公式的解答就叫做 dynamic programming.

哈哈哈 可能这对好多人来说都是废话吧 其实我就是新人想获得点积分 ：）不知道有没有人给我加加分 ：）谢谢啦

这里的programming其实就是规划的意思，不是什么编程。有个subfield就叫做mathmatical programming（领域内的一本顶刊也是这个名字）。再不济，linear programming（线性规划）很多人也应该有所耳闻吧。

Richard Bellman当时取"dynamic programming"这个名字的时候，在给美帝军方打工。这个名字也包含了一些政治因素在里面，他选择了这个名字的一大原因就是应付他（Bellman自己认为的）nt老板。我下面放出原话。

An interesting question is, ‘Where did the name, dynamic programming, come from?’The 1950s were not good years for mathematical research. We had a very interesting gentleman in Washington named Wilson. He was Secretary of Defense, and he actually had a pathological fear and hatred of the word, research. I'm not using the term lightly; I’m using it precisely. His face would suffuse, he would turn red, and he would get violent if people used the term, research, in his presence. You can imagine how he felt, then, about the term, mathematical. The RAND Corporation was employed by the Air Force, and the Air Force had Wilson as its boss, essentially. Hence, I felt I had to do something to shield Wilson and the Air Force from the fact that I was really doing mathematics inside the RAND Corporation. What title, what name, could I choose? In the first place I was interested in planning, in decision making, in thinking. But planning, is not a good word for various reasons. I decided therefore to use the word,‘programming.’ I wanted to get across the idea that this was dynamic, this was multistage, this was time-varying—I thought, let’s kill two birds with one stone. Let’s take a word that has an absolutely precise meaning, namely dynamic, in the classical physical sense. It also has a very interesting property as an adjective, and that is it’s impossible to use the word, dynamic, in a pejorative sense. Try thinking of some combination that will possibly give it a pejorative meaning. It’s impossible. Thus, I thought dynamic programming was a good name. It was something not even a Congressman could object to. So I used it as an umbrella for my activities.

我觉得动态规划就是家里老人们口中的“走一步看一步”哈哈

这个term提出来的时候, Richard Bellman要骗项目/骗经费，所以起了一个看上去很运筹很重要的名字。。。明白了吗?

给加分了！作为dynamics simulation的phd，我一开始也以为dp和我专业有什么关系，然后发现咋什么关系都没有。

NellyCat 发表于 2020-11-20 16:56
给加分了！作为dynamics simulation的phd，我一开始也以为dp和我专业有什么关系，然后发现咋什么关系都没有 ...

：）） 多谢 是的coding上其实没有半毛钱关系 但是code之前最重要的一步就是得到递推公式

nullspace 发表于 2020-11-20 02:38:05
这里的programming其实就是规划的意思，不是什么编程。有个subfield就叫做mathmatical programming（领域内的一本顶刊也是这个名字）。再不济，linear progr

此楼是正解。当时教我们算法的教授也讲过这个故事

programming指的不是编程呀，指的是general 解决问题的一种方法。和linear programming的programming是一个意思

哈哈 没想到这里边还有故事 楼上几位说的对 programming应该不是编程的意思 不过我对这个词没有太多疑惑 主要过去一直不理解的是 dynamic 在这里的意义。
另外programming翻译成“规划”好像不大贴切，反正小时候的我是无法理解 “规划”跟写程序有什么关系。

这儿的dynamic也有相对static的意思。做multiperiod/sequential的优化问题的时候可以从t=0到t=T用lagrange/kkt一次性优化整个问题，这种就是static的规划；也可以 在每个t，优化t+1，然后总结出来一个policy，这种就是dynamic programming

很像高中学的归纳法