Consider the following statements : S1: A heuristic is admissible if it never…
2018
Consider the following statements :
S1: A heuristic is admissible if it never overestimates the cost to reach the goal.
S2: A heuristic is monotonous if it follows triangle inequality property.
Which of the following is true referencing the above statements ?
Choose the correct answer from the code given below :
𝐶𝑜𝑑𝑒:
- A.
Neither of the statements S1 and S2 are true
- B.
Statement S1 is false but statement S2 is true
- C.
Statement S1 is true but statement S2 is false
- D.
Both the statements S1 and S2 are true
Attempted by 102 students.
Show answer & explanation
Correct answer: D
Answer: Both statements are true.
Admissible heuristic: A heuristic is admissible if for every node it never overestimates the true cost to reach the goal (formally, for all nodes n, h(n) ≤ true cost from n to goal).
Monotone (consistent) heuristic: A heuristic is monotone if it satisfies the triangle inequality: for every node n and every successor n' reachable with step cost c(n,n'), h(n) ≤ c(n,n') + h(n'). Also h(goal) = 0.
Relation between them: Monotonicity implies admissibility. If the triangle inequality holds along any path to the goal, repeated application shows h at a node is at most the total path cost to the goal, so the heuristic does not overestimate.
Proof sketch that monotone implies admissible:
Consider an optimal path from node n to the goal through successors n = n0, n1, ..., nk = goal.
Apply the monotonicity inequality at each step: h(ni) ≤ c(ni,ni+1) + h(ni+1).
Summing these inequalities telescopes to h(n) ≤ sum of step costs + h(goal). Since h(goal)=0, h(n) ≤ true cost from n to goal, so the heuristic is admissible.
Therefore both statements are true: S1 correctly states admissibility and S2 correctly states monotonicity (triangle inequality).
A video solution is available for this question — log in and enroll to watch it.