Uninformed Search Algorithms:
Uninformed search algorithms are also known as blind search algorithms are a class of search
algorithms that do not use any domain-specific knowledge about the problem being solved.
Uninformed search algorithms rely on the information provided in the problem definition,
such as the initial state, actions available in each state, and the goal state.
These are called "blind" because they do not have a heuristic function to guide the search
towards the goal instead; they explore the search space systematically.
Uninformed search algorithms provide basic search strategies for exploring problem spaces
where no additional knowledge is available beyond the problem definition.
These algorithms are important for solving a wide range of problems in AI, such as path
finding, puzzle solving, and state-space search.
The main types of uniform search strategies include:
Breadth-First Search (BFS):
This algorithm explores the search space level by level, expanding all nodes at a given depth
before moving to the next depth. It guarantees finding the shortest path in terms of the number
of edges if one exists.
Depth-First Search (DFS):
This algorithm explores as deeply as possible along each branch before backtracking. It is
memory-efficient but does not guarantee finding the shortest path.
Uniform-Cost Search (UCS):
This algorithm expands nodes in order of their accumulated path cost from the start node. It
uses a priority queue to prioritize nodes with the lowest path cost, guaranteeing the optimal
(least-cost) path when edge costs are non-negative.
Depth-Limited Search (DLS):
This is a variation of DFS that introduces a depth limit, preventing the search from going
infinitely deep in cyclic graphs or very large search spaces.
Iterative Deepening Depth-First Search (IDDFS):
This combines the advantages of DFS (memory efficiency) and BFS (completeness and
optimality for shortest paths). It performs a series of DLS searches with increasing depth
limits.
Bidirectional Search:
This strategy conducts two simultaneous searches, one forward from the start node and one
backward from the goal node, meeting in the middle. This can significantly reduce the search
space in certain problems.
BFS algorithm:
Initialization:
Choose a starting node (source node) from which to begin the traversal.
Create an empty queue and add the starting node to it.
Mark the starting node as "visited" to prevent revisiting it and creating infinite loops in cyclic
graphs. A common way to do this is using a boolean array or a set.
Traversal:
While the queue is not empty, perform the following:
Dequeue: Remove the node at the front of the queue. This is the current node being
processed.
Process Node: Perform any desired operation on the dequeued node (e.g., print its value,
check if it's the target node in a search).
Explore Neighbors: For each unvisited neighbor of the current node:
Mark the neighbor as "visited."
Add the neighbor to the end of the queue.
Termination:
The algorithm terminates when the queue becomes empty. This indicates that all reachable
nodes from the starting node have been visited.
If the goal is to find a specific target node, the algorithm can terminate early once the target
node is found and processed.
Step Traversal Description
1 Initialize the queue.
We start from visiting S (starting node), and
2
mark it as visited.
We then see an unvisited adjacent node
from S. In this example, we have three
3
nodes but alphabetically we choose A, mark
it as visited and enqueue it.
Next, the unvisited adjacent node
4 from S is B. We mark it as visited and
enqueue it.
Next, the unvisited adjacent node
5 from S is C. We mark it as visited and
enqueue it.
Now, S is left with no unvisited adjacent
6
nodes. So, we dequeue and find A.
From A we have D as unvisited adjacent
7
node. We mark it as visited and enqueue it.
#Python program for Breadth First Search
# defining MAX 5
MAX = 5
class Vertex:
def __init__(self, label):
self.label = label
self.visited = False
# queue variables
queue = [0] * MAX
rear = -1
front = 0
queueItemCount = 0
# graph variables
#array of vertices
lstVertices = [None] * MAX
#adjacency matrix
adjMatrix = [[0] * MAX for _ in range(MAX)]
#vertex count
vertexCount = 0
# queue functions
def insert(data):
global rear, queueItemCount
rear += 1
queue[rear] = data
queueItemCount += 1
def removeData():
global front, queueItemCount
queueItemCount -= 1
data = queue[front]
front += 1
return data
def isQueueEmpty():
return queueItemCount == 0
# graph functions
#add vertex to the vertex list
def addVertex(label):
global vertexCount
vertex = Vertex(label)
lstVertices[vertexCount] = vertex
vertexCount += 1
#add edge to edge array
def addEdge(start, end):
adjMatrix[start][end] = 1
adjMatrix[end][start] = 1
#Display the vertex
def displayVertex(vertexIndex):
print(lstVertices[vertexIndex].label, end=" ")
#Get the adjacent unvisited vertex
def getAdjUnvisitedVertex(vertexIndex):
for i in range(vertexCount):
if adjMatrix[vertexIndex][i] == 1 and not lstVertices[i].visited:
return i
return -1
def breadthFirstSearch():
#mark first node as visited
lstVertices[0].visited = True
#Display the vertex
displayVertex(0)
#insert vertex index in queue
insert(0)
while not isQueueEmpty():
#get the unvisited vertex of vertex which is at front of the queue
tempVertex = removeData()
#no adjacent vertex found
unvisitedVertex = getAdjUnvisitedVertex(tempVertex)
while unvisitedVertex != -1:
lstVertices[unvisitedVertex].visited = True
displayVertex(unvisitedVertex)
insert(unvisitedVertex)
unvisitedVertex = getAdjUnvisitedVertex(tempVertex)
#queue is empty, search is complete, reset the visited flag
for i in range(vertexCount):
lstVertices[i].visited = False
# main function
if __name__ == "__main__":
#set adjacency
for i in range(MAX):
#matrix to 0
for j in range(MAX):
adjMatrix[i][j] = 0
addVertex('S')
addVertex('A')
addVertex('B')
addVertex('C')
addVertex('D')
addEdge(0, 1)
addEdge(0, 2)
addEdge(0, 3)
addEdge(1, 4)
addEdge(2, 4)
addEdge(3, 4)
print("Breadth First Search: ", end="")
breadthFirstSearch()
OUTPUT:
Breadth First Search: S A B C D
DFS Algorithm (Iterative Approach):
Initialization:
Create an empty stack to store nodes to be visited.
Create a set or array to keep track of visited nodes to prevent cycles and redundant
processing.
Choose a starting node for the traversal.
Start Traversal:
Push the starting node onto the stack.
Mark the starting node as visited.
Iterative Exploration:
While the stack is not empty:
Pop the top node from the stack. This is the current node being processed.
Process the current node: Perform any desired operation on this node (e.g., print its value,
add it to a traversal list, check if it's a target node).
Explore Neighbors: For each unvisited neighbor of the current node:
Mark the neighbor as visited.
Push the neighbor onto the stack.
Completion:
The algorithm terminates when the stack becomes empty, indicating that all reachable nodes
from the starting point have been visited. If the graph is disconnected, you might need to
repeat the process from other unvisited starting nodes to visit all components.
Step Traversal Description
1 Initialize the stack.
Mark S as visited and put it onto the stack.
Explore any unvisited adjacent node from S.
2 We have three nodes and we can pick any of
them. For this example, we shall take the
node in an alphabetical order.
Mark A as visited and put it onto the stack.
Explore any unvisited adjacent node from A.
3
Both S and D are adjacent to A but we are
concerned for unvisited nodes only.
Visit D and mark it as visited and put onto
the stack. Here, we have B and C nodes,
4 which are adjacent to D and both are
unvisited. However, we shall again choose in
an alphabetical order.
We choose B, mark it as visited and put onto
the stack. Here B does not have any
5
unvisited adjacent node. So, we pop B from
the stack.
We check the stack top for return to the
previous node and check if it has any
6
unvisited nodes. Here, we find D to be on
the top of the stack.
Only unvisited adjacent node is
7 from D is C now. So we visit C, mark it as
visited and put it onto the stack.
As C does not have any unvisited adjacent node so we keep popping the stack until we find a node that has
an unvisited adjacent node. In this case, there's none and we keep popping until the stack is empty.
#Python program for Depth First Traversal
MAX = 5
class Vertex:
def __init__(self, label):
self.label = label
self.visited = False
#stack variables
stack = []
top = -1
#graph variables
#array of vertices
lstVertices = [None] * MAX
#adjacency matrix
adjMatrix = [[0] * MAX for _ in range(MAX)]
#vertex count
vertexCount = 0
#stack functions
def push(item):
global top
top += 1
stack.append(item)
def pop():
global top
item = stack[top]
del stack[top]
top -= 1
return item
def peek():
return stack[top]
def isStackEmpty():
return top == -1
#graph functions
#add vertex to the vertex list
def addVertex(label):
global vertexCount
vertex = Vertex(label)
lstVertices[vertexCount] = vertex
vertexCount += 1
#add edge to edge array
def addEdge(start, end):
adjMatrix[start][end] = 1
adjMatrix[end][start] = 1
#Display the Vertex
def displayVertex(vertexIndex):
print(lstVertices[vertexIndex].label, end=' ')
def getAdjUnvisitedVertex(vertexIndex):
for i in range(vertexCount):
if adjMatrix[vertexIndex][i] == 1 and not lstVertices[i].visited:
return i
return -1
def depthFirstSearch():
lstVertices[0].visited = True
displayVertex(0)
push(0)
while not isStackEmpty():
unvisitedVertex = getAdjUnvisitedVertex(peek())
if unvisitedVertex == -1:
pop()
else:
lstVertices[unvisitedVertex].visited = True
displayVertex(unvisitedVertex)
push(unvisitedVertex)
for i in range(vertexCount):
lstVertices[i].visited = False
for i in range(MAX):
for j in range(MAX):
adjMatrix[i][j] = 0
addVertex('S') # 0
addVertex('A') # 1
addVertex('B') # 2
addVertex('C') # 3
addVertex('D') # 4
addEdge(0, 1) # S - A
addEdge(0, 2) # S - B
addEdge(0, 3) # S - C
addEdge(1, 4) # A - D
addEdge(2, 4) # B - D
addEdge(3, 4) # C - D
print("Depth First Search:", end=' ')
depthFirstSearch()
OUTPUT:
Depth First Search: S A D B C
Heuristic Search Techniques:
Informed Search Algorithms
Informed search algorithms are a class of search algorithms that use heuristic information—
domain-specific knowledge—to guide the search process toward the goal more efficiently than
uninformed (blind) methods.
They evaluate nodes by estimating the cost to reach the goal from a given state, which helps
prioritize which paths are likely to lead to an optimal solution.
Definition of Heuristic Search
Heuristic search is a type of informed search that uses a heuristic function to estimate how close
a state is to the goal. It helps the algorithm make intelligent decisions by choosing paths that appear
more promising, reducing the overall search time.
Key Idea:
Heuristic search uses domain-specific knowledge to prioritize which nodes to explore first based
on a heuristic value h(n).
Heuristic Function h(n)
Definition:
A heuristic function h(n) is a function that estimates the cost of the cheapest path from a node n
to the goal.
h(n):Estimated cost from node n to the goal
Underestimate (Admissible Heuristic):
Definition:
A heuristic underestimates if it always returns a value less than or equal to the actual cost to reach
the goal from node n.
h(n)≤h∗(n)
Where h∗(n) is the true cost from n to the goal.
Example:
In a GPS routing problem, if the straight-line distance between two cities is used as the
heuristic, it usually underestimates the actual driving distance (since roads don’t go
perfectly straight).
Effects:
Guarantees optimality in A*.
May cause the algorithm to explore more nodes than necessary (less efficient), but ensures
correct results.
Overestimate (Non-Admissible Heuristic):
Definition:
A heuristic overestimates if it exceeds the actual cost to reach the goal from node n.
h(n)>h∗(n)
Example:
If a GPS app uses a heuristic that adds extra distance assuming traffic, even when there's
none, it may overestimate the travel cost.
Effects:
May lead the algorithm to miss the optimal path.
Not guaranteed to be optimal in A*.
Might be faster in practice but sacrifices accuracy.
A* (A-Star) Search Algorithm
A* is one of the most powerful and widely used informed search algorithms. It finds the shortest
(optimal) path from a start node to a goal node using both the actual cost so far and an estimated
cost to the goal.
Definition:
A* search finds the path from the start node to the goal node by minimizing the total estimated cost:
f(n)=g(n)+h(n)
Where:
g(n):
The actual cost of the path from the starting node to the current node 'n'.
h(n):
The estimated cost (heuristic) from the current node 'n' to the goal node. This estimate must
be admissible, meaning it never overestimates the actual cost to reach the goal. Common
heuristics include Manhattan distance, Euclidean distance, or Diagonal distance, depending
on the problem domain.
f(n): total estimated cost of the path through n
How It Works (Step-by-Step):
1. Initialize an open list (priority queue) and add the start node.
2. Loop until goal is found or open list is empty:
o Pick the node with the lowest f(n) from the open list.
o If it's the goal, return the path.
o Otherwise:
Expand it (generate its successors).
For each successor:
Calculate g(n), h(n), and f(n).
Add to the open list if not already there or if a better path is found.
