1
$\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$
  • $\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$ – Apass.Jack May 5 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 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$ – Apass.Jack May 5 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$ – Marcus Ritt May 5 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$ – Marcus Ritt May 5 at 19:23
1
$\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$
1
$\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$

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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.