Pages

Wednesday 22 March 2017

A dream

Last night, I dreamed a strange dream.

I had to write software for a satnav. My part of it was the core engine - not the user interface. So I had to work out the best route from A to B. So far, a rather ordinary dream.
But what made this a strange drean, is that I worked out an algorithm for doing it, and when I woke up, I remembered the algorithm, and it seems to me to be workable.

So here's the algorithm.

Suppose you want to go from Snodgrass Road, SW1, London to McMurray Street, Endinburgh.

I happen to know that to go from London to Edinburgh, you go up the A1. I know that, because I have a mental map in my head of the major cities in the UK, and I know, roughly, how to get from one to another. So the problem now reduces to: How to get from Snodgrass Road to the south end of the A1, and how to get from the north end of the A1 to McMurray Street. You see, I've now reduced one big problem to two smaller ones.

To get from Snodgrass Road to the south end of the A1, I'd go up the Edgware road (A5) then around the M25. Again, I've reduced that problem to two smaller ones. And you keep opn doing this until you've got the whole route worked out.

Then, if that calculation was fast and there was time to spare, you could try small variations on the route, to see if changes made it faster.



Here's what I don't know.

Is this a good algorithm? Is this how existing satnavs do it? And why on earth did I have this dream in the first place?

1 comment: