5 – Breath First Search 1

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

3 – Tree Search Continued

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

2 – Tree Search

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

19 – Search Comparison 3

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

18 – Search Comparison 2

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

17 – Search Comparison 1

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

16 – Search Comparison

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

10 – Uniform Cost Search

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