optimal substructure

In computer science, a problem is said to have optimal substructure if its optimal solution can be constructed efficiently from optimal solutions to its subproblems. This property is used to determine the usefulness of dynamic programming and greedy algorithms in a problem. An example of optimal substructure, finding a shortest path between two vertices in a graph, is shown in Figure 1. We first find the shortest path to the goal from all neighbors of the starting point (using the same procedure recursively), and then choose the overall path that minimizes the total edge weight. Typically, a greedy algorithm is used to solve a problem with optimal substructure wherever such an algorithm can be found; otherwise, providing the problem exhibits overlapping subproblems as well, dynamic programming is used. If there are no greedy algorithms or overlapping subproblems, often a straightforward search of the solution space is the best possible solution.

Problems with optimal substructure

* Longest-common subsequence problem.

<< Previous

Word Browser

Next >>

london palladium
a moveable feast
gerry hannah
king's highway (disambiguation)
criticisms of marketing
evolution of marketing
music of california
treknobabble
king's highway (st. augustine to mexico)
jody scheckter
aaas

kamchadal
separation anxiety disorder
moshe katsav
nivkh
american association for the advancement of science
halloween iii: season of the witch
john fitzwilliam stairs
sanctuary (band)
three forms of mathematical induction
bank one ballpark
the murder of roger ackroyd

gerald merrithew
fai
malic acid
the a.b.c. murders
spectral method
johann georg hamann
hess's law
samuel roxy rothafel
roy ridley
caligula (film)
tarjan's off line least common ancestors algorithm

lucius valerius potitus
marcus valerius corvus
southwest conference
antonio sanchez
homogeneous co ordinates
afghanistan timeline june 2003
ktm
oculomotor nerve
afghanistan timeline july 2003
trochlear nerve
trigeminal nerve