ARTIFICIAL INTELLIGENCE

UNIT 2: PROBLEM SOLVING

Search Algorithms & Heuristic Strategies

Comprehensive Study Notes with Diagrams & Examples

Topics: BFS · DFS · DLS · IDDFS · UCS · A* · AO* · MBA* · Greedy · Hill Climbing · Genetic
Algorithm
Includes: Definitions · Step-by-step Solutions · Complexity Analysis · Comparisons

Prepared for undergraduate AI coursework

UNIT 2: PROBLEM SOLVING IN AI Artificial Intelligence – Search Algorithms

TABLE OF CONTENTS
1 Search Algorithms – Introduction
1.1 What is Search?
1.2 State Space Representation
1.3 Classification of Search Algorithms
2 Uninformed Search Strategies
2.1 Breadth First Search (BFS)
2.2 Depth First Search (DFS)
2.3 Depth Limited Search (DLS)
2.4 Iterative Deepening DFS (IDDFS)
2.5 Uniform Cost Search (UCS)
3 Heuristic Search Strategies
3.1 A* Search Algorithm
3.2 AO* Search Algorithm
3.3 Memory-Bounded A* (MBA*)
3.4 Greedy Depth First Search
4 Local Search Strategies
4.1 Hill Climbing Algorithm
5 Evolutionary Algorithms
5.1 Genetic Algorithm
6 Comparison & Summary Tables

AI Unit 2 Notes Page 2 Search Algorithms & Heuristics

UNIT 2: PROBLEM SOLVING IN AI Artificial Intelligence – Search Algorithms

1. SEARCH ALGORITHMS – INTRODUCTION

1.1 What is Search?
Search is the systematic process of exploring a state space to find a solution to a given problem. In Artificial
Intelligence, search algorithms are fundamental techniques used by an agent to move from an initial state to a
goal state by applying a sequence of actions. The quality of a search algorithm is measured by completeness,
time complexity, space complexity, and optimality.

Key Terminology:
Glossary of Terms

• State: A description of the world at a given moment.

• Initial State: The starting point of the search.

• Goal State: The desired final configuration.

• State Space: The set of all possible states reachable from the initial state.

• Search Tree: A tree representation of the state space exploration.

• Node: A data structure representing a state in the search tree.

• Frontier (Open List): Set of nodes generated but not yet expanded.

• Explored (Closed List): Set of already visited nodes.

• Path Cost: Total cost from initial state to current node.

• Branching Factor (b): Average number of successors per node.

• Depth (d): Number of steps from root to goal node.

1.2 State Space Representation

A problem is represented as a 4-tuple: (S, A, T, G) where S = set of states, A = set of actions, T = transition
function T(s,a)→s', G = goal test.

Example – 8-Puzzle Problem:

Component Description

Initial State 1 2 3 / 4 _ 6 / 7 5 8 (_ = blank tile)

Goal State 123/456/78_

Actions Move blank: UP, DOWN, LEFT, RIGHT

State Space Size 9! / 2 = 181,440 reachable states

Solution Sequence of moves to reach goal from initial

1.3 Properties of Search Algorithms

Property Definition

Completeness Will the algorithm always find a solution if one exists?

Time Complexity How many nodes are generated during search?

Space Complexity How much memory is required?

AI Unit 2 Notes Page 3 Search Algorithms & Heuristics

UNIT 2: PROBLEM SOLVING IN AI Artificial Intelligence – Search Algorithms

Optimality Does the algorithm find the least-cost solution?

Classification of Search Algorithms:

Category Algorithms Uses Heuristic?

Uninformed (Blind) BFS, DFS, DLS, IDDFS, UCS No

Informed (Heuristic) A*, AO*, MBA*, Greedy Best-First Yes

Local / Stochastic Hill Climbing, Simulated Annealing Yes (local)

Evolutionary Genetic Algorithm Fitness Function

AI Unit 2 Notes Page 4 Search Algorithms & Heuristics

UNIT 2: PROBLEM SOLVING IN AI Artificial Intelligence – Search Algorithms

2. UNINFORMED SEARCH STRATEGIES

Uninformed (or blind) search strategies have no additional information about states beyond what is provided in
the problem definition. They explore the state space systematically without knowledge of how far they are from the
goal.

2.1 Breadth First Search (BFS)

Definition: BFS explores the state space level by level, expanding all nodes at depth d before expanding nodes at
depth d+1. It uses a FIFO queue as the frontier.

Core Characteristics:
BFS Properties

• Data Structure: Queue (FIFO – First In First Out)

• Completeness: YES – guaranteed to find a solution if one exists (for finite branching factor)

• Optimality: YES – finds shallowest (least number of steps) goal first

