This is the first of a series of journal entries for my AI class, taught by Wheeler Ruml at UNH. Each entry is meant to be a retrospective of sorts about my reactions to the class, and to various interesting parts of artificial intelligence in general.
I was interested to learn about A*, a search algorithm which I had heard much about but never actually investigated. After reading a brief overview about in in Wikipedia, I became curious about some of the other state-space search algorithms that returned admissible results. Some digging around revealed B*, which seems quite similar to A* except for the fact that it uses intervals for each node in the search tree as opposed to single values. I would be curious to see if this is ever faster than A* for a common problem; obviously it must be faster for some cases, but which ones? It would be interesting to run both algorithms on a variety of sets of data to benchmark one versus the other.
I also discovered the Bellman-Ford algorithm, which piqued my interest when I noticed it solved a problem posed by Brad Larsen in class. Brad had noted that negative edge weights often played havoc with some of the algorithms we discussed, so I was pleased to notice the BF algorithm, which is a variant of Dijkstra's shortest-path algorithm which accounts for the possibility of negative edge weights. Instead of choosing the minimum edge weight path to expand, it expands all the paths and adjusts those that are negative until no negative edge weights remain. It seems a little counter-intuitive the way it is described here, and I wonder if it could be better explained. It seems to be used in some forms of routing in that all nodes in a network are constantly examining nodes they can reach, noting the shortest path, and propagating this information about the shortest path outward upon the network. Interesting stuff!
RSS Feed