Informed Search Strategies

Heuristic-Based Search Algorithms

CSET-381 | Lecture 3.4 | Artificial Intelligence

❌ Problem with Uninformed Search

Blind Search Issues:

🔍 BFS: Explores ALL paths
S → [A, B, C, D, E, F, G...]

📊 DFS: No direction guidance
S → A → X → Y → Z → DEAD END
Backtrack → Try B → ...

🔄 IDS: Repeated blind exploration
Depth 1: [A, B, C]
Depth 2: [A, B, C] + children

Result: Inefficient exploration!

Key Issues:

Searches in ALL directions equally
No knowledge about goal location
Wastes time on unpromising paths
Cannot prioritize better moves
Treats all nodes as equally likely
No way to "guide" the search

💡 Solution Needed: Add intelligence to guide search toward the goal!

✅ Solution: Informed Search

🚫

Uninformed Search

Problems:
• Travels ALL possible paths
• No guidance about direction
• Searches blindly in space
• Inefficient resource usage

Examples: BFS, DFS, IDS

🎯

Informed Search

Solutions:
• Adds intuition/logic to search
• Uses heuristic information
• Guides search toward goal
• Avoids unpromising paths

Key: Still may need backtracking if heuristic is wrong!

                    🧠 Core Concept: Add domain knowledge (heuristics) to make intelligent decisions about which path to explore next.
                

📊 Heuristic Functions

Three key functions needed for informed search:

🎯 f(n) - Evaluation Function

f(n) = g(n) + h(n)

Purpose: Determines which node to expand next

Logic: Combines actual cost with estimated cost

Used in: A* Search algorithm

📏 g(n) - Actual Cost

g(n) = cost from start to n

Purpose: Tracks the actual path cost so far

Logic: Known, exact distance traveled

Example: Steps taken, distance moved

🔮 h(n) - Heuristic Function

h(n) = estimated cost to goal

Purpose: Estimates remaining cost to goal

Logic: Domain-specific knowledge

Example: Straight-line distance, Manhattan distance

                    🎲 Key Insight: The heuristic h(n) guides the search - better heuristics lead to more efficient search!
                

🏆 Best-First Search

Best-First Search Logic:

Step 1: Evaluate all available nodes
Node A: f(A) = 5
Node B: f(B) = 3 ← Best!
Node C: f(C) = 7

Step 2: Expand best node (B)
Add B's children to frontier

Step 3: Re-evaluate all frontier nodes
Continue with best f(n) value

Data Structure: Priority Queue (Heap)

Key Characteristics:

Strategy: Always expand the "best" node according to evaluation function
Implementation: Uses priority queue (heap data structure)
Evaluation: Based on f(n) = estimate of total cost
Flexibility: Can use different evaluation functions
Efficiency: Focuses search on promising areas
Memory: Keeps all nodes in memory for comparison

🤑 Greedy Best-First Search

Greedy Strategy:

Evaluation Function:
f(n) = h(n) only!
(Ignores g(n) - actual cost)

Example - Pathfinding:
Node A: h(A) = 8 (8 units from goal)
Node B: h(B) = 3 (3 units from goal) ← Pick this!
Node C: h(C) = 12 (12 units from goal)

Always chooses node that appears closest to goal

Heuristic Example:
Straight-line distance to goal

Characteristics:

Complete: ❌ No (can get stuck in loops)
Optimal: ❌ No (ignores actual path cost)
Time: O(b^m) in worst case
Space: O(b^m) keeps all nodes
Advantage: Fast when heuristic is good
Problem: Can be misled by poor heuristics

                            ⚡ Speed vs Accuracy: Very fast but may find suboptimal solutions or get stuck!
                        

⭐ A* Search Algorithm

A* Evaluation Function:

f(n) = g(n) + h(n)

Example:
Node A:
• g(A) = 4 (actual cost from start)
• h(A) = 6 (heuristic to goal)
• f(A) = 4 + 6 = 10

Node B:
• g(B) = 3 (actual cost from start)
• h(B) = 5 (heuristic to goal)
• f(B) = 3 + 5 = 8 ← Choose this!

Balances actual cost + estimated cost

A* Characteristics:

Complete: ✅ Yes (if heuristic is admissible)
Optimal: ✅ Yes (if heuristic is admissible & consistent)
Strategy: Best-first using f(n) = g(n) + h(n)
Admissible heuristic: h(n) ≤ actual cost to goal
Consistent heuristic: h(n) ≤ cost(n,n') + h(n')
Performance: Optimally efficient for given heuristic

🏆 Gold Standard: A* is the most widely used informed search algorithm!

⚖️ Search Algorithm Comparison

Algorithm	Complete?	Optimal?	Time Complexity	Space Complexity	Key Feature
BFS	✓ Yes	✓ Yes	O(b^d)	O(b^d)	Uninformed, level-order
DFS	✗ No*	✗ No	O(b^m)	O(bm)	Uninformed, memory efficient
Best-First	~ Depends	~ Depends	O(b^m)	O(b^m)	Uses evaluation function f(n)
Greedy Best-First	✗ No	✗ No	O(b^m)	O(b^m)	Fast but can be misleading
*A Search**	✓ Yes*	✓ Yes*	O(b^d)	O(b^d)	Optimal & complete with good heuristic

Legend: b = branching factor, d = depth of optimal solution, m = maximum depth
*A* properties depend on admissible & consistent heuristics

🎯 Key Takeaways

🧠 Heuristics Are Crucial

The quality of your heuristic function determines search efficiency. Good heuristics guide toward the goal, poor ones can mislead the search entirely.

⭐ A* is the Gold Standard

A* combines actual cost g(n) with heuristic h(n) to find optimal solutions efficiently. It's complete and optimal with admissible heuristics.

⚡ Speed vs Accuracy Trade-off

Greedy Best-First is fastest but risky. A* balances optimality with efficiency. Choose based on your requirements for speed vs accuracy.

🎲 Admissible Heuristics

For A* to be optimal, heuristics must be admissible (never overestimate) and consistent. Examples: straight-line distance, Manhattan distance.

                    🎓 Real-world Applications: GPS navigation, game AI pathfinding, robotics, network routing, and puzzle solving all use these algorithms!
                