why do we use the word optimal in case of optimal sub-structure , I guess in case of divide and conquer also we have sub-problems and they too when merged together provide the solution for entire problem .So what is the difference in terminology of sub-problems in divide and conquer and dynamic programming except for the fact that in the latter case we have overlapping sub-problems since both tend to imply that we have some sub-problems which combine to give an optimal solution to entire problem so in case of divide and conquer can we say that each sub-problem also gives us optimal solution ?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
The CLRS definition of optimal substructure:
A problem exhibits optimal substructure if any optimal solution to the problem contains within it optimal solutions to subproblems.
This make sense for both methods.
Divide&Conquer is used when subproblems are independent, there is no overlapping subproblems. In this case you just combine solutions to resolve the main problem.
Dynamic Programming is used when subproblems are dependent, there are overlapping subproblems and results are typically stored in some data structure for later reuse.
-
$\begingroup$ In case of Divide and Conquer approach , when subproblems are independent then how can there be a possibility that we have choices while calculating a particular solution ,henceforth we can neither maximize or minimize it since we will not be having any choices for sub-problems , they will be just combining to give a solution , then where is the key idea behind the word "optimal $\endgroup$– radhikaCommented Dec 23, 2015 at 22:07
-
$\begingroup$ It depends on what you understand by "divide&conquer", for example DP can be implemented in a top-down approach by what some people call "divide&conquer + memoization", where memoization is the technique of storing pre-computed results, its like a lazy version of the iterative/tabular DP bottom-up technique. However in most (if not all) books, the concept of "optimal sub-structure" is introduced with DP. At the same time, you can see DP as a form of divide&conquer. $\endgroup$ Commented Dec 23, 2015 at 23:13
-
$\begingroup$ As you said that DP is "divide&conquer + memoization",then what is optimal here since we have the sub-problems and we are simply not recomputing the results so then when to attach the word optimal with sub-problems there's where I am confused since it should be attached when we have some choices to make and I guess it has nothing to do with either dynamic or divide and conquer approach ,it is just an implication that the sub-problems give an optimal solution ,but don't know why it is a necessary condition for a problem to be solved by DP $\endgroup$– radhikaCommented Dec 24, 2015 at 5:24
-
$\begingroup$ Maybe you could provide more information, e.g. where do you hear about "optimal substructure" in D&C?, because as i said you will find it in (i think) any book as something relevant to DP. Consider the shortest path between two vertices X and Z, then you also have the shortest path between X and other vertex, say Y, in the middle. So the solution for your problem for X and Z is composed by optimal solutions for the subproblems i.e. the other vertices between X and Z. $\endgroup$ Commented Dec 24, 2015 at 5:53
-
$\begingroup$ Actually I did not see it anywhere in D & C , I just asked it since I was confused in the keyword "optimal" , but now it is clear , thanksss $\endgroup$– radhikaCommented Dec 24, 2015 at 17:21