• Time Complexity: O(bd) where b = branching factor, d = depth of solution

• Space Complexity: O(bd) – stores all nodes at the current level in memory

• Disadvantage: Exponential memory usage makes it impractical for deep solutions

BFS Algorithm (Pseudocode):

function BFS(problem):
node ← initial_state
if GOAL_TEST(node): return node
frontier ← QUEUE with node
explored ← empty set
loop:
if frontier is empty: return FAILURE
node ← [Link]()
[Link](node)
for each action in ACTIONS(node):
child ← CHILD_NODE(node, action)
if child not in explored or frontier:
if GOAL_TEST(child): return child
[Link](child)

Diagram – BFS Tree Traversal:

AI Unit 2 Notes Page 5 Search Algorithms & Heuristics

UNIT 2: PROBLEM SOLVING IN AI Artificial Intelligence – Search Algorithms

BFS Traversal Order: A→B→C→D→E→F→G→H→I→J→K

1

2 3

B C

4 5 6 7

D E F G

8 9 10 11

H I J K

Level 0 Level 1 Level 2 Level 3

Figure 2.1: BFS explores level by level. Numbers show visit order. Level 0 (red) → Level 1 (teal) → Level 2 (gold) → Level 3 (green).

Step-by-Step BFS Example (Graph: A→B,C; B→D,E; C→F,G; Find G):

Step Frontier (Queue) Explored Action

1 [A] {} Dequeue A, expand → add B,C

2 [B,C] {A} Dequeue B, expand → add D,E

3 [C,D,E] {A,B} Dequeue C, expand → add F,G

4 [D,E,F,G] {A,B,C} Dequeue D (no children)

5 [E,F,G] {A,B,C,D} Dequeue E (no children)

6 [F,G] {A,B,C,D,E} Dequeue F (no children)

7 [G] {A,B,C,D,E,F} Dequeue G → GOAL FOUND!

Key Insight: BFS guarantees the shortest path (in terms of number of edges) because it explores all paths of
length k before any path of length k+1.

2.2 Depth First Search (DFS)

Definition: DFS explores as far as possible along each branch before backtracking. It uses a LIFO stack (or
recursion) as the frontier.

DFS Properties

• Data Structure: Stack (LIFO – Last In First Out) or recursion

• Completeness: NO – may get stuck in infinite loops (loops in graph), YES with cycle detection

• Optimality: NO – does not guarantee shortest path

• Time Complexity: O(bm) where m = maximum depth of search tree

• Space Complexity: O(b×m) – linear space, only stores current path + siblings

• Advantage: Much lower memory requirement than BFS

• Disadvantage: May find non-optimal solutions; can be trapped in infinite branches

DFS Algorithm (Pseudocode):

AI Unit 2 Notes Page 6 Search Algorithms & Heuristics

UNIT 2: PROBLEM SOLVING IN AI Artificial Intelligence – Search Algorithms

function DFS(node, explored):

if GOAL_TEST(node): return node
[Link](node)
for each child of node:
if child not in explored:
result ← DFS(child, explored)
if result ≠ FAILURE: return result
return FAILURE

Diagram – DFS Tree Traversal:

DFS Traversal Order: A→B→D→H→I→E→C→F→G
1

2 7

B C

3 6 8 9

D E F G

4 5

H I

Numbers indicate visit order | DFS goes deep before backtracking

Figure 2.2: DFS goes deep first (A→B→D→H→I) then backtracks. Each color represents a different step in traversal.

Step-by-Step DFS Example:

Step Stack (Top→Bottom) Explored Action

1 [A] {} Pop A, push C,B (right-first)

2 [B,C] {A} Pop B, push E,D

3 [D,E,C] {A,B} Pop D, push I,H

4 [H,I,E,C] {A,B,D} Pop H → leaf node

5 [I,E,C] {A,B,D,H} Pop I → leaf node

6 [E,C] {A,B,D,H,I} Pop E → leaf node

7 [C] {A,B,D,H,I,E} Pop C, push G,F

8 [F,G] {A,B,C,...} Pop F → leaf; Pop G → GOAL!

BFS vs DFS Comparison:

Property BFS DFS
d
Memory O(b ) – exponential O(b×m) – linear

Time O(bd) O(bm)

Completeness Yes (finite space) No (infinite space)

Optimality Yes (unit cost) No

Best for Shortest path, shallow goal Memory-limited, deep goal

AI Unit 2 Notes Page 7 Search Algorithms & Heuristics

UNIT 2: PROBLEM SOLVING IN AI Artificial Intelligence – Search Algorithms

2.3 Depth Limited Search (DLS)

