How is Dynamic programming different from Brute force

Question

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 ??

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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.

Answer 6

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.