Module II: Search Algorithms in Ar ficial Intelligence

1. Automated Problem Solving

Automated problem solving is the process of finding a sequence of ac ons that transforms an ini al
state into a goal state.

Components of a Problem

 Ini al State

 Goal State

 Ac ons / Operators

 State Space

 Path Cost

2. State Space Search

 State Space: Set of all possible states reachable from the ini al state.

 Search Tree: A tree generated by applying operators to states.

 Nodes represent states, edges represent ac ons.

Search Strategies

 Define the order in which nodes are explored.

 Classified into:

o Uninformed (Blind) Search

o Informed (Heuris c) Search

3. Uninformed vs Informed Search

1
Uninformed Search

 No addi onal knowledge about the problem.

 Uses only problem defini on.

 Examples: BFS, DFS, Uniform Cost Search.

Informed Search

 Uses heuris c informa on to guide the search.

 More efficient than uninformed search.

 Examples: Best First Search, A*, IDA*.

4. Uninformed Search Algorithms

4.1 Breadth First Search (BFS)

 Expands the shallowest node first.

 Uses FIFO queue.

Proper es:

 Complete: Yes

 Op mal: Yes (for equal step cost)

 Time Complexity: 𝑂(𝑏 )

 Space Complexity: 𝑂(𝑏 )

Detailed Explana on:

Breadth First Search (BFS) is a way to explore a graph or tree level by level.

Think of it like this:

“First check everything close to me, then move one step farther, then farther…”

BFS is commonly used in AI for:

 Finding the shortest path

 Exploring state spaces

 Problem solving in games and puzzles

Simple real-life analogy

Imagine you’re looking for a friend in an apartment building:

1. First, check all rooms on the ground floor

2. Then check all rooms on the first floor

3. Then the second floor…

2
You don’t go deep into one floor before checking the others.
That’s BFS.

Key idea

 BFS uses a queue (First In, First Out)

 It explores all neighbors first, before going deeper

Simple graph example

Imagine this graph:

/ \

B C

/\ \

D E F

Start node: A

BFS step-by-step

1. Start at A

2. Visit all neighbors of A → B, C

3. Visit neighbors of B → D, E

4. Visit neighbors of C → F

BFS traversal order

A→B→C→D→E→F

This is level by level explora on.

How BFS works (simple steps)

1. Put the start node in a queue

2. Mark it as visited

3. While the queue is not empty:

o Remove the front node

3
 o Visit all its unvisited neighbors

o Add them to the queue

Why BFS is important in AI

 Finds the shortest path (minimum number of steps)

 Used in:

o Game AI

o Pathfinding (maps, robots)

o Web crawling

o Puzzle solving (like 8-puzzle)

Quick comparison with DFS

BFS DFS

Level by level Goes deep first

Uses queue Uses stack

Finds shortest path Not guaranteed

4.2 Depth First Search (DFS)

 Expands the deepest node first.

 Uses stack or recursion.

Proper es:

 Complete: No (in infinite depth)

 Op mal: No

 Time Complexity: 𝑂(𝑏 )

 Space Complexity: 𝑂(𝑏𝑚)

Detailed explana on:

Depth First Search (DFS)

Defini on

Depth First Search (DFS) is a search algorithm that:

 Expands the deepest node first

4
  Goes as deep as possible along one path before backtracking

How DFS works

 Starts from the root (start node)

 Explores one branch completely

 If no more nodes are le , it backtracks

 Con nues un l the goal is found or all nodes are explored

Data structure used

 Stack (explicitly)

 Recursion (implicitly uses call stack)

Simple example

Consider this tree:

/ \

B C

/\ \

D E F

Start node: A

DFS traversal (Le to Right)

1. Visit A

2. Go deep to B

3. Go deep to D

4. No children → backtrack

5. Visit E

6. Backtrack to A

7. Visit C

8. Go deep to F

5
DFS order

A→B→D→E→C→F

DFS goes deep first, not level by level.

Algorithm steps (simple)

1. Push the start node onto the stack

2. Pop the top node

3. Visit it if not visited

4. Push its children onto the stack

5. Repeat un l stack is empty or goal is found

Proper es of DFS

1. Completeness

Not complete

 If the tree has infinite depth, DFS may go down one infinite path and never return

2. Op mality

Not op mal

 Does not guarantee the shortest path

 First solu on found may be longer than others

