Informed and Heuristic Search Questions and Answers

101.

A* algorithm is guaranteed to find an optimal solution if

A.h' is always 0.
B.g is always 1.
C.h' never overestimates h.
D.h' never underestimates h.

Exam Year(s)

UGC NET - 2012,

Answer: C

The A* algorithm is guaranteed to find an optimal solution if the heuristic h' never overestimates the true cost h to reach the goal, which is called an admissible heuristic. If h' were always 0, the search would become uniform cost search, which is also optimal but is not the condition stated in general, and g always 1 would make the cost of every step the same. A heuristic that never underestimates would be too large and could miss the best path. The keyed answer is that h' never overestimates h.

Discuss in Forum

102.

A* algorithm uses f ' = g + h' to estimate the cost of getting from the initial state to the goal state, where g is a measure of the cost of getting from initial state to the current node and the function h' is an estimate of the cost of getting from the current node to the goal state. To find a path involving the fewest number of steps, we should set

A.g = 1
B.g = 0
C.h' = 0
D.h' = 1

Exam Year(s)

UGC NET - 2012,

Answer: A

In A* the estimate f is the sum of g, the cost from the start to the current node, and h', the estimated cost from the node to the goal. If every step costs the same and g counts the steps, so that g = 1 for each step, the search finds the path with the fewest steps. Setting g = 0 would ignore the cost already paid, which makes the search greedy, and setting h' = 0 would discard the estimate, so it is the cost per step that must be one. The answer is g = 1, option (A).

Discuss in Forum

103.

If h* represents an estimate of the cost of getting from the current node N to the goal node and h represents actual cost of getting from the current node to the goal node, then A* algorithm gives an optimal solution if

A.h* is equal to h
B.h* overestimates h
C.h* underestimates h
D.none of these

Exam Year(s)

UGC NET - 2013,

Answer: C

A* gives an optimal solution when the estimate h* underestimates h, that is, when it never exceeds the actual cost to the goal. Such a heuristic is called admissible, and A* with an admissible heuristic is guaranteed to find a cheapest path.

If h* equals h the search is perfectly informed, which is a special case rather than the general condition. If h* overestimates h, A* may skip the optimal path, so it can return a non-optimal solution.

Discuss in Forum

104.

Which one of the following is not an informed search technique ?

A.Hill climbing search
B.Best first search
C.A* search
D.Depth first search

Exam Year(s)

UGC NET - 2013,

Answer: D

Depth first search is not an informed search technique. It expands the deepest node without any knowledge of how close a node is to the goal, so it is a blind (uninformed) search. The answer is (D).

Hill climbing, best first search and A* search all use heuristic information about the goal: hill climbing moves to a better neighbour, best first search expands the most promising node, and A* uses the cost so far plus the estimated cost to the goal. So (A), (B) and (C) are informed.

Discuss in Forum

Loading…

Topics

Other Subjects

Tags: Informed and Heuristic Search Questions and Answers || Informed and Heuristic Search MCQ Questions and Answers || Informed and Heuristic Search GK Questions and Answers || Informed and Heuristic Search GK MCQ Questions || Informed and Heuristic Search Multiple Choice Questions and Answers || Informed and Heuristic Search GK || GK on Informed and Heuristic Search || Artificial Intelligence Questions and Answers || Artificial Intelligence MCQ Questions and Answers || Artificial Intelligence GK Questions and Answers || GK on Artificial Intelligence

Informed and Heuristic Search Questions and Answers

Topics

Other Subjects

About Us

Stay informed about all important Dates & Notifications