UNINFORMED ALGORITHMS BEST FIRST SEARCH BREADTH FIRST SEARCH DEPTH FIRST SEARCH DIJKSTRA'S OR UNIFORM-COST SEARCH INFORMED ALGORITHMS GREEDY SEARCH A* Supposing we start from Marquette, what would cities would we visit first with Breadth-First Search Harvey, Negaunee, and Escanaba: One step away. From Harvey: SSM, and Marquette From Negaunee: Ishpeming, Iron Mountain, Marquette From Escanaba: Marquette, Iron Mountain, St Ignace So these are two steps away. And then we'd try the ones three steps away, four steps away, and so forth, until we get to Ann Arbor. We would store these cities in a queue. In Marquette, we'd add Harvey, Negaunee, Escanaba. Then we'd remove Harvey, add SSM, Marquette. Remove Negaunee, add Ishpeming, Iron Mountain, Marquette Remove Escanaba, add Marquette, Iron Mountain, St Ignance. And so forth, eventually we'd get to Ann Arbor. Plus side, you'll get there, even if there are a large number of states or even if there are an infinite number of states, you will get there. Down side: you might not find the best way to get there, and you may well visit and process the same state more than once. (You might to be able to pare this down if you track of the states you've previously visited, but this is not always feasible, especially if you have a large or infinite number of states.) Extremely crude way to do it. We're not even keeping track of what our distances are! Along the same lines, Depth-First Search. Marquette: Negaunee, Escanaba, Harvey In DFS, they go into a stack. Stack->Harvey->Escanaba->Negaunee Pop Harvey Stack->SSM->Escanaba->Negaunee In DFS, I'd better have some mechanism to not visit already visited states. DFS is an infinite loop just waiting to happen. Pop SSM Stack->St. Ig->Escanaba->Negauneee Pop St. IG Stack->Mackinac City->Escanaba->Negaunee And so forth and so on, until I get to Ann Arbor. Again, very crude, and you do have to some way of preventing infinite loops. Either in the form of keeping track of visiting states or some sort of depth limitation or something along those lines. Not making use of distances. Dijkstra You have an "evaluation function" and at every step you visit the node with the lowest evaluation function from where you are now. And to do this, you use a priority queue. A priority queue generalizes a stack and queue: you add an item with a certain priority and when you remove an item, the item with the lowest priority gets removed. For the evaluation function in this problem, we will take a look at "distance from Marquette" The next node you visit is on the "frontier" those nodes one step away from a node previously visited. Start with Marquette: PQ Harvey (5) Negaunee (10) Escanaba (50) I remove Harvey (5) and add SSM (80) Negaunee (10) Escanaba (50) SSM (80). In Uniform-Cost, you never add a previously node to the PQ. You have to keep track of visited nodes. Negaunee (10) : Add Iron Mountain (10+30) and Ishpeming (10+10) PQ: Ishpeming (20), Iron Mountain (40), Escanaba (50), SSM (80). Ishpeming (20): Add Houghton (20+40), Ironwood (20+60). PQ : Iron Mountain (40), Escanaba (50), Houghton (60) SSM (80), Ironwood (80). Iron Mountain (40): Escanaba (40+20) Escanaba is already in the PQ, but with a lower value, so we don't change it. If we were to readd Escanaba with a lower value than it already had, we would update Escanaba's value to the lower value. PQ: Escanaba (50), Houghton (60) SSM (80), Ironwood (80). And so forth, and so on. Eventually, we'd make it to Ann Arbor, and in the process, if we kept going. We'd find the best path not just to Ann Arbor but to every place else too. Unforunately, Dijkstra's algorithm looks for nearby stuff, not necessarily stuff that even in the direction you want to go. In AI, use of heuristics, precomputed components, and deprioritization of the "perfect answer" can help make AI algorithms run faster than their more theoretical counterparts. Heuristic: "guess" A heuristic is "problem dependent" and gives a guess as to where I ought to check next for a good solution. An algorithm that uses a heuristic is called an "informed" algorithm. An algorithm without a heuristic is an "uninformed" algorithm. In the problem we're looking at, going from Marquette to Ann Arbor, a good "heuristic" would be one that would estimate the distance to Ann Arbor from wherever we are now. I mean "estimate", meaning that we're not actually computing the true distance from analyzing the graph which would take too long. I mean estimate with a more easily computed function. So, looking at our map. We can estimate the distance between where we are and Ann Arbor by using the latitude and longitude of these locations and plugging them into the Great Circle formula. You may say this is ridiculous. The great circle formula between Ironwood and Ann Arbor takes you across Lake Michigan. That's not a great estimate at all, since you have to drive around Lake Michigan. Ideally, your estimate should NEVER overestimate the correct value. Greedy approach is to use a priority queue on the heuristic rather than on the evaluation function. So, starting from Marquette, I would add things to the PQ based on their estimated distance to Ann Arbor. PQ: Escanaba, Harvey, Negaunee. Pop Escanaba: St Ignace, Iron Mountain, Harvey, Negaunee. And so forth and so on, I'll eventually get to Ann Arbor, and perhaps the route I eventually take, won't be so bad. (Right now, it's taking me from Marquette->Escanaba->St Ignace, which isn't so bad.) But there's no guarantee that the route I find will be the best one. So, the algorithm that is often used in such situations is called A*. We run uniform-cost with this formula: eval(x)+heuristic(x). We start with the distance from Marquette to that node, and then add the estimated distance to Ann Arbor. As long as the estimate is NEVER an overestimate, A* is guaranteed not only to get there, but to find the best path there.