I think it was 4.12.
That wasn't the only one on the assignment. I will post my whole HW thing here (should be safe, it was due Wed, and he doesn't give partial credit/late credit...) 4.2, 4.3, 4.11, and the question above, 4.12. His biggest thing is mostly about demonstrating an understanding, after I talked to him... that seemed to be his biggest thing, even if our numbers/answers aren't quite right... although there isn't much in the way of partial credit, so either you get it or you don't.
The heuristic path algorithm is a best-first search with the objective function: f(n)=(2-w)*g(n)+ w*h(n) For what values of w is this algorithm guaranteed to be optimal? What kind of search is performed for the following values for w?
w = 0 â†’ f(n)=2*g(n)
w = 1 â†’ f(n)=g(n)+ h(n)
w = 2 â†’ f(n)=2*h(n)
This algorithm will be found to be optimal for any values of w that make the h(n) portion of the function negligible if it is not already admissible. If it is overestimating the distance from the goal it would be made optimal for w = 0. This happens because w = 0 removes h(n) from the decision function removing the effect of overestimating the distance. This also makes it most like a uniform-cost search, which is optimal by its definition. For w = 1 it will also be optimal provided that h(n) is admissible. If h(n) is admissible it will also be optimal for w = 2 as it is going to choose the nodes who are closest to the goal and the factor of two out in front will not change the order they are expanded in.
For w = 0 :: f(n)=2*g(n)
This removes the â€œestimated distance from the goalâ€