---

tags:

• 🌱
• AI
• ComputerScience
• Search date: 18--Apr--2023

---

Also known as best-first search.

• Makes use of Heuristic function = h(n)
  • estimated cost from node to goal

• Complete
  • No. The algorithm takes the least cost path from all nodes in the frontier (similar to Breadth first search). For some infinite state space, the algorithm can be trapped in a loop and not recover.
• Optimal
  • If an algorithm is not complete, optimality cannot be guaranteed.
• Time
  • Worse case is when all nodes needs to be expanded
  • O(b^d)
• Space
  • All nodes in the frontier must be stored in the queue
  • O(b^d)

---

Links: