Tip:
Highlight text to annotate it
X
So, we've looked at 2 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 way the opposite of breadth-first search.
In depth-first search, we always expand first the longest path,
the path with the most lengths in it.
Now, what I want to ask you to do is for each of these nodes in each of the trees,
tell us in what order they're expanded,
first, second, third, fourth, fifth and so on by putting a number into the box.
And if there are ties, put that number in and resolve the ties in left to right order.
Then I want you to ask one more question or answer one more question
which is are these searches optimal?
That is, are they guaranteed to find the best solution?
And for breadth-first search, optimal would mean finding the shortest path.
If you think it's guaranteed to find the shortest path, check here.
For cheapest first, it would mean finding the path with the lowest total path cost.
Check here if you think it's guaranteed to do that.
And we'll allow the assumption that all costs have to be positive.
And in depth first, cheapest or optimal would mean, again,
as in breadth first, finding the shortest possible path in terms of number of lengths.
Check here if you think depth first will always find that.