The Wikipedia article on this topic is good, if short, and contains the following example of a
Question:
The Wikipedia article on this topic is good, if short, and contains the following example of a problem that lacks optimal substructure: https://en.wikipedia.org/wiki/Optimal_substructure#:~:text=In%20computer%20science%2C%20a%20problem,greedy%20algorithms%20for%20a%20problem.
Least-cost airline fare. (Using online flight search, we will frequently find that the cheapest flight from airport A to airport B involves a single connection through airport C, but the cheapest flight from airport A to airport C involves a connection through some other airport D.) However, if the problem takes the maximum number of layovers as a parameter, then the problem has optimal substructure: the cheapest flight from A to B involving a single connection is either the direct flight; or a flight from A to some destination C, plus the optimum direct flight from C to B.
Assume that airline flights are represented as a graph where the nodes are airports and edges (each labeled with an arbitrary monetary cost - not a distance!) exist when such a flight is offered. For the parts below that ask for an algorithm, you may give an English language description or pseudo-code with either good comments or a separate statement about the strategy
. a. Describe an algorithm for finding the lowest cost from airport A to B, where the only flights considered are direct flights or flights with one intermediate stop.
b. Generalize your algorithm to take as parameters not just A and B, but the maximum number of intermediate stops, where 0 means a direct flight.
c. Explain why the generalized algorithm has optimal substructure.
d. Describe an algorithm for finding the lowest cost from airport A to B where there is no limit to the number of intermediate stops.
e. Explain why the problem now lacks optimal substructure, after we have removed any limit on the number of intermediate stops
Management information systems
ISBN: 978-0073376813
10th edition
Authors: James A. O Brien, George M. Marakas