Informed and Uninformed Search Technique

Uninformed search or blind search algorithms use only the information available in the
problem definition, that is, initial state, successor function, goal test and path cost. They do
not use any additional knowledge about how close a state is to the goal.

Example: BFS,DFS, Iterative Deepening Search

Informed search or heuristic search algorithms use heuristic functions to estimate how close
a node is to the goal.

A heuristic function:

𝒉(𝒏) = estimated cost from node 𝒏 to goal

This helps the algorithm focus on promising paths.

Example: Best-First Search, A* Search

Feature Uninformed Search Informed Search

Knowledge Used No extra knowledge Uses heuristic

Guidance Blind exploration Goal-directed

Node Expansion Large number of nodes Fewer nodes (usually)

Higher (with good

Efficiency Lower
heuristic)

Examples BFS, DFS, UCS, IDS Greedy, A*

Optimality Depends on algorithm Depends on heuristic

Complexity Often high Usually lower

BFS
Breadth-First Search (BFS) is an uninformed search algorithm that explores a graph or tree
level by level, expanding all nodes at one level before moving to the next depth. It uses a
FIFO queue (First-In, First-Out) data structure.

Starting from the root or source node, it explores all of its immediate neighbours and then
explore the neighbours of those neighbours. It continues until the goal is found.

Algorithm:

1. Put the start node into a queue.

2. Mark it as visited.
3. While the queue is not empty:
i) Remove (dequeue) the front node.
ii) If it is the goal → stop.
iii) Otherwise, enqueue all unvisited neighbours.
iv) Mark them as visited.

Property Value

Completeness Yes (if branching factor is finite)

Optimality Yes (for equal step costs)

Time Complexity O(b^d)

Space Complexity O(b^d)

Where:

 b = branching factor

 d = depth of shallowest goal

DFS
Depth-First Search (DFS) is an uninformed search algorithm that explores a graph or tree by
going as deep as possible along one branch before backtracking. It uses a stack (LIFO) data
structure.

Algorithm:

1. Start at the root node.

2. Mark it as visited.
3. Explore one unvisited neighbour deeply.
4. Continue until:
i) Goal is found, or
ii) No more unvisited neighbours.
5. Backtrack and explore other branches.

Property Value

Completeness No (fails in infinite-depth spaces)

Optimality No

Time Complexity O(b^m)

Space Complexity O(bm)

Where:

 b = branching factor

 m = maximum depth of search tree

Depth-Bounded DFS
Depth-Bounded DFS is a variation of Depth-First Search where a maximum depth limit is
imposed. The algorithm explores nodes depth-first, but stops expanding any node once the
depth limit is reached. Regular DFS may go infinitely deep and can get stuck in very deep
branches. Whereas, in case of Depth-Bounded DFS it prevents infinite descent, controls
search depth and useful when solution depth is known approximately.

Property Value

Completeness No (unless limit ≥ solution depth)

Optimality No

Time Complexity O(b^ℓ)

Space Complexity O(bℓ)

Where:

 b = branching factor

 ℓ = depth limit

Depth First Iterative Deepening (DFID) or Iterative Deepening

Depth-First Search (IDDFS)
Depth-First Iterative Deepening combines the advantages of DFS, that is low memory usage
and advantages of BFS, that is completeness and optimality for unit costs. Instead of
searching deeply once, it performs multiple depth-limited DFS searches, increasing the
depth limit step by step.

Property Value

Completeness Yes (if branching factor finite)

Optimality Yes (for equal step cost)

Time Complexity O(b^d)

Space Complexity O(bd)

Where:

 b = branching factor

 d = depth of shallowest goal

Hill Climbing
Hill Climbing is a local search algorithm that continuously moves toward a better state
(higher value or lower cost) until no improvement is possible. It is called “hill climbing”
because it is like climbing a hill step by step, always moving upward.

Starting with an initial solution, it evaluates neighbouring states and move to the neighbour
with the best improvement. It repeats until no better neighbour exists. It uses only local
information (no full search tree). The algorithm moves upward toward higher values and
stops at a local maximum even if a higher global maximum exists.

Problems in Hill Climbing

Local Maximum: Stops at a peak that is not the global best.

Plateau: Flat area where neighbours have same value.

Ridge: Narrow path where progress is difficult.

Property Value

Completeness No

Optimality No

Depends on
Time Complexity
problem

O(1) (very
Space Complexity
low)
Best First Search
Best-First Search is an informed search algorithm that selects the next node to expand based
on an evaluation function choosing the most promising node first. It uses a priority queue,
where nodes are ordered according to an evaluation function f(n)=h(n),

where h(n)= heuristic estimate of distance from node n to the goal

This version is specifically called Greedy Best-First Search because it greedily selects the
node that seems closest to the goal.

Algorithm:

1) Insert the start node into a priority queue.

2) While the queue is not empty:

a) Remove the node with the lowest 𝑓(𝑛).

b) If it is the goal → stop.

c) Otherwise expand it.

d) Add its successors into the priority queue.

3) Repeat until goal is found.

Property Value

Completeness No (in infinite spaces)

Optimality No

Time Complexity O(b^m)

Space Complexity O(b^m)

Where:

 b = branching factor

 m = maximum depth
A* algorithm
The A* (A-star) algorithm is an informed search algorithm and an extension of best-first
search algorithm that finds the least-cost path from a start node to a goal node using both
actual cost and estimated cost. With a good heuristic, A* is complete, optimal and efficient.

Below are the main components of A* algorithm:

1) Evaluation Function:

The core of A*algorithm is its evaluation function:

𝑓(𝑛) = 𝑔(𝑛) + ℎ(𝑛)

Where:

 𝑔(𝑛)→ actual cost from the start node to node n. Represents the exact cost
accumulated so far

 ℎ(𝑛)→ heuristic estimate from node n to the goal. An estimate of the remaining cost
to reach the goal.

 𝑓(𝑛)→ estimated total cost of the solution path through n

2) Open List:
It is a priority queue that stores nodes that have been generated but not yet expanded. It is
ordered by the lowest 𝑓(𝑛)value and the next node expanded is the one with smallest
value of 𝑓(𝑛).

3) Closed List:
It stores nodes already expanded and prevents re-processing the same node, improving
the efficiency and avoid loops.

4) Goal:
It checks whether the current node is the goal. When the goal is selected for expansion,
the algorithm stops. The solution path is reconstructed using parent pointers.

5) Parent:
Using parent pointer, each node keeps track of its parent node. Once the goal is found, the
path is traced backward from goal to start.
Algorithm:

 Initialize open list with start node.

 Loop:

1) Select node with lowest 𝑓(𝑛)

2) If it is goal → reconstruct path

3) Otherwise expand it

4) Update 𝑔(𝑛), compute 𝑓(𝑛)

5) Add new nodes to open list

 Continue until goal found or open list empty.