Optimal substructure: Difference between revisions

Revision as of 20:29, 21 October 2014

Revision as of 19:04, 17 June 2015

Line 9:

Consider finding a [[Shortest path problem|shortest path]] for travelling between two cities by car, as illustrated in Figure 1. Such an example is likely to exhibit optimal substructure. That is, if the shortest route from Seattle to Los Angeles passes through Portland and then Sacramento, then the shortest route from Portland to Los Angeles must pass through Sacramento too. That is, the problem of how to get from Portland to Los Angeles is nested inside the problem of how to get from Seattle to Los Angeles. (The wavy lines in the graph represent solutions to the subproblems.)

As an example of a problem that is unlikely to exhibit optimal substructure, consider the problem of finding the cheapest airline ticket from Buenos Aires to MoscowKyiv. Even if that ticket involves stops in Miami and then London, we can't conclude that the cheapest ticket from Miami to MoscowKyiv stops in London, because the price at which an airline sells a multi-flight trip is usually not the sum of the prices at which it would sell the individual flights in the trip.

==Definition==