PSet 3: informed search

(videos up to and including A*)

1. In the graph below, run Greedy search from Zerind to Bucharest. When vertices are removed from Open, break ties in alphabetical order. Show the order vertices were assigned to the current state s, and how the priority queue evolved in the same manner I have in the lectures. Label the nodes with their h-costs. What was the total cost of the path you find? is it optimal?

2. In the graph below, run A* search from Zerind to Bucharest. When vertices are removed from Open, break ties in alphabetical order. Show the order vertices were assigned to the current state s, and how the priority queue evolved in the same manner I have in the lectures. Label the nodes with their f-costs. What was the total cost of the path you find? is it optimal?

   

Challenge Problems¶

3. In the lecture, I defined monotonicity as a property of a heuristic where if $n$ is an ancester of $n'$, $f(n) \leq f(n')$. Another way to talk about the same thing is with a property called consistency, where for every node $n$ and every adjacent successor $n'$ generated by an action $a$, $h(n) \leq c(n,a,n') + h(n')$, and $h(goal)=0.$ In english, $h(n)$ is less than or equal to the cost of going from $n$ to $n'$ by taking action $a$, plus $h(n')$.

   Show that consistency implies monotonicity. That is, if a heuristic is consistent, it must be monotonic.

4. Show that consistency implies admissibility. That is if a heuristic is consistent, it must be admissible.