April 21st, 2004


userinfo senji
2004/04/21 12:07:00 - Map Annealing
diziet and emperor were talking about Simulated Annealing as a tool in Automatic Graph Drawing Algorithms on Monday night, and it's just struck me that a similar process seems to operate in finding routes between places.



This map shows routes from Girton (off the top left) to the Grafton Centre, in Cambridge.
(1) is my initial "naïve" route; which is probably the shortest, but one runs into too many pedestrians and traffic-lights.
(2) is my first revision, based mainly on the fact that I tend to turn down Oxford Road to get to a lot of other places, but as is clearly visible from the map (if not my head) it's much further).
(3) describes a simple optimisation to (2) that turns out to be generally helpful.
(4) was the next approach, but I quickly realised that the optimisation (5) that I used to use from Darwin Drive was still applicable.
(6) is the route I currently use, I think it's probably the most optimal, particularly since if the traffic is heavy at the turn-off point you can revert to (5).
(7) is a rejected optimisation to (2) that experimentally took longer than the original.


Current Mood: [mood icon] geeky

< | 5 glosses | comment | > )

userinfo yrieithydd
2004/04/21 15:19:39
Intriguing. I'd just stick to 1 myself (given that all but 2 make sense from where I live) but maybe that just reflects the fact that I hate Mitchim's Corner and I'm not hugely keen on Victoria Road. I only tend to use those routes when I have to. I also don't find pedestrians that much of a hassle on Magdalene street. I also tend to choose the pedestrians on Trinity Street over the backs.

Having said that, last time I came back from the Grafton I did go via Mitchim's corner but that was because I was following emperor at the time!
reply | thread )
userinfo ewx
[userpic]
2004/04/21 16:25:42
How does down Castle Hill then along Chesterton Rd to pick up 5 sound?
reply | thread )
userinfo senji
[userpic]
2004/04/21 17:46:25
I think that depends on how lucky you are with the lights at the bottom of Castle Hill. I might give it a go next time....
reply | parent | thread )
userinfo yrieithydd
2004/04/21 23:51:40
Nooooooooo, Chesterton Lane should be avoided at all costs! There are homicidal bus drivers there!
reply | parent | thread )
userinfo acronym
[userpic]
2004/04/21 17:33:21
SA is one of the standard guns-clubs-and-knives approaches for minimization on any significantly complex potential surface, anyway. It's used in my field too. The kind of problems it's good for are ones where you have lots of metastable (local) minima, with large barriers between them; so a function F(n1, n2.... nx) = E where you want the absolute minimum of Eo, but gradient-based techniques are going to pull you into one of the local minima E1 through En where Ex > Eo.

Anyway. (Yes, this is relevant to my PhD.)
reply | thread )

< | 5 glosses | comment | > )

Map Annealing - Squaring the circle...

> log in
> recent entries
> fiends
> archive
> toothywiki page
> profile
> new entry
> recent comments


> go to top