3. Time Complexity

O(b^m)

Where:

 b = branching factor (number of children per node)

 m = maximum depth of the tree

DFS may explore all nodes up to depth m.

4. Space Complexity

O(bm)

 Stores only one path from root to leaf + siblings

6
  Uses much less memory than BFS

Advantages of DFS

✔ Low memory usage

✔ Simple to implement
✔ Useful when solu ons are deep

Disadvantages of DFS

✖ Can get stuck in infinite paths

✖ Does not find shortest solu on
✖ Not complete in infinite spaces

4.3 Uniform Cost Search (UCS)

 Expands node with lowest path cost.

 Uses priority queue.

Proper es:

 Complete: Yes

 Op mal: Yes

 Handles varying step costs.

Details:

Defini on

Uniform Cost Search (UCS) is a search algorithm that:

 Expands the node with the lowest path cost

 Always chooses the cheapest path so far, not the shallowest one

Key idea

“Go where the total cost is minimum.”

UCS is like BFS with costs.

Data structure used

 Priority Queue

 Nodes are ordered by total path cost (g(n))

7
Simple example

Consider this graph (numbers are step costs):

/ \

(1)B C(5)

\ /

(1)D

Goal node: D
Start node: A

Step-by-step UCS execu on

1. Start at A (cost = 0)

2. Add neighbors to priority queue:

o B (cost = 1)

o C (cost = 5)

3. Expand B (lowest cost = 1)

4. From B, go to D:

o Total cost = 1 + 1 = 2

5. Priority queue now has:

o D (cost = 2)

o C (cost = 5)

6. Expand D → Goal reached

UCS result

 Path: A → B → D

 Total cost: 2 (cheapest path)

Even though C is closer in depth, UCS ignores it because the cost is higher.

Algorithm steps (simple)

1. Insert start node into priority queue with cost 0

2. Repeat un l queue is empty:

8
 o Remove node with lowest cost

o If it is goal, stop

o Expand it and update costs of neighbors

3. Con nue un l goal is found

Proper es of Uniform Cost Search

1. Completeness

Complete

 UCS will find a solu on if one exists

 Works even with varying step costs (as long as costs are posi ve)

2. Op mality

Op mal

 Guarantees lowest-cost path

 Always expands the cheapest node first

3. Handles varying step costs

Yes

 Works when different ac ons have different costs

 BFS fails in such cases, UCS succeeds

Advantages of UCS

✔ Finds op mal (least-cost) solu on

✔ Works with unequal costs
✔ Complete and reliable

Disadvantages of UCS

✖ Can be slow
✖ High memory usage
✖ Expands many nodes with small costs

Quick comparison

BFS UCS

Equal costs only Unequal costs

9
 Shallowest first Cheapest first

Uses queue Uses priority queue

4.4 Depth Limited Search (DLS)

 DFS with a predefined depth limit.

 Avoids infinite depth problems.

Limita on: May miss solu on beyond limit.

Detailed Explana on:

What is Depth Limited Search?

Depth Limited Search (DLS) is a modified version of Depth First Search (DFS) where a maximum
depth limit (L) is predefined.
The search algorithm explores nodes depth-wise only up to the given limit and does not go beyond
it.

This helps prevent DFS from going infinitely deep in cases where the search space is very large or
infinite.

Key Idea

 Perform DFS

 Stop expanding a node when depth = limit

 If the goal is not found within the limit, return cutoff/failure

How DLS Works

1. Start from the root node (depth = 0)

2. Expand nodes depth-first

3. If the current depth equals the predefined limit:

o Do not expand further

o Backtrack

4. Con nue un l:

o Goal is found, or

o All nodes within the depth limit are explored

Example:

10
Simple Example (AI Search Tree)

Suppose we have the following tree and the depth limit L = 2:

Search Process

 Start at A

 Go to B → D → E

 Backtrack to C → F

 G is at depth 3, but depth limit = 2

Result:
DLS fails to find the goal because it lies beyond the depth limit

Why Use DLS?

 Avoids infinite depth problems (unlike plain DFS)

 Useful when:

11
 o Maximum depth of solu on is known

o Memory is limited

Advantages of DLS

✔ Prevents infinite loops

✔ Requires less memory than BFS
✔ Simple to implement
✔ Efficient for shallow solu ons

Limita ons of DLS

