Optimal substructure: Difference between revisions

Revision as of 08:13, 16 April 2025

Latest revision as of 08:14, 16 April 2025

Line 9:

==Example==

Consider finding a [[Shortest path problem|shortest path]] for traveling 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 ASeattle to BLos Angeles passes through CPortland and then DSacramento, then the shortest route from CPortland to BLos Angeles must pass through DSacramento too. That is, the problem of how to get from CPortland to BLos Angeles is nested inside the problem of how to get from ASeattle to BLos 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 Moscow. Even if that ticket involves stops in Miami and then London, we can't conclude that the cheapest ticket from Miami to Moscow 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.