|
Optimal substructure - Definition and Overview |
| Related Words: Basement, Basis, Bed, Bedding, Bedrock, Bottom, Floor, Flooring, Foundation, Fundamental, Ground, Hardpan, Infrastructure, Pavement, Principle, Radical, Rudiment, Seat, Sill |
|
|
 Figure 1. Finding the shortest path using optimal substructure; wavy lines indicate shortest paths In computer science, the Optimal-substructure property refers to problems with optimal solutions that exhibit optimal solutions in 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
|
|
|