May miss the solu on if it lies beyond the depth limit

Choosing the correct depth limit is difficult
Not complete if the limit is too small
Not op mal (may not find shortest path)

Summary

 DLS = DFS + Depth Limit

 Solves infinite depth issues

 Success depends heavily on the chosen limit

4.5 Itera ve Deepening Search (IDS)

 Repeatedly applies DLS with increasing depth.

 Combines advantages of BFS and DFS.

Proper es:

 Complete: Yes

 Op mal: Yes (for unit cost)

 Space Complexity: Low like DFS

Explana on in Details:

What is Itera ve Deepening Search?

Itera ve Deepening Search (IDS) is a search strategy that repeatedly applies Depth Limited Search
(DLS) with increasing depth limits un l the goal is found.

It combines the memory efficiency of DFS and the completeness of BFS.

12
Key Idea

 Run DLS with depth = 0

 If goal not found → increase depth to 1

 Repeat un l the goal is found

How IDS Works

1. Start with depth limit = 0

2. Perform DLS

3. If goal not found:

o Increase depth limit by 1

o Run DLS again from the root

4. Con nue un l:

o Goal is found, or

o Search space is exhausted

Simple Example (AI Search Tree)

IDS Execu on

Itera on Depth Limit Nodes Explored

1 0 A

2 1 A→B→C

13
Itera on Depth Limit Nodes Explored

3 2 A→B→D→E→C→F

4 3 A → B → D → E → C → F → G (Goal)

Goal found at depth 3

Why IDS is Effec ve

 Does not go infinitely deep like DFS

 Does not consume high memory like BFS

 Guarantees finding a solu on if it exists

Proper es of Itera ve Deepening Search

Completeness

✔ Complete

 IDS will find a solu on if one exists in a finite search space.

Op mality

✔ Op mal (for unit step cost)

 Finds the shallowest solu on, just like BFS.

Space Complexity

✔ Low (like DFS)

 Stores only a single path from root to leaf.

 Space complexity: O(b × d)

where
b = branching factor
d = depth of the solu on

Time Complexity

 O(bᵈ)

 Some nodes are re-expanded, but the overhead is small compared to BFS.

Advantages of IDS

14
✔ Complete and op mal
✔ Low memory usage
✔ Avoids infinite depth problems
✔ Best choice when solu on depth is unknown

Disadvantages of IDS

Repeated node expansion

Slightly more computa on than BFS

Summary

 IDS = Repeated DLS with increasing depth

 Combines BFS accuracy and DFS efficiency

 Ideal when depth of solu on is unknown

4.6 Bidirec onal Search

 Searches forward from ini al state and backward from goal state.

 Stops when two searches meet.

Proper es:

 Time Complexity: 𝑂(𝑏 /

)

 Requires ability to generate predecessors.

Explain in Details:

Bidirec onal Search (in Ar ficial Intelligence)

15
Bidirec onal Search is a search strategy where:

 One search starts from the ini al state

 Another search starts from the goal state

 The algorithm stops when both searches meet

Simple Example

Imagine a robot moving through rooms:

Room A → Room B → Room C → Room D → Room E

 Ini al state: Room A

 Goal state: Room E

Step 1: Forward Search (from start)

 Start at Room A

 Move to Room B

 Move to Room C

Step 2: Backward Search (from goal)

 Start at Room E

 Move to Room D

 Move to Room C

Step 3: Mee ng Point

Both searches reach Room C.

So the search stops here.

Final Path Found

Room A → Room B → Room C → Room D → Room E

Why Bidirec onal Search is Efficient

 Each search explores half the path

 Fewer states are expanded compared to one-direc onal search

 Faster for large search spaces

16
5. Heuris c Search
Heuris c Func on 𝒉(𝒏)

 Es mates the cost from node n to the goal.

 Helps guide informed search.

Proper es of Heuris cs:

 Admissible: Never overes mates cost.

 Consistent: Sa sfies triangle inequality.

Detailed explana on:

Heuris c Search uses extra knowledge (a heuris c) to decide which node to explore next, instead of
searching blindly.

Heuris c Func on: h(n)

 h(n) = es mated cost from node n to the goal

 It guides the search toward the goal faster

Think of it as a hint or distance guess.

Simple Example (Map / Path Finding)

Imagine a robot wants to go from Start (S) to Goal (G).

Each step costs 1.

Heuris c Values h(n)

(es mated distance to Goal G)

h(S) = 3

h(A) = 2

h(B) = 1

17
h(C) = 2

h(G) = 0

Diagram with Heuris c Values

How Heuris c Search Works

 The algorithm chooses the node with the lowest h(n)

 Moves closer to the goal using the es mate

 Reaches the goal faster than uninformed search

Proper es of Heuris cs

1. Admissible Heuris c

A heuris c is admissible if:

It never overes mates the true cost to reach the goal

✔ Example:

 True cost from A to G = 2

 h(A) = 2 or 1 → ✔ admissible

 h(A) = 3 → not admissible

Why it ma ers:
Guarantees op mal solu on (used in A* search)

2. Consistent (Monotonic) Heuris c

A heuris c is consistent if it sa sfies the triangle inequality:

h(n) ≤ cost(n, n') + h(n')

Simple Meaning:

18
The es mated cost from n to the goal should not be more than
going to a neighbor n' plus that neighbor’s es mate.

✔ Example:

h(A) = 2

cost(A → B) = 1

h(B) = 1

2≤1+1 ✔

6. Informed Search Algorithms

6.1 Best First Search

 Expands node with lowest heuris c value.

 Evalua on func on:

𝑓(𝑛) = ℎ(𝑛)

Pros: Fast
Cons: Not op mal, may be incomplete

Explana on:

19
Best First Search is an informed search algorithm that:

 Always expands the node with the lowest heuris c value

 Tries to go closest to the goal first

Evalua on Func on

f(n) = h(n)

(only the heuris c is considered, not the path cost)

Simple Example

A robot wants to reach the Goal (G) from Start (S).

S —— A —— G

\—— B —— C —— G

Heuris c Values h(n)

(es mated distance to Goal)

h(S) = 4

h(A) = 2

h(B) = 1

h(C) = 3

h(G) = 0

Diagram with Heuris c Values

A (h=2) —— G (h=0)

S (h=4)

B (h=1) —— C (h=3) —— G (h=0)

How Best First Search Works

1. Start at S

2. Compare neighbors:

20
 o A → h=2

o B → h=1 (smallest)

3. Expand B

4. Move to C

5. Finally reach G

The algorithm always picks the node that looks closest to the goal, based only on h(n).

Important Observa on

 The path chosen may be longer

 The algorithm ignores actual path cost

 It is greedy

Pros and Cons

Pros

 Fast

 Explores fewer nodes

 Good when a quick solu on is needed

Cons

 Not op mal (may not find shortest path)

 May be incomplete (can get stuck in loops or dead ends)

6.2 A* Search

 Combines path cost and heuris c.

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

Where:

 𝑔(𝑛)= cost from start to node n

 ℎ(𝑛)= es mated cost to goal

Proper es:

 Complete: Yes

21
  Op mal: Yes (with admissible heuris c)

 Widely used in AI.

Example:

6.3 Itera ve Deepening A* (IDA*)

 Combines A* and itera ve deepening.

 Uses cost limit instead of depth limit.

Proper es:

 Less memory than A*

 Op mal with admissible heuris c

22
Detailed explana on:

What is the Itera ve Deepening A* (IDA*) Algorithm?

IDA* is a variant of depth-first search (DFS) that itera vely deepens its search by incremen ng the cost
threshold, which controls the depth of the explora on. Unlike A*, which explores all possible nodes
within a threshold, IDA* uses a heuris c func on to evaluate and priori ze the most promising nodes.
This allows it to prune less promising paths, reducing memory usage while ensuring that the search
focuses on op mal routes.

Key Features of IDA* Algorithm

1. Graph Traversal Algorithm: IDA* explores a graph by progressively deepening the search
depth.

2. Shortest Pathfinding: It efficiently finds the shortest path in a weighted graph using a
combina on of DFS and A* techniques.

3. Admissible Heuris c: The heuris c func on in IDA* ensures that the es mated cost never
exceeds the actual cost, making it an admissible heuris c.

4. Memory Efficiency: As a depth-first search algorithm, IDA* uses far less memory compared
to the tradi onal A* algorithm.

5. Focused Search: The algorithm is designed to explore only the most promising nodes,
ensuring it doesn’t go to unnecessary depths.

How the IDA* Algorithm Works?

