[Year 12 SofDev] The complexity of buying tickets for flights

[Savage, John L]

I was just reading an essay on ANSI Lisp (as you do) and came across this humdinger discussing the computing of ticket booking:

The real challenge is that a single fixed itinerary (a fixed set of flights from BOS to LAX and a fixed set back) with only two flights in each direction may have more than 10,000 possible combinations of applicable "fares", each fare with complex restrictions that must be checked against the flights and the other fares. That means that the search space for this simple trip is of the order 5000 x 5000 x 10000, and a naive program would need to do a _lot_ of computation just to validate each of these possibilities. Suitably formalized, its not even clear that the problem of finding the cheapest flight is NP-complete, since it is difficult to put a bound on the size of the solution that will result in the cheapest price. If you're willing to dispense with restrictions on the energy in the universe, then it is actually possible to formalize the cheapest-price problem in a not-too-unreasonable way that leads to a proof of undecidability by reduction to the Post correspondance problem :-).

From
Carl de Marcken of ITA Software<http://www.itasoftware.com/>
Source: http://www.paulgraham.com/carl.html

They do it by wrapping C++, C and Java in Lisp, not bad for a language that has been "dead" longer than most modern languages have been alive.


Laurie Savage
http://accelerus.pvgc.vic.edu.au


Important - This email and any attachments may be confidential. If received in error, please contact us and delete all copies. Before opening or using attachments check them for viruses and defects. Regardless of any loss, damage or consequence, whether caused by the negligence of the sender or not, resulting directly or indirectly from the use of any attached files our liability is limited to resupplying any affected attachments. Any representations or opinions expressed are those of the individual sender, and not necessarily those of the Department of Education and Early Childhood Development.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.edulists.com.au/pipermail/sofdev/attachments/20141026/a118b26c/attachment.html