If the heuristic function h is consistent, then A* search with f(n) = g(n) + h(n)...

 

Transcribed Image Text:

If the heuristic function h is consistent, then A* search with f(n) = g(n) + h(n) is optimal. Hint: Let's say, for a node n, the shortest path to the goal is through a successor called m. Since, the heuristic is consistent, h(n) <h(m)+c(m, n). Since, d(n) = d(m)+c(m, n) and for induction, assuming that, h(m) < d(m), we find that, h(n) <h(m) + c(m, n) < d(m) + c(m, n) = d(n). If the heuristic function h is consistent, then A* search with f(n) = g(n) + h(n) is optimal. Hint: Let's say, for a node n, the shortest path to the goal is through a successor called m. Since, the heuristic is consistent, h(n) <h(m)+c(m, n). Since, d(n) = d(m)+c(m, n) and for induction, assuming that, h(m) < d(m), we find that, h(n) <h(m) + c(m, n) < d(m) + c(m, n) = d(n).