![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
Let's try this again
Dec. 22nd, 2004 07:02 pmThe 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.
