687 views

An $A^{*}$ algorithm is a heuristic search technique which

1. Is like a depth-first search where most promising child is selected for expansion
2. Generates all successor nodes and computes an estimate of distance (cost) from start node to a goal node through each of the successors. It then chooses the successor with shortest cost.
3. Saves all path lengths (costs) from start node to all generated nodes and chooses shortest path for further expansion.
4. None of the above
in Others
retagged | 687 views

+1 vote

Ans. (B)

Explanation

Option (A) defines Hill climbing search

Option (B) defines A* search

Option (C) defines Branch and Bound search

by (61 points)

ans is B

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 specificnode 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.

At each iteration of its main loop, A* needs to determine which of its partial paths to expand into one or more longer paths. It does so based on an estimate of the cost (total weight) still to go to the goal node. Specifically, A* selects the path that minimizes

where n is the last node on the path, g(n) is the cost of the path from the start node to n, and h(n) is a heuristic that estimates the cost of the cheapest path from n to the goal. The heuristic is problem-specific. For the algorithm to find the actual shortest path, the heuristic function must be admissible, meaning that it never overestimates the actual cost to get to the nearest goal node.

by Boss (49.3k points)
Option B is correct
by (319 points)