This is the fifth entry in my ongoing series of journal entries concerning stuff I find interesting in AI. This entry will consider a thought I had about a possible final project.
More often than not, I find that programming geeks are somewhat obsessed with optimization even before they have any interest in programming. When I was younger, I used to play with Lego before all other toys. After I built my contraptions, I always wondered if I could do it with fewer pieces. The point of this little aside is that programmers are often thinking about the fewest pieces, the lowest time, and especially the shortest path.
While wandering around campus with my friend Brad (usually just heading from the MUB to Kingsbury, or vice versa), we often consider whether the path we are taking is the fastest. This is not just idle speculative chatter; we are both usually pretty cold and wish to get to our destination as soon as possible. Suddenly at the end of class on Thursday, an idea dawned on me: why not implement a route-planner to figure out the fastest route from one location on campus to another?
The idea is quite straightforward. Use Dijkstra's shortest path algorithm to find the best way to get from place to place. The sidewalks could be edges, and buildings and sidewalk crossings could be nodes. Edge weights would be proportional to distances between sidewalk crossings and buildings in real life. The most interesting part might be a “Winter” mode, where special emphasis is put on paths that cross through mostly buildings as opposed to sidewalks. Both Brad and I were constantly ducking through Hamilton Smith on our way along Main St.
The only issue for this idea: is this too easy? Dijkstra's shortest path algorithm isn't all that hard to implement. Maybe more of a challenge would be a multi-stage algorithm, for multi-part trips? That way it would be possible to simulate a whole day on campus. Or possibly a program that analyzes a set of various possible days, and generates a set of rules that could guide a program deciding which paths to take on the fly. This idea greatly appeals to that Lego maniac I used to be. Build it with fewer pieces!
RSS Feed