Optimal substructure

From Wikipedia, the free encyclopedia

Figure 1. Finding the shortest path using optimal substructure; straight lines indicate single edges, wavy lines indicate shortest 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. 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.

[edit] Definition

It is possible to give a slightly more formal definition of optimal substructure. Let a "problem" be a collection of "alternatives", and let each alternative have an associated cost c(a). Our problem is to find that set of alternatives which maximizes c(a). Suppose we can partition the problem into subsets of alternatives such that each alternative falls into one subset exactly, and suppose we give each subset its own cost function. We can find the maxima of each of these cost functions, and we can also find the maxima of the global cost function, restricted to the same subsets. If these maxima match for each subset, then it's almost obvious that we can pick a global maximum not out of the full set of alternatives, but out of only the set which consists of the maxima of the smaller, local cost functions we have defined. If maximizing the local functions is a problem of "lower order", and (specifically) if, after a finite number of these reductions, the problem becomes trivial, then we have an optimal substructure.