# UGCNET-Dec2014-III: 56

1.1k 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

1 vote

Ans. (B)

Explanation

Option (A) defines Hill climbing search

Option (B) defines A* search

Option (C) defines Branch and Bound search

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.

Option B is correct

## Related questions

1
939 views
Match the following learning modes $w.r.t$. characteristics of available information for learning : a. Supervised i. Instructive information on desired responses, explicitly specified by a teacher. b. Recording ii. A priori design information for memory storing c. Reinforcement iii. Partial information ... about desired responses Codes : a b c d i ii iii iv i iii ii iv ii iv iii i ii iii iv i
1 vote
A ________ point of a fuzzy set $A$ is a point $x \in X$ at which $\mu_{A} (x) = 0.5$ Core Support Crossover $\alpha​$-cut