2 ms·

Here's the classic presentation people usually refer to when talking about flight pricing complexity. http://www.demarcken.org/carl/papers/ITA-software-travel-

• kiwidrew 15y ago
  Well, if one narrows down the options a bit, it becomes far more tractable. Considering that Google's flight search only works for domestic return trips of 15 days or less (it didn't seem to give me results for anything longer than that?) and doesn't allow stopovers or open jaws, it's entirely possible that the complexity is much reduced.
• objclxt 15y ago
  What's interesting is that you linked to an ITA Software presentation, and Google own ITA Software. So it's almost certain that some of the people who put that document together worked on this pre-computed solution.
• lars 15y ago
  If I remember correctly, it's mentioned in Artificial Intelligence, A Modern Approach that this problem is not only hard but in fact formally undecidable in the general case.