Definition: DLS is a modified DFS where the search is limited to a pre-defined depth limit L. Nodes at depth L are
treated as if they have no successors. This prevents DFS from getting trapped in infinite-depth branches.

DLS Properties

• Depth Limit: L – predetermined maximum search depth

• Completeness: YES, if goal depth d ≤ L; NO if d > L

• Optimality: NO – does not guarantee optimal solution

• Time Complexity: O(bL)

• Space Complexity: O(b×L)

• Returns: Solution, Failure (no solution), or Cutoff (limit reached before goal)

DLS Algorithm:
function DLS(node, goal, limit):
if GOAL_TEST(node): return node
if limit == 0: return CUTOFF
cutoff_occurred ← False
for each child of node:
result ← DLS(child, goal, limit-1)
if result == CUTOFF: cutoff_occurred ← True
else if result ≠ FAILURE: return result
if cutoff_occurred: return CUTOFF
else: return FAILURE

Worked Example – DLS with L=2:

Tree: A→{B,C}, B→{D,E}, C→{F,G}, D→{H}, Goal = G, Limit = 2

Step Result

Visit A (depth 0) Not goal, depth < 2, expand

Visit B (depth 1) Not goal, depth < 2, expand

Visit D (depth 2) Not goal, depth = L → CUTOFF, backtrack

Visit E (depth 2) Not goal, depth = L → CUTOFF, backtrack

Visit C (depth 1) Not goal, depth < 2, expand

Visit F (depth 2) Not goal, depth = L → CUTOFF, backtrack

Visit G (depth 2) GOAL FOUND! Return solution

Note: DLS works here because goal G is at depth 2 = L. If goal were at depth 3, DLS would fail with CUTOFF.

2.4 Iterative Deepening Depth-First Search (IDDFS)

Definition: IDDFS combines the space efficiency of DFS with the completeness and optimality of BFS by running
DLS repeatedly with increasing depth limits (0, 1, 2, … until goal is found).

IDDFS Properties – Best of Both Worlds

• Strategy: Run DLS with limit=0, then limit=1, then limit=2, … until goal found

• Completeness: YES – guaranteed to find solution if one exists

AI Unit 2 Notes Page 8 Search Algorithms & Heuristics

UNIT 2: PROBLEM SOLVING IN AI Artificial Intelligence – Search Algorithms

• Optimality: YES – finds shallowest goal (like BFS) when all step costs are equal

• Time Complexity: O(bd) – same as BFS asymptotically

• Space Complexity: O(b×d) – linear like DFS!

• Overhead: Nodes at top levels are re-generated multiple times (acceptable overhead)

Why Repeated Node Generation is Acceptable:

In a tree with branching factor b=10 and goal at depth d=5, the bottom level has bd=100,000 nodes. The top levels
together have only 1+10+100+1000+10000=11,111 nodes – just 11% overhead. As d increases, this fraction
diminishes further, making IDDFS highly efficient in practice.

Diagram – IDDFS Iterations:

IDDFS: DFS repeated with increasing depth limit (0,1,2,3...)
Depth 0
A

Depth 1
B C

Depth 2
D E F G

Depth 3
H I J K

Figure 2.4: IDDFS runs DFS with limit 0 (only root), then limit 1 (1 level), then limit 2, etc. Each color shows nodes reachable at that
depth.

Step-by-Step IDDFS (Goal at depth 3):

Iteration Depth Limit Nodes Visited Result

1 L=0 A CUTOFF (goal not found)

2 L=1 A, B, C CUTOFF (goal not found)

3 L=2 A,B,C,D,E,F,G CUTOFF (goal not at depth ≤2)

4 L=3 A,B,C,D,E,F,G,H,I,J,K GOAL FOUND at depth 3

AI Unit 2 Notes Page 9 Search Algorithms & Heuristics

UNIT 2: PROBLEM SOLVING IN AI Artificial Intelligence – Search Algorithms

2.5 Uniform Cost Search (UCS)

Definition: UCS expands the node with the lowest cumulative path cost g(n) from the start node. It uses a priority
queue ordered by g(n). UCS generalises BFS to handle non-uniform step costs and always finds the optimal
(least-cost) solution.

UCS Properties

• Data Structure: Priority Queue (min-heap ordered by cumulative cost g(n))

• Completeness: YES – if every step cost ≥ ε > 0

• Optimality: YES – always finds the least-cost path

• Time Complexity: O(b1+■C*/ε■) where C* = optimal cost, ε = min step cost

• Space Complexity: Same as time complexity

• Key Difference from BFS: BFS expands by depth; UCS expands by total cost

• Condition: Step costs must be non-negative

UCS Algorithm:
function UCS(problem):
frontier ← PRIORITY_QUEUE with (0, initial_state)
explored ← empty set
loop:
if frontier is empty: return FAILURE
(cost, node) ← [Link]() // lowest cost first
if GOAL_TEST(node): return (cost, node)
[Link](node)
for each (child, step_cost) in EXPAND(node):
new_cost ← cost + step_cost
if child not in explored:
[Link]((new_cost, child))

Diagram – UCS Graph:

UCS Optimal Path: S→A→C→G (Cost = 1+3+6 = 10)

3
A C

1 6

7
S G

5 1

2
B D

Optimal path Other edges

Figure 2.5: UCS graph. Red path (S→A→C→G, cost=10) is optimal. Numbers on edges are step costs.

AI Unit 2 Notes Page 10 Search Algorithms & Heuristics

UNIT 2: PROBLEM SOLVING IN AI Artificial Intelligence – Search Algorithms

Step-by-Step UCS Example:

Graph: S→A(1), S→B(5), A→C(3), A→D(7), B→D(2), C→G(6), D→G(1)

Step Frontier (node:cost) Explored Action

1 S:0 {} Expand S → A:1, B:5

2 A:1, B:5 {S} Expand A (cost 1) → C:4, D:8

3 C:4, B:5, D:8 {S,A} Expand C (cost 4) → G:10

4 B:5, G:10, D:8 {S,A,C} Expand B (cost 5) → D:7 (update!)

5 D:7, G:10 {S,A,C,B} Expand D (cost 7) → G:8 (update!)

6 G:8 {S,A,C,B,D} Expand G → GOAL! Optimal cost = 8

Optimal Path: S→B→D→G with cost 5+2+1 = 8 (not S→A→C→G = 10)

AI Unit 2 Notes Page 11 Search Algorithms & Heuristics

UNIT 2: PROBLEM SOLVING IN AI Artificial Intelligence – Search Algorithms

3. HEURISTIC SEARCH STRATEGIES

Heuristic (informed) search uses problem-specific knowledge, called a heuristic function h(n), to guide the
search toward the goal more efficiently. A heuristic estimates the cost from a node n to the goal. A good heuristic
dramatically reduces the search space.

Properties of a Good Heuristic:

Heuristic Properties

• Admissibility: h(n) ≤ h*(n) for all n (never overestimates the true cost to goal)

• Consistency (Monotonicity): h(n) ≤ c(n,a,n') + h(n') for all successors n' via action a

• Informedness: h2(n) ≥ h1(n) means h2 dominates h1 (better heuristic)

• Example heuristics: Manhattan distance, Euclidean distance, Misplaced tiles count

3.1 A* Search Algorithm

Definition: A* is the most widely used informed search algorithm. It evaluates nodes using f(n) = g(n) + h(n), where
g(n) is the actual cost from start to n, and h(n) is the estimated cost from n to goal. A* finds the optimal path when the
heuristic is admissible.

A* Properties

• Evaluation Function: f(n) = g(n) + h(n)

• g(n): Actual cost from initial state to node n

• h(n): Heuristic estimate from n to goal (must be admissible)

• f(n): Estimated total cost of the cheapest path through n

• Completeness: YES (if branching factor is finite and h is admissible)

• Optimality: YES – with admissible h(n)

• Time Complexity: O(bd) in worst case; much better in practice

• Space Complexity: O(bd) – stores all generated nodes

• Advantage over UCS: h(n) guides search, reducing nodes explored

A* Algorithm:
function A_STAR(problem, h):
frontier ← PRIORITY_QUEUE with (f(start), start, g=0)
explored ← {}; came_from ← {}
g_cost ← {start: 0}
loop:
if frontier empty: return FAILURE
(f, node) ← [Link]() // min f first
if GOAL_TEST(node): return RECONSTRUCT_PATH(came_from, node)
[Link](node)
for each (child, cost) in EXPAND(node):
tentative_g ← g_cost[node] + cost
if child not in explored and tentative_g < g_cost.get(child, ∞):
came_from[child] ← node
g_cost[child] ← tentative_g
[Link]((tentative_g + h(child), child))

AI Unit 2 Notes Page 12 Search Algorithms & Heuristics

UNIT 2: PROBLEM SOLVING IN AI Artificial Intelligence – Search Algorithms

Diagram – A* Graph:
A* Path: S→A→C→G f(n)=g(n)+h(n) | Total cost=2+4+3=9

A g=4 C
h=6 h=2

g=2 g=3

S g=6 G
h=7 h=0

g=3 g=4

B g=2 D
h=5 h=3

h=heuristic (estimated cost to G) | g=actual cost from S

Figure 3.1: A* evaluates f(n)=g(n)+h(n). Teal path is optimal. h values shown inside nodes as 'h=N'. Edge labels show actual step costs
g.

