🔎 Uninformed Search vs Informed Search in AI

1. What is Search in AI?

Search is the process of exploring a problem space (possible states and actions) to find a path from the initial state to the goal state.

Search algorithms are broadly divided into:

1. Uninformed Search (Blind Search)

2. Informed Search (Heuristic Search)

---

2. Uninformed Search (Blind Search)

Definition

Uninformed search algorithms do not have any domain-specific knowledge (like distance to goal or cost estimates).
They only know:

• The initial state

• The goal state (or test for goal)

• The possible actions and transitions

That’s why they are called blind — they explore without guidance.

---

Characteristics of Uninformed Search

• No heuristic function used.

• Explores nodes in a uniform or systematic way.

• May generate many unnecessary states.

• Some are complete and optimal, but often less efficient.

---

Major Algorithms

1. Breadth-First Search (BFS)

   • Expands the shallowest node first.

   • Complete: Yes

   • Optimal: Yes (if all step costs are equal)

   • Time Complexity: $O(b^d)$

   • Space Complexity: $O(b^d)$

2. Depth-First Search (DFS)

   • Expands the deepest node first.

   • Complete: No (fails in infinite-depth spaces)

   • Optimal: No

   • Time Complexity: $O(b^m)$

   • Space Complexity: $O(bm)$

3. Depth-Limited Search (DLS)

   • DFS with depth cutoff limit $l$.

   • Avoids infinite loops.

4. Iterative Deepening Search (IDS/IDDFS)

   • Combines BFS and DFS (runs DFS repeatedly with increasing depth limit).

   • Complete: Yes

   • Optimal: Yes (when step cost = 1)

   • Time Complexity: $O(b^d)$

5. Uniform Cost Search (UCS)

   • Expands node with lowest path cost $g(n)$.

   • Complete: Yes

   • Optimal: Yes

   • Time Complexity: $O(b^{1+\lfloor C^*/\epsilon \rfloor})$

---

Advantages

• Simple to implement.

• Guarantee completeness in some cases (BFS, UCS, IDS).

• No need for heuristic knowledge.

Disadvantages

• Can be very inefficient (explores huge search spaces).

• High memory usage (BFS especially).

• Not practical for complex real-world problems.

---

3. Informed Search (Heuristic Search)

Definition

Informed search algorithms use heuristics (extra domain-specific knowledge) to estimate how close a state is to the goal.

A heuristic function $h(n)$ assigns an estimated cost from node $n$ to the goal.
This makes the search goal-directed and more efficient.

---

Characteristics of Informed Search

• Uses heuristic evaluation function.

• More efficient than uninformed search.

• Can balance between exploration and exploitation.

• Optimality depends on the heuristic quality.

---

Major Algorithms

1. Greedy Best-First Search

   • Expands the node with the lowest heuristic value $h(n)$.

   • Complete: No

   • Optimal: No

   • Time Complexity: Can be $O(b^m)$ in worst case

2. A* Search

   • Uses evaluation function:

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

     where:

     • $g(n)$ = cost from start to node $n$

     • $h(n)$ = estimated cost from $n$ to goal

   • Complete: Yes (with admissible heuristic)

   • Optimal: Yes (if heuristic is admissible & consistent)

   • Time Complexity: Exponential in worst case, but usually much better than uninformed.

3. Hill Climbing

   • Moves in the direction of increasing value (like climbing a hill).

   • Can get stuck in local maxima.

4. Beam Search

   • Keeps only a limited number of best states at each level.

---

Advantages

• More efficient than blind search.

• Reduces search space significantly.

• Can give optimal solutions (A*).

Disadvantages

• Requires good heuristic design.

• Wrong heuristics → bad performance.

• Some algorithms (like Greedy, Hill Climbing) are not guaranteed to be complete or optimal.

---

4. Comparison Table

Feature	Uninformed Search	Informed Search
Knowledge used	Only problem definition	Problem definition + heuristic
Heuristic function	Not used	Used ($h(n)$)
Efficiency	Low (may explore many nodes)	High (goal-directed)
Optimality	Some are optimal (BFS, UCS)	A* optimal (if heuristic admissible)
Examples	BFS, DFS, UCS, IDS	Greedy, A*, Hill Climbing
Real-world use	Simple puzzles, small problems	Pathfinding, AI planning, robotics

---

5. Real-Life Example

Imagine finding your way in a new city:

• Uninformed Search: You explore randomly, trying every possible street until you reach your destination (wasteful).

• Informed Search: You use Google Maps, which uses heuristics like distance and traffic to guide you efficiently (fast & goal-directed).

---

✅ In summary:

• Uninformed search = Blind, no heuristics, explores everything.

• Informed search = Smart, uses heuristics, faster & more efficient.