patternModerate
How is Dynamic programming different from Brute force
Viewed 0 times
forcehowprogrammingdifferentdynamicbrutefrom
Problem
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 ??
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 ??
Solution
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.
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.
Context
StackExchange Computer Science Q#23599, answer score: 17
Revisions (0)
No revisions yet.