Assume that you have two heuristic functions for a specific problem h1, h2. Prov
ID: 3843748 • Letter: A
Question
Assume that you have two heuristic functions for a specific problem h1, h2. Provide formal arguments to answer the following questions.
a. If you use the minimum value of h1(n) and h2(n) at every state, will the resulting heuristic be admissible? Is it a consistent one?
b. If you use the maximum value of h1(n) and h2(n) at every state, will the resulting heuristic be admissible? Is it a consistent one?
c. If you define the heuristic function h3(n) = · h1(n) + (1 ) · h2(n), where 0 1, will this be admissible? Will it be consistent?
d. Consider an informed, best-first search algorithm in which the objective function is ƒ (n) = (2 ) · g(n) + · h(n). For what values of is this algorithm guaranteed to be optimal when h is admissible (for the case of TREE-SEARCH)? What kind of search does the resulting algorithm perform when = 0? When = 1? When = 2?
Explanation / Answer
In general definition from the text book we say,
Consistent: if the estimated cost from node to the goal is no greater than the step cost to its descendant n plus the predictable cost from the successor to the goal.
Admissible if h(n) never overestimates the true cost to the goal state.
Let we have two heurisitics functions for a specific problem h1 and h2,
a)
If we use the minimum value of h1(n) and h2(n) at every state,
h3(n) = minimum( h1(n) , h2(n) ) is admissible, since given that h1(n) leqslant h*(n)
is always true that min( h1(n) , infty ) leqslant h*(n)
b)
If we use the maximum value of h1(n) and h2(n) at every state,
h4(n) = maximum( h1(n) , h2(n) ) is admissible, since given that h1(n) leqslant h*(n) and h2(n) leqslant h*(n) we deduce that max( h1(n) , h2(n) ) leqslant h*(n) .
c)
For the heuristic function h3(n) = w. h1(n) + (1-w) h2(n) , where 0 leqslant w leqslant 1,
With w = 0, there is a uniform cost for the algorithm, which is guaranteed to find an optimal solution. So it is admissible.
With w =0.5, the algorithm is A* where h admissible so it is guaranteed to find an optimal solution.
But with w>0.5, we are multiplying h1(n) by a factor larger than used for h2(n). So this is not admissible.
d)
For the objective function, f(n) = (2-w) g(n) + w h(n),
The algorithm is to be guaranteed for 0<= w <=1 , since multiplied by a constant in g(n) implies no effect on the relative ordering of chosen paths, but if w>1 then possibly it may overestimates the distance to a goal, and heuristics made to be inadmissible. If w <=1 the estimate reduces and is guaranteed to underestimate the distance to a goal/
For the above function,
When w =0; it gives f(n) = 2 g(n) is exactly behaves like Uniformed Cost search or Uninformed Best first search states that the factor of 2 makes no difference in the ordering of the nodes.
When w = 1; it gives f(n) = g(n) + h(n) is A* search and guaranteed to find an optimal solution.
When w =2; it gives f(n) = 2 h(n) is Greedy Best first search.