Step-by-Step A* Example:
Graph: S→A(2), S→B(3), A→C(4), A→D(6), B→D(2), C→G(3), D→G(4) | h: S=7, A=6, B=5, C=2, D=3, G=0

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

S 0 7 7 Start; expand S

A 2 6 8 Via S→A; expand A

B 3 5 8 Via S→B; expand B

C 6 2 8 Via S→A→C; expand C

D(via B) 5 3 8 Via S→B→D; update if better

G(via C) 9 0 9 Via S→A→C→G → GOAL!

Real-World Applications of A*:

• GPS Navigation: Finding shortest route on road maps (Google Maps, Waze)

• Game AI: Pathfinding for characters in video games (Pacman, RPGs)

• Robotics: Motion planning for autonomous robots

• Network Routing: Finding optimal data packet routes

• Puzzle Solving: 8-puzzle, 15-puzzle, Rubik's cube

AI Unit 2 Notes Page 13 Search Algorithms & Heuristics

UNIT 2: PROBLEM SOLVING IN AI Artificial Intelligence – Search Algorithms

3.2 AO* Search Algorithm

Definition: AO* is an extension of A* for AND-OR graphs. In an AND-OR graph, some nodes require ALL children
(AND nodes) to be solved, while others require only ONE child (OR nodes) to be solved. AO* finds the optimal solution
graph (not just a path) in such structures.

AND-OR Graph Concepts:

AND-OR Graph Terminology

• OR Node: Represents alternatives – solving any ONE child solves the OR node

• AND Node: Represents decomposition – ALL children must be solved

• Solution Graph: A subgraph of the AND-OR graph that solves the root node

• Cost of AND node: Sum of costs of all children + arc cost

• Cost of OR node: Minimum cost among all children + arc cost

• Solved Node: A terminal (leaf) node or a node whose solution graph is solved

AO* Algorithm Steps:

Step Description

Step 1 Start with initial node A in open list; compute h(A)

Step 2 Select node with best f-value from open list

Step 3 Expand selected node; classify children as AND/OR

Step 4 Update costs bottom-up through the graph

Step 5 Mark solved nodes; propagate upward

Step 6 If start node is SOLVED → return solution graph

Step 7 Else add unsolved children to open list; repeat from Step 2

Worked Example – AO* on AND-OR Tree:

Problem: Solve node A. A has OR children B and C. B has AND children D,E. C is terminal (goal). h values: A=5,
B=3, C=2, D=2, E=1.

Phase Action

Initialize Open: {A}, h(A)=5, f(A)=5

Expand A (OR) Children: B(h=3), C(h=2). f(B)=3, f(C)=2. Best = C

Expand C C is terminal → SOLVED. Cost(C)=0+2=2

A is OR → best child = C. Cost(A)=cost(C)+arc=2+1=3. A is

Update A SOLVED!

Result Solution graph: A → C (total cost = 3)

Key Difference: A* finds a path; AO* finds an optimal solution tree/graph. AO* is ideal for problems with
subproblems that can be decomposed (e.g., game trees, theorem proving, robot task planning).

3.3 Memory-Bounded A* Algorithm (MBA*)

AI Unit 2 Notes Page 14 Search Algorithms & Heuristics

UNIT 2: PROBLEM SOLVING IN AI Artificial Intelligence – Search Algorithms

Definition: MBA* (also called SMA* – Simplified Memory-Bounded A*) is a variant of A* that uses only a fixed amount
of memory. When memory is exhausted, it drops the worst leaf node (highest f-value) and regenerates it later if
needed.

Key Variants:
Algorithm Description

IDA* (Iterative Deepening A*) Uses DFS + A* heuristic; O(d) space; re-expands nodes

SMA* (Simplified MBA*) Uses bounded memory; drops worst node when full

RBFS (Recursive BFS) Recursive A* with O(bd) memory like IDA*

MA* (Memory-Bounded A*) Original proposal; SMA* is simplified version

SMA* Algorithm Key Steps:

SMA* Properties

• Step 1: Run A* normally, keeping all generated nodes

• Step 2: When memory is full, identify the node with the HIGHEST f-value in the queue

• Step 3: Remove that node; back up its f-value to its parent (parent remembers best forgotten child
cost)

• Step 4: Continue search; re-generate forgotten nodes only when needed

• Completeness: YES if solution fits within memory

• Optimality: YES if solution fits within memory

• Space Complexity: O(memory limit) – user defined

IDA* – Iterative Deepening A*:

