1
$\begingroup$

In the Optimal Substructure Wikipedia,

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.

(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.

It is very unclear that why optimal substructure can be observed when we specify the at most intermediate stops? From my understanding (which can be wrong), even if we provide the at most intermediate stops such as K = 4, we can not conclude that the cheapest price will be the sum of the prices of the individual flights in the trip as the multi flight trip is usually not the sum of the prices of the individual intermediate flights.

Can anyone please explain me with examples?

$\endgroup$
1
  • $\begingroup$ Was my answer helpful? Have you considered upvoting and accepting my answer? Please comment if my answer can be improved. (This comment will be deleted upon feedback.) $\endgroup$
    – John L.
    May 11, 2022 at 18:27

1 Answer 1

1
$\begingroup$

It is better to ignore the confusing text below, which was added to that page of Wikipedia by an anonymous user on "20 August 2020", as shown on this comparison page.

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.

Here is a better explanation that could replace that confusing text.

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 that involves at most $k$ layovers is either the direct flight; or the cheapest flight from A to some location C that involves at most $t$ layover for some $t$ such that $0\le t\le k-1$, plus the cheapest flight from C to B that involves at most $k-1-t$ layovers.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.