3-2. Uninformed Search

Now, why doesn’t the general tree search or graph search algorithm stop when it adds a goal node to the Frontier? The reason is because it might not be the best path to the goal. Now here we found a path of length 2. And we added a path of length 3 that reached the … Read more

The answer is that we add one more path, the path to Bucharest. We don’t add the path going back because it’s in the explored list, but we don’t terminate yet. True, we have added a path that ends in Bucharest but the goal test isn’t applied when we add a path to the Frontier. … Read more

So we move on. We look for another shortest path. There’s one path left of length one, so we look at that path, we expand it. Add in this path, put that one on the explored list. And now we’ve got three paths of length two. We choose one of them. And let’s say we … Read more

In this case, there’s nothing to add, because of the two neighbors, one is in the explored list, and one’s in the frontier. And if we’re using graph search, then we won’t add either of those.

And the answer is that breadth first search always considers the shortest path first. And this case there’s two path of length 1. The path from Arad to Zerind and Arad to Timisoara. So those would be the two paths that would be considered. Now, let supposed that the tight broken someway and we choose … Read more

Now we see how to modify the tree search function and make it be a graph search function to avoid those repeated paths. What we do is we start off and initialize the set, called the explored set, of states that we’ve already explored. Then, when we consider a new path, we add the new … Read more

The answer is that in Sibiu, the action function gives us four actions corresponding to traveling along these four roads. So we have to add in paths for each of those actions. One of those paths goes here. The other path continues from Arad and goes out here. The third path continues out here. And … Read more

Now let’s define a function for solving problems. It’s called Tree.Search because it superimposes a search tree over the state space. Here’s how it works. Starts off by initializing the frontier to be the path which consisting of only the initial state. And then it goes into a loop in which it first check, see, … Read more

The answer is that breadth first search is complete, so even if the tree is infinite, if the goal is placed at any finite level, eventually we’re going to march down and find that goal. Same with cheapest first. No matter where the goal is, if it has a finite cost, eventually we’re going to … Read more

Given the non-optimality of depth-first search, why would anybody choose to use it? Well, the answer has to do with the storage requirements. Here I’ve illustrated a state space consisting of a very large, or even infinite, binary tree. As we go to level one, two, three down to level n, the tree gets larger … Read more

Here are the answers. Breadth-first search, as the name implies, expands nodes in this order, 1, 2, 3, 4, 5, 6, 7. So it’s going across a stripe at a time, breadth first. Is it optimal? Well, it’s always expanding the shortest paths first. And so wherever the goal is hiding, it’s going to find … Read more

We’ve looked at two search algorithms, one Breadth-First search, in which we always expand first the shallowest paths, the shortest paths. Second, Cheapest-First search, in which we always expand first the path with the lowest total cost. And I’m going to take this opportunity to introduce a third algorithm, Depth-First search, which is in a … Read more

An algorithm that has traditionally been called Uniform Cost Search, but could be called Cheapest First Search, is guaranteed to find the path with the cheapest total cost. Let’s see how it works. We start out as before in the start state, and we pop that empty path off. Move it from frontier to explored, … Read more

Now let’s see how the definition of a problem maps on to the route founding domain. First, the initial state we’re given, let’s say, we start off in Arad. And the goal test, let’s say, that the state of being in Bucharest is the only state that counts as a goal. And all other states … Read more