Neural Sync Active

⭐ Best First Search

Registry Synced

⭐ Best First Search

1134 words

6 min read

Reading compass

Now · 1. 🎯 Learning Objectives

⭐ Best First Search

1. 🎯 Learning Objectives

By the end of this topic, you will be able to:

Trace Best First Search using heuristic function h(N) with full OPEN/CLOSED tables
Define heuristic functions: Hamming distance, Manhattan distance for 8-puzzle
Explain why Best First Search does NOT guarantee optimality
Compare Best First Search to BFS and DFS
Design a heuristic function for a given problem

2. 📋 Prerequisites

Prerequisite	Course	Why It Matters
State spaces	W2 T1	Where heuristics guide search
BFS/DFS	W2 T2-4	Comparison with heuristic search
Priority queues	BSCS2002	Data structure for Best First

3. 📖 Core Content

3.1 Intuition: Using Domain Knowledge

Blind search (BFS, DFS, DFID) treats all states equally — it only knows whether a state is the goal or not. Heuristic search uses domain knowledge to estimate which states are more promising. Best First Search uses a heuristic function

h(N)

that estimates the distance from node N to the goal. It uses a priority queue for OPEN, ordered by

h(N)

, and always expands the node with the lowest h-value (the one that "looks closest" to the goal).

3.2 Heuristic Functions

A heuristic function

h(N)

estimates the cost from node N to the goal state. Example: 8-Puzzle Heuristics Hamming Distance (also called "tiles out of place"): Count of tiles not in their goal positions (excluding the blank). Goal state: [1, 2, 3], [8, 0, 4], [7, 6, 5] Current state: [2, 8, 3], [1, 6, 4], [7, 0, 5]

Position	Goal	Current	Same?
(0,0)	1	2	No
(0,1)	2	8	No
(0,2)	3	3	Yes
(1,0)	8	1	No
(1,1)	0	6	No
(1,2)	4	4	Yes
(2,0)	7	7	Yes
(2,1)	6	0	No
(2,2)	5	5	Yes

Hamming = 5 (5 tiles out of place). Note: we usually don't count the blank, so it's 4. Manhattan Distance: Sum of horizontal + vertical distances from each tile's current position to its goal position. For the same state:

Tile 1: at (1,0), goal (0,0) → |1-0| + |0-0| = 1
Tile 2: at (0,0), goal (0,1) → |0-0| + |0-1| = 1
Tile 3: at (0,2), goal (0,2) → 0
Tile 4: at (1,2), goal (1,2) → 0
Tile 5: at (2,2), goal (2,2) → 0
Tile 6: at (1,1), goal (2,1) → |1-2| + |1-1| = 1
Tile 7: at (2,0), goal (2,0) → 0
Tile 8: at (0,1), goal (1,0) → |0-1| + |1-0| = 2 Total Manhattan = 1+1+0+0+0+1+0+2 = 5

3.3 Best First Search Algorithm


text
BestFirstSearch(initial_state, goal_test, move_gen, heuristic):
    OPEN = priority_queue()  // Ordered by h(N), smallest first
    OPEN.add(initial_state, h(initial_state))
    CLOSED = {}
    nodePairs = {}
    while OPEN is not empty:
        N = OPEN.extract_min()  // Node with smallest h(N)
        CLOSED.add(N)
        if goal_test(N):
            return reconstruct_path(N, nodePairs)
        for child in move_gen(N):
            if child not in OPEN and child not in CLOSED:
                priority = h(child)
                OPEN.add(child, priority)
                nodePairs[child] = N
    return NO_SOLUTION

3.4 Worked Example: Best First Search Trace

Consider route-finding with straight-line distance heuristic: (Diagram) Heuristic h(N) = straight-line distance to goal F: h(A)=8, h(B)=6, h(C)=5, h(D)=4, h(E)=2, h(F)=0

Step	OPEN (h)	CLOSED	N	Successors	Notes
0	{A(8)}	{}	—	—	Start
1	{}	{A}	A(8)	B(6), C(5)	Add B, C
2	{B(6), C(5)}	{A}	C(5)	D(4)	C has lower h, expand first
3	{B(6), D(4)}	{A, C}	D(4)	E(2)	D has lowest h
4	{B(6), E(2)}	{A, C, D}	E(2)	F(0)	E has lowest h
5	{B(6), F(0)}	{A, C, D, E}	F(0)	—	Goal!