IDA* is the most commonly implemented memory-bounded variant. It runs iterative deepening but uses f-cost
cutoffs instead of depth limits.
function IDA_STAR(problem, h):
threshold ← h(start)
loop:
(result, threshold) ← SEARCH(start, 0, threshold)
if result == FOUND: return path
if threshold == ∞: return FAILURE

function SEARCH(node, g, threshold):

f ← g + h(node)
if f > threshold: return (NOT_FOUND, f)
if GOAL_TEST(node): return (FOUND, f)
min ← ∞
for each child with cost c:
(result, t) ← SEARCH(child, g+c, threshold)
if result == FOUND: return (FOUND, t)
min ← MIN(min, t)
return (NOT_FOUND, min)

AI Unit 2 Notes Page 15 Search Algorithms & Heuristics

 UNIT 2: PROBLEM SOLVING IN AI Artificial Intelligence – Search Algorithms

3.4 Greedy Best-First Search

Definition: Greedy Best-First Search (GBFS) expands the node that appears closest to the goal according to the
heuristic function h(n) alone, ignoring the actual cost g(n). It is greedy because it always picks the locally best option
without considering the full path cost.

Greedy Best-First Search Properties

• Evaluation Function: f(n) = h(n) only (unlike A* which uses g(n)+h(n))

• Data Structure: Priority Queue ordered by h(n)

• Completeness: NO – can get stuck in loops

• Optimality: NO – does not guarantee shortest/cheapest path

• Time Complexity: O(bm) in worst case

• Space Complexity: O(bm)

• Advantage: Very fast in practice; good for large spaces with good heuristic

• Disadvantage: Ignores past costs; may find sub-optimal or no solution

Greedy vs A* Comparison:
y Greedy BFS A*

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

eness No Yes (admissible h)

y No Yes (admissible h)

Faster (fewer expansions) Slower (considers full cost)

Less More

Stuck in local optima Safe if h is admissible

Example – Greedy BFS vs A* on same graph:

Graph: S→A(2), S→B(1), B→G(10), A→G(3) | h: S=4, A=2, B=1, G=0

Algorithm Path Found

Greedy BFS Picks B first (h=1 < h(A)=2) → B→G; Cost=11 (sub-optimal!)

g(A)=2,h(A)=2,f=4; g(B)=1,h(B)=1,f=2; Picks B first but finds

A* S→A→G=5 optimal

AI Unit 2 Notes Page 16 Search Algorithms & Heuristics

UNIT 2: PROBLEM SOLVING IN AI Artificial Intelligence – Search Algorithms

4. LOCAL SEARCH: HILL CLIMBING ALGORITHM

Definition: Hill Climbing is a local search algorithm that iteratively moves to a neighboring state with a higher (or
equal) value according to an objective function, until no better neighbor exists. Unlike global search (BFS/DFS), it does
not maintain a search tree – only the current state is kept in memory.

Hill Climbing Properties

• Analogy: Like climbing a mountain in thick fog – you can only see your immediate surroundings

• Objective Function: A value function to maximize (or minimize for descent)

• Neighbor: A state reachable from current state in one move

• Current State: The only state stored in memory

• Space Complexity: O(1) – only current state stored

• Completeness: NO – may get stuck at local maxima

• Optimality: NO – local optima ≠ global optima

Hill Climbing Algorithm:

function HILL_CLIMBING(problem):
current ← INITIAL_STATE
loop:
neighbor ← highest-valued successor of current
if VALUE(neighbor) ≤ VALUE(current):
return current // local maximum reached
current ← neighbor

Diagram – Hill Climbing Landscape:

Hill Climbing: follows gradient, stuck at local max!

Local Max Global Max

Local Min

Start → Local Max (stuck) | Cannot reach Global Max without restarts
Figure 4.1: Hill Climbing follows the gradient upward but gets stuck at local maxima. The global maximum can only be reached with
restarts or different strategies.

Variants of Hill Climbing:

Variant Description

Simple Hill Climbing Picks the first neighbor better than current; fast but risky

Steepest Ascent HC Evaluates ALL neighbors; picks the best one; more thorough

Stochastic HC Randomly picks among uphill moves; avoids some local optima

AI Unit 2 Notes Page 17 Search Algorithms & Heuristics

UNIT 2: PROBLEM SOLVING IN AI Artificial Intelligence – Search Algorithms

Random Restart HC Restarts from random state on stuck; complete with enough restarts

Allows downhill moves with decreasing probability; can escape local

Simulated Annealing optima

Problems with Hill Climbing:

Common Problems

• Local Maxima: A state better than all neighbors but not the global optimum → algorithm stops

• Plateaux (Flat regions): All neighbors have the same value → random walk required

• Ridges: Sequence of local maxima that are hard to traverse with simple moves