The IDA* algorithm works by incrementally increasing the threshold based on the f-score of each
node, which is calculated using the formula:

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

𝑓(𝑛) = Actualcost + Es mated cost
Where h is admissible.

Here,

 f(n) = Total cost evalua on func on.

 g(n) = The actual cost from the ini al node to the current node.

 h(n) = Heuris c es mated cost from the current node to the goal state. it is based on the
approxima on according to the problem characteris cs.

What is the F-score?

In the IDA* algorithm, F-score is a heuris c func on that is used to es mate the cost of reaching the
goal state from a given state. It is a combina on of two other heuris c func ons, g(n) and h(n).
It is used to determine the order in which the algorithm expands nodes in the search tree and thus, it
plays an important role in how quickly the algorithm finds a solu on.

23
A lower F-score indicates that a node is closer to the goal state and will be expanded before a node
with a higher F-score. Simply it is nothing but g(n) + h(n).

Step-by-Step Process of the IDA* Algorithm

1. Ini aliza on: Set the root node as the current node and compute its f-score.

2. Set Threshold: Ini alize a threshold based on the f-score of the star ng node.

3. Node Expansion: Expand the current node’s children and calculate their f-scores.

4. Pruning: If the f-score exceeds the threshold, prune the node and store it for future
explora on.

5. Path Return: Once the goal node is found, return the path from the start node to the goal.

6. Update Threshold: If the goal is not found, increase the threshold based on the minimum
pruned value and repeat the process.

Example of IDA* Algorithm

In the below tree, the f score is wri en inside the nodes means the f score is already computed and
the start node is 2 whereas the goal node is 15. the explored node is colored green color.

So now we have to go to a given goal by using IDA* algorithm.

Itera on 1

Itera on 1

 Root node as current node i.e 2

 Threshold = current node value (2=2). So explore its children.

 4 > Threshold & 5>Threshold. So, this itera on is over and the pruned values are 4, and 5.

Itera on 2

24
Itera on 2

 In pruned values, the least is 4, So threshold = 4

 current node = 2 and 2< threshold, So explore its children. i.e two children explore one by one

 So, first children 4, So, set current node = 4 i.e equal to the threshold, so, explored its children
also i.e 5, 4 having 5> threshold so, pruned it and explore second child of node 4 i.e 4, so set
current node = 4 = threshold, and explore its children i.e 8 & 7 having both 8 & 7 > threshold
so, pruned it. At the end of this, our pruned value is 5,8,7

 Similarly, Explore the second child of root node 2 i.e 5 as the current node, i.e 5>threshold, So
pruned it.

 So, our pruned value is 5,8,7.

Itera on 3

Itera on 3

 In pruned values, the least is 5, So threshold = 5

25
  current node = root node = 2 and 2< threshold, So explore its children. i.e two children explore
one by one

 So, first children 4, So, set current node = 4 < threshold, so, explored its children also i.e 5, 4
having 5= threshold so explore its child also 7&8 > threshold. So, pruned it and explore the
second child of node 4 i.e 4, so set current node = 4 < threshold, and explore its children i.e 8
& 7 here, both 8 & 7 > threshold so, pruned it. At the end of this, our pruned value is 7 & 8

 Similarly, Explore the second child of root node 2 i.e 5 as the current node, i.e 5 = threshold,
so, explored its children also i.e 6 & 6, i.e both 6 & 6 > threshold. So pruned it

 So, our pruned value is 7,8 & 6

Itera on 4

 In pruned values, the least value is 6, So threshold = 6

 current node = root node = 2 and 2< threshold, So explore its children. i.e two children explore
one by one

 So, the first child is 4, So, set current node = 4 < threshold, so, explored its children also i.e 5,
4 having 5< threshold so explore its child also 7&8 > threshold. So, pruned it and explore the
second child of node 4 i.e 4, so set current node = 4 < threshold, and explore its children i.e 8
& 7 here, both 8 & 7 > threshold so, pruned it. At the end of this, our pruned value is 7 & 8

 Similarly, Explore the second child of root node 2 i.e 5 as the current node, i.e 5 = threshold,
so, explored its children also i.e 6 & 6, i.e both 6 & 6 = threshold, So, explore one by one,

 The first 6 has two children i.e 6 & 8, having 6 = threshold. So, explore its child also i.e 13 & 7.
here both 13 & 7 > Threshold. So, pruned it. next is 8 > Threshold. pruned it, So, pruned value
at this stage is 13,7 & 8.

 Explore the second child of 5 i.e 6 = Threshold. So, explore its child i.e 7 & 9. Both are greater
than Threshold. So, pruned it

 So, our pruned values are 13,7,8 & 9.

Itera on 5

26
  In pruned values, the least value is 7, So threshold = 7

 current node = root node = 2 and 2< threshold, So explore its children. i.e two children explore
one by one

 So, the first child is 4, So, set current node = 4 < threshold, so, explored its children also i.e 5,
4

 The first child of 4 is 5 i.e 5< threshold so explore its child also 7&8, Here 7 = threshold. So,
explore its children i.e 12 & 14, both > Threshold. So, pruned it. And the second child of 5 is 8
> Threshold, So, pruned it. At this stage, our pruned value is 12, 14 & 7.

 Now explore the second child of node 4 i.e 4, so set current node = 4 < threshold, and explore
its children i.e 8 & 7 here, 8 > threshold so, pruned it. then go to the second child i.e 7 =
Threshold, So explore its children i.e 13 & 8. having both > Threshold. So pruned it. At the end
of this, our pruned value is 12,14,8 & 13

 Similarly, Explore the second child of root node 2 i.e 5 as the current node, i.e 5 < threshold,
so, explored its children also i.e 6 & 6, i.e both 6 & 6 < threshold, So, explore one by one,

 The first 6 has two children i.e 6 & 8, having 6 < threshold. So, explore its child also i.e 13 & 7.
here 13 > Threshold. So, pruned it. And 7= Threshold. And it hasn't any child. So, the shi to
the next sub-child of 6 i.e 8 > threshold, So, pruned it. The pruned value at this stage is 12,14,8
&13

 Explore the second child of 5 i.e 6 < Threshold. So, explore its child i.e 7 & 9. Here 7 = Threshold,
So, explore its children i.e 8 & 14, Both are greater than Threshold. So, pruned it, Now the sub
child of 6 is 9 > Threshold, So, pruned it.

 So, our pruned values are 12,14,8,13 & 9.

Itera on 6

27
Itera on 6

 In pruned values, the least value is 8, So threshold = 8

 current node = root node = 2 and 2< threshold, So explore its children. i.e two children explore
one by one

 So, the first child is 4, So, set current node = 4 < threshold, so, explored its children also i.e 5,
4

 The first child of 4 is 5 i.e 5< threshold so explore its child also 7&8, Here 7 < threshold. So,
explore its children i.e 12 & 14, both > Threshold. So, pruned it. And the second child of 5 is 8
= Threshold, So, So, explore its children i.e 16 & 15, both > Threshold. So, pruned it. At this
stage, our pruned value is 12, 14, 16 & 15.

 Now explore the second child of node 4 i.e 4, so set current node = 4 < threshold, and explore
its children i.e 8 & 7 here, 8 = Threshold, So, So, explore its children i.e 12 & 9, both >
Threshold. So, pruned it. then go to the second child i.e 7 < Threshold, So explore its children
i.e 13 & 8. having 13 > Threshold. So pruned it. and 8 = Threshold and it hasn't any child. At
the end of this, our pruned values are 12, 14, 16, 15, and 13.

 Similarly, Explore the second child of root node 2 i.e 5 as the current node, i.e 5 < threshold,
so, explored its children also i.e 6 & 6, i.e both 6 & 6 < threshold, So, explore one by one,

 The first 6 has two children i.e 6 & 8, having 6 < threshold. So, explore its child also i.e 13 & 7.
here 13 > Threshold. So, pruned it. And 7<Threshold. And it hasn't any child. So, the shi to
the next sub-child of 6 i.e 8 = threshold. So, explored its children also i.e 15 & 16, Here 15 =
Goal Node. So, stop this itera on. Now no need to explore more.

 The goal path is 2-->5-->6-->8-->15

Real-World Applica ons of IDA*

1. The 15-Puzzle Problem

The 15-puzzle problem is a classic example of a sliding puzzle game. It consists of a 4x4 grid of
numbered les with one le missing. The aim is to rearrange the les to form a specific goal
configura on. The state space of the puzzle can be represented as a tree where each node represents

28
a configura on of the puzzle and each edge represents a legal move. IDA* can be used to find
the shortest sequence of moves to reach the goal state from the ini al state.

