18
$\begingroup$

I was reading up on Dynamic Programming when I came across the following quote

A dynamic programming algorithm will examine all possible ways to solve the problem and will pick the best solution. Therefore, we can roughly think of dynamic programming as an intelligent, brute-force method that enables us to go through all possible solutions to pick the best one. If the scope of the problem is such that going through all possible solutions is possible and fast enough, dynamic programming guarantees finding the optimal solution

The following example was given

For example, let's say that you have to get from point A to point B as fast as possible, in a given city, during rush hour. A dynamic programming algorithm will look into the entire traffic report, looking into all possible combinations of roads you might take, and will only then tell you which way is the fastest. Of course, you might have to wait for a while until the algorithm finishes, and only then can you start driving. The path you will take will be the fastest one (assuming that nothing changed in the external environment)

Brute Force is trying every possible solution before deciding on the best solution .

How is Dynamic Programming different from Brute Force if it also goes through all possible solutions before picking the best one , the only difference i see is that Dynamic Programming takes into account the additional factors ( traffic conditions in this case).

Am i correct to say that Dynamic Programming is a subset of Brute Force method ??

$\endgroup$
5
  • 1
    $\begingroup$ Traffic conditions are a red herring. You could consider them in any algorithm. $\endgroup$ Apr 9, 2014 at 16:52
  • $\begingroup$ Related answer. $\endgroup$
    – Raphael
    Apr 9, 2014 at 22:41
  • $\begingroup$ Your first quote doesn't define dynamic programming. $\endgroup$ Apr 10, 2014 at 9:18
  • $\begingroup$ @reinierpost Well, it tries to get there with intelligent, brute force, but then forgets to describe the "intelligent" part $\endgroup$
    – Izkata
    Apr 10, 2014 at 14:34
  • $\begingroup$ @Izkata By that reasoning, every algorithm is "intelligent brute force" (which is an oxymoron, anyway). $\endgroup$
    – Raphael
    Apr 10, 2014 at 14:37

6 Answers 6

17
$\begingroup$

A dynamic programming algorithm will examine all possible ways to solve the problem and will pick the best solution.

This statement is just plain wrong.

Dynamic programming recurrences do (often) consider all possible ways to split the given problem instance into smaller instances according to some scheme. However, it will not combine all solutions to all partial problems with each other and pick the best -- it combines only optimal partial solutions (and picks the best out of those).

The fact that this yield an optimal solution for the original problem is not trivial and does, in fact, only hold for some problems. Namely those that fulfill the Bellman principle of optimality (one of the most fishy, misunderstood "definitions" that are regularly quoted). See here for some more thoughts on that.

As a concrete example, consider the Bellman-Ford algorithm on a complete graph $K_n$ with unit weights: it only ever considers paths of length one and two (i.e. $\Theta(n^2)$ many) because those using one edge are all optimal. But there are infinitely many solutions if you don't bound the maximum number of edges allowed, and still $\gg (n-1)!$ many if you allow every node to be used only once. So clearly, Bellman-Ford -- a dynamic programming algorithm -- does not perform a brute-force search.

$\endgroup$
3
  • $\begingroup$ "This statement is just plain wrong" -- Fix it. $\endgroup$
    – nmclean
    Apr 10, 2014 at 12:08
  • 4
    $\begingroup$ @nmclean My experience with editing algorithm-related articles on Wikipedia has been less than pleasant, so no. I'd rather invest my time here. $\endgroup$
    – Raphael
    Apr 10, 2014 at 12:31
  • $\begingroup$ I tried my luck and edited the article. Hope it's a bit less wrong now. $\endgroup$
    – C4stor
    Apr 10, 2014 at 19:23
9
$\begingroup$

Dynamic Programming is clever as it reuses computation, while brute force doesn't. Suppose to solve, f(6), you need to solve 2 sub-problems which both call f(3). The brute force method will calculate f(3) twice thereby wasting effort while dynamic programming will call it once, save the result in case future computations need to use it. In many problems, dynamic improves the exponential complexity of brute force to polynomial complexity.

