The Gateway to Computer Science Excellence
+2 votes
671 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 by Boss (30.2k points)
retagged by | 671 views

3 Answers

+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)
0 votes

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

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.

by Boss (48.8k points)
0 votes
Option B is correct
by (319 points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,647 questions
56,492 answers
195,462 comments
100,763 users