Path found: A-C-D-E-F (length 4) Nodes inspected: A, C, D, E, F Note: Best First Search found a path, but was it optimal? In this case, the path length = 4 edges. But could there be a shorter path? A-B-D-E-F is also 4 edges. What if there were a direct edge A-F? Best First might have missed it because it greedily followed the best heuristic.

3.5 Properties of Best First Search

Property	Value
Time complexity	$O(b^d)$ — worst case same as blind
Space complexity	$O(b^d)$ — stores all generated nodes
Complete?	Yes (with CLOSED, finite spaces)
Optimal?	No — greedy, can miss optimal
OPEN structure	Priority queue (by h(N))

3.6 Why Best First Is Not Optimal

Best First Search is greedy — it always expands the node that looks closest to the goal according to h(N). This can lead to suboptimal solutions: Example: In the graph above, if there were a direct path A-C-D-E-F (heuristic guidance) but the actual costs were such that A-B-D-F was cheaper, Best First might still find the longer path first. Best First Search does not consider the cost already incurred. It only looks forward. This is why A* (which combines g(N) + h(N)) is needed for optimality.

3.7 Heuristic Comparison Table

Heuristic	Definition	Admissible?	Dominates?
Hamming	Count of misplaced tiles	Yes	No
Manhattan	Sum of horizontal+vertical distances	Yes	Dominates Hamming

A heuristic

h_1

dominates

h_2

h_1(N) \geq h_2(N)

for all nodes N (and both are admissible). Dominating heuristics are better — they prune more nodes. Fact: Manhattan dominates Hamming for the 8-puzzle because every misplaced tile has at least Manhattan distance 1, so Manhattan ≥ Hamming for all states.

4. 📐 Key Formulas / Concepts

Concept	Definition
Heuristic h(N)	Estimated distance from N to goal
Hamming distance	Count of misplaced tiles
Manhattan distance	Sum of
Best First	Expand node with smallest h(N)
Priority queue	OPEN ordered by h(N)

5. ⚠️ Common Pitfalls

Pitfall 1: Confusing Best First with A*

The mistake: Thinking Best First finds optimal solutions. Correct approach: Best First uses only h(N). A* uses g(N)+h(N). Only A* guarantees optimality with admissible heuristics.

Pitfall 2: Using a Non-Informative Heuristic

The mistake: Using h(N)=0 for all nodes — Best First becomes BFS. Correct approach: A good heuristic is informative — it should distinguish between promising and unpromising states.

Pitfall 3: Confusing Hamming with Manhattan

The mistake: Computing Manhattan as just the count of misplaced tiles. Correct approach: Hamming = count of wrong positions. Manhattan = sum of distances each tile must travel.

6. 📝 Practice Questions

Q1: Compute Hamming and Manhattan for 8-puzzle state [3, 7, 2][6, 4, 1][5, 8, 0] with goal [1,2,3][8,0,4][7,6,5]

Answer: Hamming: count tiles not in goal position. Goal mapping: 1->(0,0), 2->(0,1), 3->(0,2), 8->(1,0), 0->(1,1), 4->(1,2), 7->(2,0), 6->(2,1), 5->(2,2). Compare: 3 at (0,0) ≠ goal (0,2); 7 at (0,1) ≠ goal (2,0); 2 at (0,2) ≠ goal (0,1); 6 at (1,0) ≠ goal (2,1); 4 at (1,1) ≠ goal (1,2); 1 at (1,2) ≠ goal (0,0); 5 at (2,0) ≠ goal (2,2); 8 at (2,1) ≠ goal (1,0); 0 at (2,2) ≠ goal (1,1). All 8 tiles misplaced → Hamming = 8. Manhattan = sum of distances... (compute: |0-0|+|0-2|=2 for tile 1, etc.) ≈ 12. Q2: Why does Best First Search not guarantee optimality?

Answer: Best First Search only considers the estimated remaining cost h(N), not the actual cost incurred so far (g(N)). A node that "looks close" to the goal according to h(N) might be on a very long path when considering actual costs already incurred. Q3: What is a dominating heuristic and why is it better?

Answer: Heuristic h1 dominates h2 if h1(N) ≥ h2(N) for all nodes N and both are admissible. A dominating heuristic provides more pruning because it gives a more accurate (higher) estimate of remaining cost, reducing the search space. Join Discord PreviousDFID (Iterative Deepening)NextHeuristic Design