Optimal substructure: Difference between revisions

Revision as of 16:59, 14 October 2022

Latest revision as of 08:14, 16 April 2025

(5 intermediate revisions by 4 users not shown)

Line 1:

{{Short description|Property of a computational problem}}

[[Image:Shortest path optimal substructure.svg|200px|thumb|'''Figure 1'''. Finding the shortest path using optimal substructure. Numbers represent the length of the path; straight lines indicate single [[Edge (graph theory)|edges]], wavy lines indicate shortest [[Path (graph theory)|paths]], i.e., there might be other vertices that are not shown here.]]

In [[computer science]], a problem is said to have '''optimal substructure''' if an optimal solution can be constructed from optimal solutions of its subproblems. This property is used to determine the usefulness of greedy algorithms for a problem.<ref name=cormen>{{cite book|title=Introduction to Algorithms |edition=3rd|last1=Cormen|first1=Thomas H. |last2=Leiserson |first2=Charles E. |last3=Rivest|first3=Ronald L. |last4= Stein |first4=Clifford|date=2009 |isbn=978-0-262-03384-8|publisher=[[MIT Press]]|authorlink1=Thomas H. Cormen |authorlink2=Charles E. Leiserson|authorlink3=Ron Rivest |authorlink4=Clifford Stein}}</ref>

Typically, a [[greedy algorithm]] is used to solve a problem with optimal substructure if it can be proven by induction that this is optimal at each step.<ref name=cormen /> Otherwise, provided the problem exhibits [[overlapping subproblemsubproblems]]s as well, [[Divide and conquer algorithm|divide-and-conquer]] methods or [[dynamic programming]] may be used. If there are no appropriate greedy algorithms and the problem fails to exhibit overlapping subproblems, often a lengthy but straightforward search of the solution space is the best alternative.

<!-- A special case of optimal substructure is the case where a subproblem S_ab has an activity P_y, then it should contain optimal solutions to subproblems S_ay and S_yb. --> <!-- *TODO: Add Recursion, misc. -->