Optimal substructure: Difference between revisions

Revision as of 18:03, 8 July 2012

Revision as of 05:11, 9 July 2012

Line 1:

[[Image:Shortest path optimal substructure.png|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 to its subproblems. '''Optimal Substructure''' This property is used to determine the usefulness of dynamic programming and greedy algorithms in a problem. .<ref>[http://books.google.com/books?id=NLngYyWFl_YC&pg=PA15&dq=introduction+to+algorithms&psp=1&sig=jX-xfEDWJU3PprUwH8Qfxidli6M#PPP1,M1 Introduction to Algorithms], 2nd ed., (Cormen, Leiserson, Rivest, and Stein) 2001, p. 327. ISBN 0-262-03293-7.</ref> This property is used to determine the usefulness of [[dynamic programming]] and [[greedy algorithm]]s in a problem.

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