.
According... - Grin with cat attached — LiveJournal
Previous Entry Next Entry
According... Oct. 6th, 2003 01:43 pm
to the RAC, the quickest route from Leytonstone to Whitby is via Milton Keynes.

Or, more precisely, it's via the M11 if you select "quickest route", but if you then ask it "so what if I went via MK?" it give you an answer that's about 15 minutes quicker.

In either case it's a 6-hour drive (with short breaks), which is not something I greatly enjoy.

Plus I'll need to rent a car from home (anyone know anywhere that's near, or will deliver a car to, Leytonstone?)

Meh. Hate Driving. Hate that particular rail journey slightly more.

(no subject) - (Anonymous)
From: wechsler
Date: October 6th, 2003 - 06:02 am (Link)
*nods* Just wondering if anyone had dealt with any of them.
From: tephramancy
Date: October 6th, 2003 - 06:00 am (Link)
It's a shit of a journey, isn't it? I'm just glad I'm doing it alone this year, so I can put my walkman on and fall asleep, at least for the London -> York leg of it.
From: ciphergoth
Date: October 6th, 2003 - 06:05 am (Link)
NB this isn't recommended if you plan to drive there by yourself :-)
From: tephramancy
Date: October 6th, 2003 - 06:06 am (Link)
Ah yes, should've clarified that I was talking about the train journey ;-)
From: ciphergoth
Date: October 6th, 2003 - 06:03 am (Link)
It's far from clear to me that writing a route planner that always gives the fastest route is computationally feasable. I have no idea how you would go about writing something like, say, the TfL Journey Planner in such a way that the computational cost of each journey calculation is in any way reasonable...
From: babysimon
Date: October 6th, 2003 - 06:17 am (Link)
NB: It's not travelling salesman. It is in fact in P. It's called Dijkstra's Algorithm.
From: ciphergoth
Date: October 6th, 2003 - 06:33 am (Link)
In fact there's a very simple algorithm that is at worst linear (maybe loglinear) in the number of arcs: from the starting point, you start to calculate how long it will take you to reach *every* destination, in the order in which you would reach them, until you get the desired destination. The trouble is that with that many arcs even that is a heavy load.

foreach node in nodes:
    node.state = toofar
departure.state = borderline
departure.totaltime = 0
while true:
    node = nodes.getBorderlineNodeWithLeastTotaltime()
    if node == destination:
        return
    for arc in node.arcs:
        if arc.node.state == fullyconsidered:
            next
        if arc.node.state == toofar
            arc.node.state = borderline
            arc.node.totaltime = node.totaltime + arc.time
        else:
            arc.node.totaltime = min(arc.node.totaltime, node.totaltime + arc.time)
    node.state = fullyconsidered
From: ciphergoth
Date: October 6th, 2003 - 06:38 am (Link)
Whoops, I just posted Dijkstra's algorithm without realising. Never mind me.

Well the point is that it's expensive finding the time from one destination to every other destination, isn't it?
From: babysimon
Date: October 6th, 2003 - 07:20 am (Link)
Depends what you mean by expensive. Personally, I think if it's in P it's not expensive. Plus you can cache most of your work ISTR.
From: babysimon
Date: October 6th, 2003 - 06:18 am (Link)
When hiring cars in East London I always use Avis at LCY as they seem to be cheaper than anywhere else I've found (modulo EasyCar "bargains").
From: feanelwa
Date: October 6th, 2003 - 09:52 am (Link)
Yes, but you're so good at it *hugs* and anyway Denny will be very grateful *smirk*

While we're here...you got any spaces left?