Best-First Search (BFS) (not to be confused with Breadth-First Search) is an informed search algorithm that uses a heuristic function h(n) to decide which node to explore next.

• It always expands the node that looks closest to the goal,
  i.e. the one with the lowest heuristic value (h).
• The smaller the value of h(n), the closer the algorithm believes that node is to the goal.
• It does not consider the cost of the path so far (that’s what A* does).

Algorithm: Best-First Search

1.  Let OPEN be a priority queue (min-heap) containing the start node.

    (OPEN is sorted by heuristic value h.)

2.  Repeat until goal is found or OPEN becomes empty:   

    a.  If OPEN is empty → return FAIL.

    b.  Remove the first node (with smallest h value) from OPEN → call it NODE.

    c.  If NODE is the goal →

            return the path from start to NODE (SUCCESS).

    d.  Else:

            i.   Generate all successors of NODE.

            ii.  Calculate their heuristic values h(n).

            iii. Insert each successor into OPEN according to increasing h.

1. End Loop.

To understand

(Step 1:

Let OPEN be a priority queue that initially contains only the start node.

(OPEN stores all generated nodes that have not yet been expanded.)

---

Step 2:

Repeat until the goal is found or OPEN becomes empty:

1️⃣ If OPEN is empty, return FAIL —
(No solution found).

2️⃣ Remove the first node from OPEN (the one with the lowest heuristic value h(n)).

3️⃣ If this node is the goal node,
return the path from start to goal (SUCCESS).

4️⃣ Otherwise,

• Generate all successor nodes (children).
• Compute their heuristic values (h).
• Insert them into the OPEN queue according to their h values (sorted in increasing order — smallest first).

🌀 Repeat the loop.

)

Formula used:

Evaluation function

f(n)= h(n)

The algorithm selects the node with the smallest h(n) to expand next.

        A (h=7)

       /     |      \

   B(5)     C(6)     D(1)

   / \                       / \

 G(6) H(5)       E(4)   F(6)

                         / \

                    I(10)  J(0)

⚙️ Concept of OPEN Queue (Priority Queue)

In Best-First Search, we maintain a list called the OPEN list
(or Priority Queue).

• It stores all the nodes that have been generated but not yet expanded.
• The node with the smallest heuristic value (h) gets the highest priority —
  it is expanded next.

We also have a CLOSED list (not shown here) which stores already expanded nodes.

---

🪜 Step-by-Step Expansion

Step 1: Start from A

OPEN list initially:
[A]

Expand A → add its children B, C, D to the OPEN list.

Node	h(n)
B	5
C	6
D	1

✅ Choose node with smallest h → D (h=1)

So now D is expanded next.

---

Step 2: Expand D

Children of D → E (h=4) and F (h=6)

Now OPEN list becomes:
[B(5), C(6), E(4), F(6)]

✅ Pick the node with smallest h → E (h=4)

---

Step 3: Expand E

Children of E → I (h=10) and J (h=0) (Goal)

Add these to the OPEN list.

Now OPEN list:
[B(5), C(6), F(6), I(10), J(0)]

✅ Node with smallest h → J (h=0)

Since J is the Goal Node, the algorithm stops here.

---

Step 4: Goal Found

The goal J is reached through the path:

A → D → E → J

✅ Best path found using Best-First Search

---

OPEN Queue Evolution (as shown in your image)

Let’s list the OPEN queue after each step (from the diagram):

Step	Action	OPEN Queue (after adding children)	Node Picked Next
1	Start at A	[B(5), C(6), D(1)]	D
2	Expand D	[B(5), C(6), E(4), F(6)]	E
3	Expand E	[B(5), C(6), F(6), I(10), J(0)]	J
4	Expand J	Goal found → stop	—

---

“In Best-First Search, we use a priority queue that always picks the node with the lowest heuristic value — because that node looks closest to the goal.

Starting from A, we add B, C, D. D has the smallest h, so we pick D first.
From D, we add E and F. E looks better (h=4), so we pick E.
From E, we add I and J. J has h=0, which means it’s the goal — so the search stops.

That’s how the algorithm reaches the goal efficiently, without exploring unnecessary nodes.”

---

 Key Takeaways

Feature	Description
Evaluation Function	f(n) = h(n)
Type	Informed Search
Data Structure	Priority Queue (sorted by h)
Strategy	Choose the node that looks closest to the goal
Optimal?	Not always
Example Path	A → D → E → J

---

Analogy

“Think of Best-First Search like finding your way in a foggy city using signboards —
you always follow the sign that says ‘Shortest distance to destination’.
You might not always get the best path, but you usually reach fast.”