Optimal substructure: Difference between revisions

Revision as of 02:51, 17 August 2014

Revision as of 20:29, 21 October 2014

Line 1:

[[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 efficiently from optimal solutions of its subproblems. This property is used to determine the usefulness of dynamic programming and greedy algorithms for a problem.<ref>[http://books.google.com/books?id=NLngYyWFl_YC&pg name=PA15&dq=introduction+to+algorithms&psp=1&sig=jX-xfEDWJU3PprUwH8Qfxidli6M#PPP1,M1cormen>{{cite book|title=Introduction to Algorithms], 2nd|edition=3rd|last1=Cormen|first1=Thomas edH., (Cormen, |last2=Leiserson, Rivest,|first2=Charles andE. Stein) 2001,|last3=Rivest|first3=Ronald pL. 327.|last4= ISBNStein |first4=Clifford|date=2009 |isbn=978-0-262-0329303384-78|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 proved by induction that this is optimal at each step.<ref (Cormenname=cormen et al. pp.&nbsp;381–2)./> Otherwise, providing the problem exhibits [[overlapping subproblem]]s as well, [[dynamic programming]] is 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. -->

In the application of [[dynamic programming]] to [[Optimization (mathematics)|mathematical optimization]], [[Richard Bellman]]'s [[Principle of optimality|Principle of Optimality]] is based on the idea that in order to solve a dynamic optimization problem from some starting period ''t'' to some ending period ''T'', one implicitly has to solve subproblems starting from later dates ''s'', where ''t<s<T''. This is an example of optimal substructure. The Principle of Optimality is used to derive the [[Bellman equation]], which shows how the value of the problem starting from ''t'' is related to the value of the problem starting from ''s''.