8
$\begingroup$

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?

$\endgroup$
6
  • $\begingroup$ A simple simplified answer could be "problems that can be solved recursively should have recursive substructures". Optimal substructure? That seems off the point. $\endgroup$
    – John L.
    May 5, 2019 at 4:38
  • $\begingroup$ @Apass.Jack resources.saylor.org/wwwresources/archived/site/wp-content/… In the overview section, near the end of the paragraph, it says " Likewise, in computer science, a problem that can be broken down recursively is said to have optimal substructure" $\endgroup$
    – Sazz
    May 5, 2019 at 5:31
  • $\begingroup$ Where is that article published? No author is listed. No date is given. It looks like its author is pretty familiar with dynamic programming. However, the article itself might not be the best reference. May I ask why you are reading that article? Are you learning dynamic programming for the first time or you are experienced in dynamic programming? $\endgroup$
    – John L.
    May 5, 2019 at 12:55
  • $\begingroup$ The article is from Wikipedia. Go one step further and have a look at en.wikipedia.org/wiki/Optimal_substructure. The idea is that the optimal solution of a subproblem can be extended to the optimal solution of the problem. This is not always the case. $\endgroup$ May 5, 2019 at 15:01
  • 1
    $\begingroup$ @Apass.Jack Partially, but wanted to point out Sazz that I believe that Wikipedia's article on optimal substructure responds his question. On the article: it seems to be and old version, see the source on the last page. $\endgroup$ May 5, 2019 at 19:23

4 Answers 4

5
$\begingroup$

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:

  1. 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.

  2. 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.

  3. 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.

  4. 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.

$\endgroup$
2
$\begingroup$

Every problem can be solved recursively. Recall first that every problem can be solved using an algorithm which uses a WHILE loop and conditionals. Indeed, the operation of a CPU can be described in this way. We can adapt this solution to a (tail) recursive procedure as follows.

The parameters are the instruction pointer, the content of the registers, and the content of memory. The procedure performs the instruction that the instruction pointer is pointing at, modifying the instruction pointer, the registers, and the memory. Then (unless the instruction was HALT), it calls itself recursively with the updated instruction pointer, register contents, and memory contents.

$\endgroup$
3
  • $\begingroup$ This does not even mention optimal substructure and therefore it does not answer OP's question. , $\endgroup$ Dec 2, 2019 at 14:26
  • $\begingroup$ You might have missed the point of this answer. $\endgroup$ Dec 2, 2019 at 14:27
  • $\begingroup$ I agree with @AlanEvangelista and I think this is actually answering a different question (e.g. "Does every problem accept a recursive algorithm?"), which is different from saying that every algorithm is defined recursively. I tried that clarify this here $\endgroup$ Apr 4, 2020 at 21:18
2
$\begingroup$

When solving an optimization problem recursively, optimal substructure is the requirement that the optimal solution of a problem can be obtained by extending the optimal solution of a subproblem (see for example, Cormen et al. 3ed, ch. 15.3).

Consider for example the problem of finding a simple shortest $s$-$t$ path in a directed graph with non-negative distances. Such a path must visit a predecessor $u$ of $t$. So if you are able to recursively find the shortest $s$-$u$ path for all predecessors $u$ of $t$, you can find a shortest $s$-$t$ path. In this case you have an optimal substructure.

Contrast this with finding a simple longest $s$-$t$ path. Such a path must also visit a predecessor $u$ of $t$. However, it isn't true that the longest $s$-$t$ path can be obtained by extending some longest $s$-$u$ path for a predecessor $u$ of $t$, since such a path may already visit $t$, and so its extension may not be a simple path, and you cannot remove the resulting cycle to make the path simple, since this can make it shorter. In this case you don't have an optimal substructure.

The longest $s$-$t$ path can be found by choosing a different kind of subproblem that has optimal substructure. If you define $C(s,t,V)$ as the longest path from $s$ to $t$ without visiting the vertices in $V$, you get \begin{align*} C(s,t,V)= \begin{cases} \max_{u\in N^{-}(t)\setminus V} C(s,u,V\cup\{t\})+d_{ut}, & \text{if $s\neq t$ and $N^{-}(t)\setminus V\neq \emptyset$},\\ -\infty, & \text{if $s\neq t$ and $N^{-}(t)\setminus V=\emptyset$},\\ 0, & \text{if $s=t$}, \end{cases} \end{align*} where $N^-(t)$ is the set of predecessors of vertex $t$, and $d_{uv}$ is the distance between $u$ and $v$.

$\endgroup$
1
  • $\begingroup$ This doesn't seem to answer the question in the OP. You explained what it means for a problem to have optimal substructure, but did not answer if indeed all recursive problems have optimal substructure. $\endgroup$ Apr 4, 2020 at 20:03
2
$\begingroup$

The article you were reading might not be not good enough for educational purpose, especially for a beginner in dynamic programming. It is not accurate enough, either.

It is apparent, as noticed by Marcus Ritt that article copies from the Wikipedia article on dynamic programming, a lot.

However, that article is not up to date with the following statement at the latest version of Wikipedia,

Likewise, in computer science, if a problem can be solved optimally by breaking it into sub-problems and then recursively finding the optimal solutions to the sub-problems, then it is said to have optimal substructure.

We can compare the statement above with the following statement in the article, where "recursively" instead of "optimally" is used to define optimal substructure, which is not correct.

Likewise, in computer science, a problem that can be broken down recursively is said to have optimal substructure."


Are there problems that can be solved recursively that do not have an optimal substructure?

This question is more or less off the point in the sense that being recursive is not related to being optimal. Not directly.

The truism would be that problems that can be solved recursively should have recursive substructures. Likewise, if an optimization problem can be solved by breaking it into sub-problems and then recursively finding the optimal solutions to the sub-problems, then it is said to have optimal substructure.

If we have to answer that question head-on, then the answer is, of course, yes and plenty of them. We can compute Fibonacci numbers recursively, but there is no apparent optimal substructure in Fibonacci numbers. We can compute recursively the factorials which does not have substructure that can be called optimal reasonably.

In fact, Yuval's answer presents a common view that explained why most programs can be considered or adapted as solving problems recursively.


It might have been better had you followed an excellent textbook, such as the most popular textbook Introduction to Algorithm by CLRS, in case you have not read it yet. Its chapter 15, Dynamic Programming explains the basic concepts and techniques about dynamic programming clearly. Section 3 of that chapter, elements of dynamic programming, elaborates on the components of dynamic programming, "Optimal substructure", "Overlapping subproblems", "Reconstructing an optimal solution" and "Memoization".

$\endgroup$
0

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.