Dynamic programming — mathematics versus computer

1.5k Views Asked by At

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?

2

There are 2 best solutions below

1
On BEST ANSWER

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".

0
On

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."