Figure 1. Finding the shortest path using optimal substructure; wavy lines indicate shortest paths

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. A diagram demonstrating solving the shortest path problem using optimal substructure. ... A diagram demonstrating solving the shortest path problem using optimal substructure. ... Wikibooks Wikiversity has more about this subject: School of Computer Science Open Directory Project: Computer Science Collection of Computer Science Bibliographies Belief that title science in computer science is inappropriate Categories: Computer science | Academic disciplines ... In computer science, dynamic programming is a method for reducing the runtime of algorithms exhibiting the properties of overlapping subproblems and optimal substructure, described below. ... Greedy algorithm - Wikipedia /**/ @import /skins-1. ...

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.