patternMinor
Do all recursive problems have optimal substructure?
Viewed 0 times
optimalallrecursiveproblemssubstructurehave
Problem
I am reading about dynamic programming and I understand the overlapping subproblem requirement but not sure why optimal substructure is explicitly stated. Are there problems that can be solved recursively that do not have an optimal substructure?
Solution
I think there is some confusion in terminology here. Part of the problem is what we mean by problem and algorithm. But there is more to it:
-
Textbooks like CLRS introduce the notion of optimal substructure as a property of problems (and not algorithms directly). That's because an algorithm often transforms a problem statement into other problem/s and, as a result, an algorithm may establish a link between problem solutions with subproblem solutions. Indeed, CLRS defines optimal substructure as follows:
-
Just because a problem (and actually all problems) may accept a recursive formulation or algorithm, it doesn't of course mean of course that every algorithm to solve it is indeed recursive (this is in relation to Yuval Filmus's answer). For a particular algorithm to be recursive, it must call itself recursively.
-
Similarly, just because an algorithm may involve some form of iteration or even recursion (e.g. in some of its subroutines), it doesn't mean that the algorithm is actually solving the original problem recursively.
-
Last but not least, just because an algorithm is recursive, it does not mean it solves a problem with optimal substructure where solutions to the original problem are the result of combining solutions to sub-problems of the same type. For example, if you write an algorithm to sort numbers, and this algorithm sorts the input and then once it's done sorting, it e.g. calls itself recursively with a NOP in each call for some depth of recursion, that does not mean that the algorithm is actually building the sorted sequence (the solution to the stated problem) from solutions to subproblems, and thus exploiting the optimal substructure of the problem.
-
Textbooks like CLRS introduce the notion of optimal substructure as a property of problems (and not algorithms directly). That's because an algorithm often transforms a problem statement into other problem/s and, as a result, an algorithm may establish a link between problem solutions with subproblem solutions. Indeed, CLRS defines optimal substructure as follows:
"A problem exhibits optimal substructure if a solution to the problem contains solutions to its sub-problems". While it doesn't say this directly, the term "contains" implies through an algorithm. -
Just because a problem (and actually all problems) may accept a recursive formulation or algorithm, it doesn't of course mean of course that every algorithm to solve it is indeed recursive (this is in relation to Yuval Filmus's answer). For a particular algorithm to be recursive, it must call itself recursively.
-
Similarly, just because an algorithm may involve some form of iteration or even recursion (e.g. in some of its subroutines), it doesn't mean that the algorithm is actually solving the original problem recursively.
-
Last but not least, just because an algorithm is recursive, it does not mean it solves a problem with optimal substructure where solutions to the original problem are the result of combining solutions to sub-problems of the same type. For example, if you write an algorithm to sort numbers, and this algorithm sorts the input and then once it's done sorting, it e.g. calls itself recursively with a NOP in each call for some depth of recursion, that does not mean that the algorithm is actually building the sorted sequence (the solution to the stated problem) from solutions to subproblems, and thus exploiting the optimal substructure of the problem.
Context
StackExchange Computer Science Q#108967, answer score: 5
Revisions (0)
No revisions yet.