• Solution: Random restarts, simulated annealing, or genetic algorithms overcome these issues

Example – 8-Queens Problem with Hill Climbing:

Place 8 queens on an 8×8 board so no two queens attack each other.

Phase Detail

State An arrangement of 8 queens (one per column)

Heuristic h Number of pairs of queens that are attacking each other

Goal h = 0 (no attacks)

Move Move one queen in its column to reduce h

Step 1 Random placement → h=17 attacking pairs

Step 2 Try all 8×7=56 moves → pick move reducing h the most

Step 3 New state → h=1 (1 attacking pair remains)

Step 4 All moves increase h → LOCAL MINIMUM! Restart

Restart New random placement → h=0 found in ~14 steps

AI Unit 2 Notes Page 18 Search Algorithms & Heuristics

UNIT 2: PROBLEM SOLVING IN AI Artificial Intelligence – Search Algorithms

5. EVOLUTIONARY ALGORITHMS: GENETIC

ALGORITHM
Definition: Genetic Algorithms (GAs) are stochastic search and optimization techniques inspired by the process of
natural evolution (Darwin's theory). They operate on a population of candidate solutions (chromosomes), applying
genetic operators (selection, crossover, mutation) to evolve better solutions over generations.

Biological Inspiration:
GA Term Meaning

Chromosome Encoded solution (usually a bit string or array)

Gene A single element/parameter in the chromosome

Population Set of current candidate solutions

Fitness Function Objective function evaluating solution quality

Selection Choosing parents based on fitness (survival of the fittest)

Crossover Combining two parents to produce offspring

Mutation Random change in a gene to maintain diversity

Generation One cycle of evaluation + selection + reproduction

Diagram – Genetic Algorithm Flow:

Genetic Algorithm: Population evolves via selection, crossover, mutation

Population (Fitness) & Mutation Generation

1. Initial 2. Selection 3. Crossover 4. New

Repeat until fitness goal reached

Parent 1: 1 0 1 1 0 0 1 0
Parent 2: 0 1 0 0 1 1 0 1
Child: 1 0 1 0 1 1 0 1
Figure 5.1: The GA cycle. Population evolves over generations via selection, crossover, and mutation until the fitness goal is reached.

Genetic Algorithm Pseudocode:

function GENETIC_ALGORITHM(population, FITNESS_FN):
loop:
new_population ← empty
for i = 1 to SIZE(population):
x ← RANDOM_SELECTION(population, FITNESS_FN)
y ← RANDOM_SELECTION(population, FITNESS_FN)
child ← CROSSOVER(x, y)
if RANDOM() < mutation_rate:
child ← MUTATE(child)
new_population.add(child)
population ← new_population
best ← highest FITNESS in population
if best satisfies goal: return best

AI Unit 2 Notes Page 19 Search Algorithms & Heuristics

UNIT 2: PROBLEM SOLVING IN AI Artificial Intelligence – Search Algorithms

Genetic Operators in Detail:

1. Selection Methods:
Method Description

Probability of selection ∝ fitness; fitter individuals selected more

Roulette Wheel often

Tournament k individuals compete; fittest wins; good diversity control

Rank Selection Rank by fitness; select by rank; reduces dominance of very fit

Elitism Best n individuals pass unchanged; ensures best solution preserved

2. Crossover (Recombination):
Crossover combines two parent chromosomes to produce offspring. Example with 8-bit chromosomes:

Type Parent 1 Parent 2 Child

Single-point (cut at 14)0 1 1 | 0 0 1 0 0 1 0 0 | 1 1 0 1 1 0 1 1 1 1 0 1

Two-point (cut at 3,6)

1 0 1 | 1 0 0 | 1 0 0 1 0 | 0 1 1 | 0 1 1 0 1 0 1 1 1 0

Uniform (50% each) 1 0 1 1 0 0 1 0 0 1 0 0 1 1 0 1 1 1 1 0 1 0 0 1

3. Mutation:
Mutation introduces random changes to maintain genetic diversity and prevent premature convergence. Mutation
rate is typically kept low (0.001 to 0.01).

Type Operation

Bit Flip (binary) Flip random bit: 1→0 or 0→1

Swap mutation Swap two random genes

Random Resetting Replace gene with random value from its domain

Gaussian mutation Add Gaussian noise to real-valued genes

Complete Worked Example – GA for 8-Queens:

Represent each queen's column position as a digit. Chromosome = 8-digit string. Example: [2,4,7,4,8,5,5,2] =
queen positions in columns 1-8.

Step Detail

Population Generate 4 random chromosomes (8-digit strings)

Fitness f = 28 - (number of attacking pairs); max=28 (no attacks)

P1=[2,4,7,4,8,5,5,2] Attacks=24 pairs → f=28-24=4

P2=[3,2,7,5,2,4,1,1] Attacks=23 pairs → f=28-23=5

P3=[8,2,5,3,1,4,6,7] Attacks=20 pairs → f=28-20=8

P4=[4,8,4,2,4,6,3,1] Attacks=24 pairs → f=28-24=4

Selection P3 has highest fitness (f=8) → more likely selected

Crossover P3×P2 at point 5 → [8,2,5,3,1,4,1,1]

Mutation Flip position 3: [8,2,6,3,1,4,1,1]

AI Unit 2 Notes Page 20 Search Algorithms & Heuristics

UNIT 2: PROBLEM SOLVING IN AI Artificial Intelligence – Search Algorithms

Evaluate New chromosome may have higher fitness

Repeat Continue until f=28 (perfect solution found)

Applications of Genetic Algorithms:

Real-World Applications

• Optimization: Scheduling, travelling salesman, resource allocation

• Machine Learning: Feature selection, neural network architecture search

• Engineering Design: Aerodynamic shape optimization, circuit design

• Game Playing: Evolving game strategies and agent behaviours

• Bioinformatics: Protein structure prediction, gene sequencing

• Finance: Portfolio optimization, trading strategy development

AI Unit 2 Notes Page 21 Search Algorithms & Heuristics

UNIT 2: PROBLEM SOLVING IN AI Artificial Intelligence – Search Algorithms

6. COMPREHENSIVE COMPARISON & SUMMARY

6.1 Complete Algorithm Comparison Table
Algorithm Complete Optimal Time Space Heuristic

BFS Yes Yes* O(b<super>d</super>) O(b<super>d</super>) No

DFS No No O(b<super>m</super>) O(bm) No

DLS Yes (d≤L) No O(b<super>L</super>) O(bL) No

IDDFS Yes Yes* O(b<super>d</super>) O(bd) No

UCS Yes Yes O(b<super>C*/ε</super>)

O(b<super>C*/ε</super>) No

Greedy BFS No No O(b<super>m</super>) O(b<super>m</super>) Yes

A* Yes Yes O(b<super>d</super>) O(b<super>d</super>) Yes

AO* Yes Yes O(b<super>d</super>) O(b<super>d</super>) Yes

IDA* Yes Yes O(b<super>d</super>) O(bd) Yes

SMA* Yes** Yes** O(b<super>d</super>) O(mem) Yes

Hill Climbing No No O(∞) O(1) Yes

Genetic Algo No No O(gen×pop) O(pop) Fitness

* Optimal for unit-cost paths. ** If solution fits in memory. b=branching factor, d=depth, m=max depth, L=depth limit, mem=memory size.

6.2 When to Use Which Algorithm

Algorithm Best Use Cases

Need shortest path (fewest hops); small/moderate search space;

BFS memory available

Deep solutions expected; memory constrained; solution density

DFS high

DLS Know approximate depth of solution; bounded exploration needed

Unknown depth; need BFS optimality with DFS memory; best

IDDFS uninformed choice

UCS Non-uniform step costs; need optimal cost solution

Greedy BFS Fast approximate solution OK; good heuristic available; large space

Optimal solution needed; good heuristic available; standard

A* pathfinding

AND-OR problem decomposition; theorem proving; hierarchical

AO* planning

MBA*/IDA* Very large space; memory constrained; need A* optimality

Optimization in continuous/large space; memory critical; quick

Hill Climbing approximate

Complex optimization; no gradient; combinatorial; multi-modal

Genetic Algorithm landscape

AI Unit 2 Notes Page 22 Search Algorithms & Heuristics

UNIT 2: PROBLEM SOLVING IN AI Artificial Intelligence – Search Algorithms

6.3 Quick Formulas Reference

Formula/Concept Expression

BFS/IDDFS nodes at depth d b + b² + b³ + … + bd = O(bd)

UCS optimality condition Every step cost ≥ ε > 0

A* evaluation f(n) = g(n) + h(n)

Admissibility condition h(n) ≤ h*(n) for all n

Consistency condition h(n) ≤ cost(n,n') + h(n') for all n, n'

GA fitness (8-queens) f = 28 - (attacking pairs); max=28

IDDFS node regeneration

overhead ≤ bd/(bd-1) ≈ b/(b-1); e.g. b=2 → 2x overhead

Greedy evaluation f(n) = h(n) only

End of Unit 2 – Problem Solving in AI

Topics covered: BFS · DFS · DLS · IDDFS · UCS · A* · AO* · MBA* · Greedy · Hill Climbing · Genetic Algorithm

AI Unit 2 Notes Page 23 Search Algorithms & Heuristics