UGC NET CSE | December 2012 | Part 3 | Question: 74

Question

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

Answer 1

Answer : h’ never overestimates h

A*  is a computer algorithm that is widely used in path-finding and graph traversal.

Description : A* is an informed search algorithm, or a best-first search, meaning that it solves problems by searching among all possible paths to the solution (goal) for the one that incurs the smallest cost (least distance travelled, shortest time, etc.), and among these paths it first considers the ones that appear to lead most quickly to the solution. It is formulated in terms of weighted graphs, starting from a specific node of a graph, it constructs a tree of paths starting from that node, expanding paths one step at a time, until one of its paths ends at the predetermined goal node.

Reference of Above Description is Wikipedia

Reference : Introduction to A*

Comments

Can you please explain what is h'?

I understand from wiki page that A* Algorithm minimizes the function

f(n)= g(n)+h(n)

where n is the last node in the path

g(n) is length of path from start node to n

and h(n) is an estimate of cheapest path from n to goal