Let's try this again
Dec. 22nd, 2004 07:02 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
nibotThe girl at the ticket counter laughed because I had my confirmation number written on my hand. "You made me laugh—first time all day." At the airport they have these funky old terminals with big red klunky keys and fisheye green bulging CRT's. No Orbitz-like software robots here. Every proposed routing must be manually tried. "Anywhere in Southern California and I'll be happy," I said. In a flurry of keypresses she tried to put me through Cincinnati, Philadelphia, New York, or Atlanta, on Delta, AirTran, United, Continental or Northwest, to Los Angeles, Long Beach, San Diego, or Santa Ana (she smiled again because I knew the airport codes). No dice.
If you want to do a simple round-trip from BOS to LAX in two weeks, coming back in three, willing to entertain a 24 hour departure window for both parts, then limiting to "reasonable" routes (at most 3 flights and at most 10 hours or so) you have about 5,000 ways to get there and 5,000 ways to get back.
Imagine this drama at hundreds of terminals across America -- ticket agents frantickly searching for seats, after a midwestern snowstorm threw the airline transit network into complete havoc... finally: "I got one!" Doesn't want to let it go -- it's the only one and in a second someone else will take it. I gave the thumbs up. With another smile she pressed another key, and the machine spat out a new itinerary:
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.
I imagine the airline transit system as a massive hamstertube network, suspended just above—or below—the surface of the earth. In the clouds, I suppose. Airports, then, are these nexi where the hamstertubes converge. If only there were hamsterwheels to entertain us while we're stuck in hamsterland limbo.
I need to get my laptop fixed so I can hack on software robots crafted in Lisp while shuttling through the hamstertubes. If my Dell turns out to be unfixable, I think maybe I'll get a little iBook on ebay, although I think the lack of console mode and pins of I/O might be annoying. And maybe I'll ask that ticket agent for her phone number if she's working there tomorrow.
If you want to do a simple round-trip from BOS to LAX in two weeks, coming back in three, willing to entertain a 24 hour departure window for both parts, then limiting to "reasonable" routes (at most 3 flights and at most 10 hours or so) you have about 5,000 ways to get there and 5,000 ways to get back.
Imagine this drama at hundreds of terminals across America -- ticket agents frantickly searching for seats, after a midwestern snowstorm threw the airline transit network into complete havoc... finally: "I got one!" Doesn't want to let it go -- it's the only one and in a second someone else will take it. I gave the thumbs up. With another smile she pressed another key, and the machine spat out a new itinerary:
Delta Air Lines 4976, ROC to CVG - departing Rochester at 13:40
Delta Air Lines 0235, CVG to SNA - arriving Orange County at 18:10Suitably 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.
I imagine the airline transit system as a massive hamstertube network, suspended just above—or below—the surface of the earth. In the clouds, I suppose. Airports, then, are these nexi where the hamstertubes converge. If only there were hamsterwheels to entertain us while we're stuck in hamsterland limbo.
I need to get my laptop fixed so I can hack on software robots crafted in Lisp while shuttling through the hamstertubes. If my Dell turns out to be unfixable, I think maybe I'll get a little iBook on ebay, although I think the lack of console mode and pins of I/O might be annoying. And maybe I'll ask that ticket agent for her phone number if she's working there tomorrow.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2004-12-23 01:47 am (UTC)no subject
Date: 2004-12-23 06:20 am (UTC)isn't there like a terminal CLI mode on MacOS X? I mean it's BSD, just prettier?
I thought there were USB to Serial I/O converters.
If you can get more than 18 months out of a cheap Dell laptop then it's all good. My $600 Dell has gone almost 24 months now.
no subject
Date: 2004-12-24 12:03 am (UTC)I think the "prettier" part included the elimination of the console mode. I mean, there is a unix shell CLI, but no full-screen text mode like on a PC. Linux on the Mac does have such a text mode, but I don't think OS X does.
no subject
Date: 2004-12-23 07:09 pm (UTC)hurrah for the ibook! they never die. no. really. you'll have to decide that you don't love it anymore and sell it on ebay.
no subject
Date: 2004-12-24 07:44 am (UTC)Hmm, let me see how many of those airport codes I can name: CVG (only because you just said it, PHL?, JFK/EWR/LGA, ATL?, LAX, LGB, ??? (I would make up SDG), SNA.
Was Boston also one of your considered stopovers?
It's quite easy to put a bound on the size of the solution that will result in the cheapest price: find any solution, and then since every flight costs over $1 (maybe even over $10), one knows that it will never require more stops than the price of that solution. That gives us a finite search space (though the bound isn't a priori). Even without knowing any of the prices, if one knows the total number of cities involved, it seems clear to me that the cheapest flight path will never stop in the same airport more than once (or else one could find a cheaper itinerary just by turning the intervening flights into a long layover), so that puts a linear bound on the length of the itinerary, which gives n^n as a bound.
Of course, none of that is a particularly useful bound, and doesn't even get it down to the NP level.