Skip to content
doubtly

2 answers

Best answer

A* search algorithm : 

  • It’s a variation of Best First search where the evaluation of a state or a node not only depends on the heuristic value of the node but also considers its distance from the start state.
  • It’s the most widely known form of best-first search.
  • In A* search, the value of a node n, represented as f(n) is a combination of g(n), which is the cost of heuristic estimation to reach to the node from the root node, and h(n), which is the cost of cheapest path to reach from the node to the goal node.
  • Hence f(n) = g(n) + h(n)
  • Advantages:
  • A* search algorithm is the best algorithm than other search algorithms. 
  • A* search algorithm is optimal and complete.
  • This algorithm can solve very complex problems.
  • Disadvantages:
  • It does not always produce the shortest path as it mostly based on heuristics and approximation. 
  • The main drawback of A* is memory requirement as it keeps all generated nodes in the memory, so it is not practical for various large-scale problems.
  • A* search algorithm has some complexity issues.
Anonymous · 27 Nov 2023 Report
Was this answer helpful?
  • Thank you so much for your answer you can register on this website – Doubtly ·
Sign in to comment

A* is a best-first search that expands the node with the smallest \(f(n) = g(n) + h(n)\), where \(g(n)\) is the actual cost from the start to \(n\) and \(h(n)\) is the heuristic (estimated) cost from \(n\) to the goal.

Algorithm

  1. Put the start node in the OPEN list with \(g = 0\), \(f = h(\text{start})\). CLOSED list is empty.
  2. If OPEN is empty, stop: no solution.
  3. Remove the node \(n\) with the lowest \(f\) from OPEN and put it in CLOSED.
  4. If \(n\) is the goal, stop and trace back the path.
  5. For each successor \(m\): compute \(g(m) = g(n) + \text{cost}(n,m)\) and \(f(m) = g(m) + h(m)\). If \(m\) is new, add it to OPEN; if it is already in OPEN/CLOSED with a higher \(g\), update it and its parent.
  6. Go to step 2.

Properties

  • Complete when branching factor is finite and step costs are positive.
  • Optimal if \(h\) is admissible (never overestimates the true cost); for graph search, \(h\) should also be consistent: \(h(n) \le c(n,m) + h(m)\).
  • Time and space are exponential in the worst case; the main drawback is memory, since all generated nodes are kept.

Special cases: if \(h(n) = 0\), A* becomes uniform-cost search; if \(g\) is ignored, it becomes greedy best-first search.

Example: in route finding, \(g(n)\) is the road distance travelled so far and \(h(n)\) is the straight-line distance to the destination, which never overestimates, so A* finds the shortest route.

Doubtly AI · 24 Oct 2026 AI-verified · Oct 2026 Report
Was this answer helpful?

Your answer

Log in or create a free account to answer this question.