(A) is like a depth-first search
where most promising child is selected for expansion
(B) 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.
(C) saves all path lengths (costs)
from start node to all generated nodes and chooses shortest path for further
expansion.
(D) none of the above
Answer 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.
ReplyDeleteAt 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
f(n)=g(n)+h(n)
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.
This comment has been removed by the author.
ReplyDelete