Notes:
Although clearly not a practical algorithm, in the tradition of non-deterministic search one might summarize the air travel search problem as: 1. Guess a set of flights that satisfies the travel query; 2. Guess a set of fares and a mapping from flights to fares that covers all flights exactly once; 3. Guess a partitioning of the fares into priceable units; and 4. Verify that all fares’ rules are met, where the rules may conceivably test all flights and fares in the journey but take a very restricted form.
In fact this isn’t the entire truth. For international travel computing the price of a solution involves some additional tests, called IATA checks, that compare one answer against other potential answers. In particular, IATA checks may raise the total price of a set of fares on a ticket to the maximum price of any other sufficiently similar set (similar in a technical sense), even if the other set of fares does not actually form a valid ticket itself. While practically IATA checks add greatly to the difficulty of international search, they are too complex to explore here.