edited by
2,098 views
0 votes
0 votes

​​​​​​​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 :

$Code:$

  1. Neither of the statements S1 and S2 are true
  2. Statement S1 is false but statement S2 is true
  3. Statement S1 is true but statement S2 is false
  4. Both the statements S1 and S2 are true
edited by

1 Answer

0 votes
0 votes

A heuristic function is said to be admissible if it never overestimates the cost of reaching the goal, i.e. the cost it estimates to reach the goal is not higher than the lowest possible cost from the current point in the path.

S1 is TRUE.

It's necessary and sufficient for a heuristic to obey the triangle inequalit in order to be consistent or monotone. The triangle inequality states that for any triangle, the sum of the lengths of any two sides must be greater than or equal to the length of the remaining side. A heuristic function is said to be consistent, or monotone, if its estimate is always less than or equal to the estimated distance from any neighboring vertex to the goal, plus the cost of reaching that neighbor.

S2 is TRUE.

D is correct.

 

 

Related questions

1 votes
1 votes
0 answers
3
0 votes
0 votes
2 answers
4
Arjun asked Jan 2, 2019
4,327 views
Consider the graph shown below:Use Kruskal’s algorithm to find the minimum spanning tree of the graph. The weight of this minimum spanning tree is$17$$14$$16$$13$