Optimal substructure: Difference between revisions

Revision as of 14:49, 13 November 2023

Revision as of 00:21, 15 July 2024

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>