11
$\begingroup$

I heard the term "dynamic programming" and naively assumed it had to do with programming in the sense of computer programming, as that's the only way I've heard the word used before — I used to work with software engineers a lot. After being laughed at a bit, I was told that when a mathematician or economist says "dynamic programming" it has nothing to do with computer programming; rather, it is just a technique for solving complicated problems in a dynamic setting.

I have read the Wikipedia page and I don't understand the difference. Isn't the computational approach the same as the mathematical one, just wisely using the computer as an assistant to execute the algorithm?

What exactly do the terms "programming" and "control" mean in this area?

$\endgroup$
3
  • 5
    $\begingroup$ Bellman used to work for RAND, which worked closely with and was partly funded by the military. In the military sense, "programming" is synonymous with "planning" or "scheduling", which exactly was one of the intended applications of Bellman's theory. A similar situation exists with linear programming, as Dantzig worked for RAND as well. $\endgroup$
    – J. M. ain't a mathematician
    Oct 16, 2011 at 16:43
  • 4
    $\begingroup$ @J.M. Have you seen this: link? You can learn about the birth of the name in the words of the master himself. See the section titled "Choice of the name Dynamic Programming". (I love the ending: "It was something not even a Congressman could object to.") $\endgroup$
    – Srivatsan
    Oct 18, 2011 at 13:51
  • 2
    $\begingroup$ Quite nice! Thanks @Sri! (I know the bit about making the mathematical research more palatable for the military brass, but it's nice to get it straight from the creator.) $\endgroup$
    – J. M. ain't a mathematician
    Oct 18, 2011 at 14:11

3 Answers 3

Reset to default
10
$\begingroup$

I think it's confusing because it's both at the same time. The origin of the name is a pre-computer sense of "programming" where the world simply meant the concrete planning of actions (say, deciding which vehicles to go where when you have a given amount of goods to transport from some points to other points). "Programming" is still used in that sense in combinatorial optimization.

Of course, nowadays such planning problems are solved by having a computer execute a program, though this program exists on a different meta-level than the plan for which vehicles to send where.

Also, some techniques originally developed for "programming" in the old sense have turned out to be useful for constructing computer programs, independently of the naming coincidence. So "dynamic programming" is now also an algorithmic technique that consists of solving and remembering smaller instances of a problem first and then building up to the problem you're actually interested in. This can be useful even in cases where the eventual problem is not a "programming" (in the planning/optimization sense) problem. So you use the technique while you program computers, but that's not why its name contains "programming".

$\endgroup$
1
  • 4
    $\begingroup$ The use of the word "programming" for computer programming developed from the same idea of "planning". Oxford English Dictionary's first citation for "programming" in this context is a paper by Mauchly (one of the inventors of ENIAC) in 1942. $\endgroup$
    – Robert Israel
    Oct 16, 2011 at 20:50
3
$\begingroup$

I don't have a source for this, but I would say that "algorithm" is a more precise synonym for "program" in the non-math sense than is "planning."

You also asked about "control." This implies a process that accepts inputs. Search "control theory."

$\endgroup$
3
$\begingroup$

In his autobiography "Eye of the Hurricane", Richard Bellman explains the origin of the name:

“I spent the Fall quarter (of 1950) at RAND. My first task was to find a name for multistage decision processes. “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” (p. 159).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .