1. Here is a graph of some cities of Europe. Suppose that we are searching for an optimal path from Prague to Zagreb.
Consider a breadth-first graph search, ignoring path costs. How many cities will we visit in the search?
Consider a uniform-cost graph search. What is the smallest and largest number of cities we might visit in the search?
2. True or false? In a uniform-cost graph search,
Nodes are expanded in order of their optimal path cost.
At any moment, the optimal path cost of every unexplored node is greater than the optimal path cost of every frontier node.
At any moment, the optimal path cost of every frontier node is greater than the optimal path cost of every explored node.
At any moment, the estimated path cost of at least one frontier node is actually optimal.
If all edges have the same step cost, then the uniform-cost search runs as quickly as a breadth-first search and achieves the same result.
3. Show that uniform-cost search is not complete unless step costs are bounded below by some value ε.