2. The 8-Queens Problem

The 8-Queens problem is a classic example of the n-Queens problem where n queens have been
placed on an n x n chessboard such that no two queens a ack each other. The state space of the
problem can be represented as a tree where each node represents a configura on of the chessboard
and each edge represents the placement of a queen. IDA* can be used to find the minimum number
of queens that need to be moved to reach the goal state.

In both of these examples, IDA* is used to find the op mal solu on by using a combina on of depth-
first search and a heuris c func on to limit the search space. The algorithm incrementally increases
the depth bound, allowing it to find the solu on without exploring the en re state space, which would
be infeasible for larger problems.

Advantages and Disadvantages of Itera ve Deepening A* algorithm (IDA*)

Advantages

1. Op mal Pathfinding: IDA* guarantees finding the op mal path, as it never overes mates the
cost to the goal.

2. Memory Efficient: It uses limited memory compared to A* by applying depth-first search

techniques.

3. Admissible Heuris c: The heuris c func on ensures that the algorithm remains admissible,
thus op mizing performance.

4. Efficient with Large State Spaces: IDA* handles large graphs efficiently by pruning unnecessary
nodes.

Disadvantages

1. Repeated Node Explora on: The algorithm does not store visited nodes, leading to repeated
explora on.

2. Slower than A*: IDA* can be slower than algorithms like A* due to the repeated explora on
of nodes.

3. Higher Computa onal Cost: It may take longer and consume more processing power
compared to other algorithms like A* or breadth-first search.

It's important to note that IDA* is not suitable for all types of problems, and the choice of algorithm
will depend on the specific characteris cs of the problem you're trying to solve.

IDA* vs Itera ve Deepening Depth-First Search (IDDFS)

The table given below highlights the differences between IDA* and Itera ve Deepening Depth-First
Search (IDDFS):

29
 Itera ve Deepening Depth-
Criteria First Search (IDDFS) Itera ve Deepening A (IDA)**

Systema c explora on of the Not systema c; may revisit nodes due

Systema c
search space. to threshold updates.

Guarantees op mal solu on in Op mal, but only expands nodes

Op mality
unweighted graphs. where f-score ≤ threshold.

Never expands the same node May expand the same node mul ple
Node Expansion
twice. mes if f-score < threshold.

Handling Infinite Not suited for infinite search Be er suited for infinite search
Search Traversal traversal. traversal compared to IDDFS.

Applica ons of IDA* in Ar ficial intelligence

IDA* is par cularly suited for solving complex AI problems where memory is limited. Here are a few
areas where it is commonly applied:

1. Pathfinding in Games: IDA* is frequently used in video games where memory is a constraint,
and op mal paths need to be found efficiently, such as in real- me strategy games.

2. Robot Naviga on: In robo cs, IDA* is applied to efficiently navigate through complex
environments without requiring excessive memory.

3. Puzzle Solving: Classic AI problems like the 8-puzzle or 15-puzzle can be solved using IDA*,
where the search space is large and memory constraints are significant.

4. Ar ficial General Intelligence (AGI): In research areas exploring AGI, where problem-solving
o en involves naviga ng vast search spaces, IDA* can be used to manage memory while
finding op mal solu ons.

Conclusion

The Itera ve Deepening A (IDA*) algorithm* strikes a balance between memory

efficiency and op mal pathfinding by combining the strengths of depth-first search and heuris c
func ons. It prunes unpromising paths, allowing it to handle larger state spaces than tradi onal
algorithms. While IDA* might not be the fastest op on, its ability to find the op mal solu on while
using less memory makes it an excellent choice for solving problems like the 15-puzzle and n-
Queens problems. It’s a robust solu on for graph traversal and pathfinding when memory efficiency
is a concern.

30
6.4 Simplified Memory-Bounded A* (SMA*)

 Memory-limited version of A*.

 Discards worst nodes when memory is full.

Proper es:

 Op mal if enough memory

 More prac cal for large problems

Example:

7. Comparison of Search Techniques

Algorithm Complete Op mal Time Space

BFS Yes Yes High High
DFS No No Low Low
UCS Yes Yes High High
IDS Yes Yes Medium Low
A* Yes Yes High High
IDA* Yes Yes Medium Low
SMA* Yes Yes* Medium Limited
*Op mal if memory is sufficient

31