$\endgroup$
7
  • 9
    $\begingroup$ That's memoization, which is just one of many tricks that DP employs. $\endgroup$
    – Ben Voigt
    Apr 9, 2014 at 18:15
  • 4
    $\begingroup$ Brute force with memoisation is still inefficient; only additional structure/pruning provided by DP recurrences make memoisation pay off. $\endgroup$
    – Raphael
    Apr 9, 2014 at 22:37
  • 3
    $\begingroup$ I don't know anything about dynamic programming, but I'm fairly sure there's more to it than just adding caches to a brute-force algorithm. I think dynamic programming avoids testing every possible combination by subdividing the problem space, finding an optimal solution for each small subdivision, and then combining them to create an overall best solution. (It might do this recursively, sub-diving the sub-divisions.) This only works if you can express the problem in a way that allows for combination of solutions like this and still get an overall optimum. $\endgroup$ Apr 10, 2014 at 8:06
  • 1
    $\begingroup$ This answer is actually quite accurate. I advise reading a textbook like Cormen et al: "Introduction to Algorithms" to learn more about dynamic programming, this book has a quite decent chapter on it. In a nutshell, efficient dynamic programming makes use of two properties of the (optimization) problem you want to solve: optimal solutions can be constructed from the optimal solutions of smaller sub-problems, and the total number of smaller sub-problems is actually rather small. Then, you can build all sub-problem solutions bottom-up, accelerating the computation at the cost of memory. $\endgroup$
    – MRA
    Apr 10, 2014 at 12:14
  • $\begingroup$ Or, to put it in even simpler terms: If you know how to compute a binomial coefficient using Pascal's triangle then you know all you ever need to know about dynamic programming. $\endgroup$
    – MRA
    Apr 10, 2014 at 12:28
3
$\begingroup$

The distinction the Wikipedia article might be trying to make is between three types of algorithms:

  1. Algorithms which go over all possible solutions, choosing the optimal one.

  2. Algorithms which go over a subset of all possible solutions, chosen so that the optimal solution belongs to the subset.

  3. Algorithms which go over a subset of all possible solution, without the guarantee that the optimal solution belongs to the subset.

The first two types of algorithms produce the optimal solution, while the third type aims to produce a "good" solution rather than an optimal solution. In my opinion, the distinction between the first two kinds is not so clear cut.

Let me start by giving simple examples for all three types of algorithms, in the context of shortest path (the example you give).

  1. Try all possible paths. This is known as brute force.

  2. Try all possible paths, keeping track of the minimum solution so far. Whenever the current path you are constructing is more expensive than the minimum solution so far, abandon it and choose another one (we imagine that the distance is computed on a segment-by-segment basis). This is called pruning.

  3. Look at the map, consider a few paths, and choose the best one among them. This is an algorithm for a human rather than a computer.

These examples are rather crude, and perhaps don't paint a very accurate picture. Pruning is crucial in many situations, for example in computer chess. If you're curious, look up the A* algorithm, which is actually used for shortest path.

Dynamic programming is a technique for speeding up significantly the brute force algorithm. It is somewhat misleading, however, to think of it this way. It is an algorithmic technique for solving optimization problems. You can implement pruning in the context of dynamic programming.

In the case of shortest path, here is one version of dynamic programming. We compute inductively the shortest path from the starting point to any other point of significance in the map using $t$ segments. Given the data for a certain $t$, we can compute the data for $t+1$ by enumerating over the last "hop" in any path from the starting point to any other point. When $t$ is large enough, we will have found the shortest path from the starting point to any other point. This is much more efficient than brute force, though not as efficient as some other dynamic programming algorithms.

$\endgroup$
1
  • $\begingroup$ And then there's removing a candidate from consideration without fully processing it. For example, finding the set of non-negative numbers with the minimum sum, you don't actually have to sum each set completely, only go until the sum exceeds the current best. This is a similar idea to pruning but orthogonal. Combining the two ideas yields "branch-and-bound", where a problem of reduced complexity is solved and used to justify pruning. $\endgroup$
    – Ben Voigt
    Apr 9, 2014 at 18:14
0
$\begingroup$

Dynamic programming is much faster than brute force. Brute force may take exponential time, while dynamic programming is typically much faster.

The analogy to brute force is a very loose one. Dynamic programming is not a magic silver bullet that lets you take any brute force algorithm you want and make it efficient.

$\endgroup$
1
  • 5
    $\begingroup$ That's a consequence, not an explanation. $\endgroup$
    – Raphael
    Apr 9, 2014 at 22:26
-2
$\begingroup$

This is straightforward. Dynamic programming is a "search strategy" which uses additional factors to narrow down a search. If there is no solution in the search space, dynamic programming will (typically) do a search through every element of the search space. But that does not mean that it is a brute force search.

$\endgroup$
1
  • $\begingroup$ "If there is no solution in the search space, dynamic programming will (typically) do a search through every element of the search space." -- wrong, see my answer. $\endgroup$
    – Raphael
    Apr 10, 2014 at 7:28
-2
$\begingroup$

The statement that dynamic programming is intelligent brute force is correct, but a bit difficult to understand with that phrasing. The point of dynamic programming is generally to take a problem and break it into smaller pieces in an intelligent way. After you've done that, you will be using brute force to solve each small piece, and then you will be using brute force again to combine the pieces into a final solution. So while you could definitely say that dynamic programming is a type of brute force solution, the trick lies in how you use that brute force.

$\endgroup$
1
  • 1
    $\begingroup$ "you will be using brute force to solve each small piece" -- wrong. You will typically be using the same approach recursively. $\endgroup$
    – FrankW
    Apr 10, 2014 at 14:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.