Amrita Vishwa Vidyapeetham

Amrita School of Computing, Bangalore

B. Tech. Degree Fifth Semester (AI/CSE)
19CSE451 –Principles of AI

PART I – Uninformed Search

Introduction: Uninformed search is a class of general-purpose search algorithms which
operates in brute force-way. Uninformed search algorithms do not have additional
information about state or search space other than how to traverse the tree, so it is also called
blind search.

Lab Program 1 : Implementation of Breadth First Search Algorithm

Basic Information:
o Breadth-first search is the most common search strategy for traversing a tree or graph.
This algorithm searches breadthwise in a tree or graph, so it is called breadth-first
search.
o BFS algorithm starts searching from the root node of the tree and expands all successor
node at the current level before moving to nodes of next level.
o The breadth-first search algorithm is an example of a general-graph search algorithm.
o Breadth-first search implemented using FIFO queue data structure.

Advantages:

o BFS will provide a solution if any solution exists.

o If there are more than one solution for a given problem, then BFS will provide the
minimal solution which requires the least number of steps.

Disadvantages:

o It requires lots of memory since each level of the tree must be saved into memory to
expand the next level.
o BFS needs lots of time if the solution is far away from the root node.

Algorithm

Breadth-first search is the process of traversing each node of the graph, a standard BFS
algorithm traverses each vertex of the graph into two parts: 1) Visited 2) Not Visited. So,
the purpose of the algorithm is to visit all the vertex while avoiding cycles.

BFS starts from a node, then it checks all the nodes at distance one from the beginning
node, then it checks all the nodes at distance two, and so on. So as to recollect the nodes
to be visited, BFS uses a queue.
The steps of the algorithm work as follow:

1. Start by putting any one of the graph’s vertices at the back of the queue.
2. Now take the front item of the queue and add it to the visited list.
3. Create a list of that vertex's adjacent nodes. Add those which are not within the
visited list to the rear of the queue.
4. Keep continuing steps two and three till the queue is empty.

The pseudocode for BFS in python goes as below:

create a queue Q

mark v as visited and put v into Q

while Q is non-empty

remove the head u of Q

mark and enqueue all (unvisited) neighbours of u

Implementation

graph = {
'5’: ['3','7'],
'3’: ['2', '4'],
'7’: ['8'],
'2’: [],
'4’: ['8'],
'8’: []
}

visited = [] # List for visited nodes.

queue = [] #Initialize a queue
def bfs(visited, graph, node): #function for BFS
visited.append(node)
queue.append(node)

while queue: # Creating loop to visit each node

m = queue.pop(0)
print (m, end = " ")

for neighbour in graph[m]:

if neighbour not in visited:
visited.append(neighbour)
queue.append(neighbour)

# Driver Code
print ("Following is the Breadth-First Search")
bfs (visited, graph, '5’) # function calling

Output
Following is the Breadth-First Search
537248

Complexity Analysis
The time complexity of the Breadth first Search algorithm is in the form of O(V+E), where V
is the representation of the number of nodes and E is the number of edges. Also, the space
complexity of the BFS algorithm is O(V).

Completeness: BFS is complete, which means if the shallowest goal node is at some finite
depth, then BFS will find a solution.

Optimality: BFS is optimal if path cost is a non-decreasing function of the depth of the node.

Applications of BFS Algorithm

Breadth-first Search Algorithm has a wide range of applications in the real-world. Some of
them are as discussed below:

1. In GPS navigation, it helps in finding the shortest path available from one point to
another.
2. In pathfinding algorithms
3. Cycle detection in an undirected graph
4. In minimum spanning tree
5. To build index by search index
Lab Program 2 : Implementation of Depth First Search Algorithm

Basic Information:
Depth-first search isa recursive algorithm for traversing a tree or graph data structure.

It is called the depth-first search because it starts from the root node and follows each
path to its greatest depth node before moving to the next path.

DFS uses a stack data structure for its implementation.

The process of the DFS algorithm is similar to the BFS algorithm.

Advantage:

o DFS requires very less memory as it only needs to store a stack of the nodes on the path
from root node to the current node.
o It takes less time to reach to the goal node than BFS algorithm (if it traverses in the
right path).

Disadvantage:

o There is the possibility that many states keep re-occurring, and there is no guarantee of
finding the solution.
o DFS algorithm goes for deep down searching and sometime it may go to the infinite
loop.

Algorithm

The recursive method of the Depth-First Search algorithm is implemented using stack. A
standard Depth-First Search implementation puts every vertex of the graph into one in all 2
categories: 1) Visited 2) Not Visited. The only purpose of this algorithm is to visit all the
vertex of the graph avoiding cycles.

The DSF algorithm follows as:

1. We will start by putting any one of the graph's vertex on top of the stack.
2. After that take the top item of the stack and add it to the visited list of the vertex.
3. Next, create a list of that adjacent node of the vertex. Add the ones which aren't in the
visited list of vertexes to the top of the stack.
4. Lastly, keep repeating steps 2 and 3 until the stack is empty.
DFS pseudocode
The pseudocode for Depth-First Search in python goes as below: In the init() function, notice
that we run the DFS function on every node because many times, a graph may contain two
different disconnected part and therefore to make sure that we have visited every vertex, we
can also run the DFS algorithm at every node.

DFS (G, u)

u.visited = true

for each v ∈ G.Adj[u]

if v.visited == false

DFS(G,v)

init() {

For each u ∈ G

u.visited = false

For each u ∈ G

DFS(G, u)

Implementation
# Using a Python dictionary to act as an adjacency list
graph = {
'5' : ['3','7'],
'3' : ['2', '4'],
'7' : ['8'],
'2' : [],
'4' : ['8'],
'8' : []
}
visited = set () # Set to keep track of visited nodes of graph.

def dfs(visited, graph, node): #function for dfs

if node not in visited:
print (node)
visited.add(node)
for neighbour in graph[node]:
dfs(visited, graph, neighbour)

# Driver Code
print ("Following is the Depth-First Search")
dfs(visited, graph, '5')

Output
The output of the above code is as follow:

Following is the Depth-First Search

532487

Time Complexity
The time complexity of the Depth-First Search algorithm is represented within the sort
of O(V + E), where V is that the number of nodes and E is that the number of edges.
The space complexity of the algorithm is O(V).

Optimal: Depth-limited search can be viewed as a special case of DFS, and it is also not
optimal even if ℓ>d.

Applications
Depth-First Search Algorithm has a wide range of applications for practical purposes. Some
of them are as discussed below:

1. For finding the strongly connected components of the graph

2. For finding the path
3. To test if the graph is bipartite
4. For detecting cycles in a graph
5. Topological Sorting
6. Solving the puzzle with only one solution.
7. Network Analysis
8. Mapping Routes
9. Scheduling a problem
Lab Program 3: Implementation of Depth Limited Search

Basic Information

A depth-limited search algorithm is similar to depth-first search with a predetermined

limit. Depth-limited search can solve the drawback of the infinite path in the Depth-
first search. In this algorithm, the node at the depth limit will treat as it has no successor
nodes further.

Depth-limited search can be terminated with two Conditions of failure:

o Standard failure value: It indicates that problem does not have any solution.
o Cutoff failure value: It defines no solution for the problem within a given depth limit.

Advantages:

Depth-limited search is Memory efficient.

Disadvantages:

o Depth-limited search also has a disadvantage of incompleteness.

o It may not be optimal if the problem has more than one solution.

Algorithm

def dls(graph, start, goal, depth_limit):

Performs Depth-Limited Search (DLS) on a graph.

Args:

graph: A dictionary representing the graph, where keys are nodes and values are
lists of adjacent nodes.

start: The starting node.

goal: The goal node.

depth_limit: The maximum depth to explore.

Returns:

The path from start to goal if found within the depth limit, otherwise None.

"""

def recursive_dls(node, path, depth):

 if node == goal:

return path + [node]

if depth == depth_limit:

return None

for neighbor in graph[node]:

new_path = recursive_dls(neighbor, path + [node], depth + 1)

if new_path:

return new_path

return None

return recursive_dls(start, [], 0)

Implementation

# Example usage

graph = {

'A': ['B', 'C'],

'B': ['D', 'E'],

'C': ['F'],

'D': [],

'E': ['F'],

'F': []

start_node = 'A'

goal_node = 'F'

depth_limit = 2

result = dls(graph, start_node, goal_node, depth_limit)

 if result:

print("Path found:", result)

else:

print("Goal not reachable within depth limit.")

Explanation:
1. dls(graph, start, goal, depth_limit):
• This is the main function that initiates the DLS algorithm.
• It calls the recursive_dls function to perform the actual search.
• It returns the path if found, otherwise None.
2. recursive_dls(node, path, depth):
• This function recursively explores the graph.
• Base Case 1: If the current node is the goal, it returns the path to the goal.
• Base Case 2: If the current depth reaches the depth_limit, it returns None to
indicate a cutoff.
• Recursive Case: It iterates through each neighbor of the current node.
• It calls itself recursively with the neighbor, updated path, and
incremented depth.
• If the recursive call returns a non-None value (i.e., a path), it means a
path to the goal is found, so it returns that path.
• If no path is found from any neighbor, it returns None.

Example Usage:
• The provided example defines a simple graph, a starting node, a goal node, and a
depth limit.
• It calls the dls function and prints the result.
Key Points:
• DLS is a variation of Depth-First Search (DFS) that limits the exploration to a
specified depth.
• It is useful for searching in graphs with large branching factors or infinite depth, as it
prevents the search from getting stuck in endless paths.
• However, it may not find the optimal solution if the goal is deeper than the specified
depth limit.
Lab Program 4: Implementation of Uniform cost search

Basic Information

Uniform-cost search is a searching algorithm used for traversing a weighted tree or graph. This
algorithm comes into play when a different cost is available for each edge. The primary goal
of the uniform-cost search is to find a path to the goal node which has the lowest cumulative
cost. Uniform-cost search expands nodes according to their path costs form the root node. It
can be used to solve any graph/tree where the optimal cost is in demand. A uniform-cost search
algorithm is implemented by the priority queue. It gives maximum priority to the lowest
cumulative cost. Uniform cost search is equivalent to BFS algorithm if the path cost of all edges
is the same.

Advantages:

o Uniform cost search is optimal because at every state the path with the least cost is
chosen.

Disadvantages:

o It does not care about the number of steps involve in searching and only concerned
about path cost. Due to which this algorithm may be stuck in an infinite loop.

Completeness: Uniform-cost search is complete, such as if there is a solution, UCS will find
it.

Optimal: Uniform-cost search is always optimal as it only selects a path with the lowest path
cost.

Explanation:
1. Initialize:
• Create a priority queue frontier and push the starting node with cost 0 and an
empty path.
•Create a set explored to keep track of visited nodes.
2. Explore:
• While the frontier is not empty, pop the node with the lowest cost from the
priority queue.
• If the current node is the goal, return the path and its cost.
• If the current node is already explored, skip it.
• Mark the current node as explored.
• For each neighbor of the current node, calculate the new cost (current cost + edge
cost).
• Push the neighbor, new cost, and updated path to the priority queue.
 3. Return:
• If the goal is reached, return the path and cost.
• If the frontier is empty and the goal is not found, return None, indicating no path
exists.
Key points:
• Priority queue:
Uses a heap to efficiently get the node with the lowest cost.
• Explored set:
Prevents revisiting already explored nodes, ensuring optimality and avoiding infinite
loops.
• Graph representation:
Uses a dictionary where keys are nodes, and values are dictionaries of neighbors and
their corresponding edge costs.
• Path reconstruction:
Stores the path taken to reach each node, allowing easy backtracking to find the
complete path from start to goal.
This implementation assumes:
• All edge costs are non-negative.
• The graph is represented as an adjacency list.
• The goal node is reachable from the start node.

Algorithm

import heapq

def uniform_cost_search(graph, start, goal):

Performs Uniform Cost Search on a graph to find the shortest path.

Args:

graph: A dictionary representing the graph, where keys are nodes and values are
dictionaries of neighbors and their costs.

start: The starting node.

goal: The goal node.

Returns:

A tuple containing the shortest path (list of nodes) and the total cost.
Implementation

frontier = [] # Priority queue to store nodes to explore

heapq.heappush(frontier, (0, start, [start])) # (cost, node, path)

explored = set() # Set to store explored nodes

while frontier:

cost, current, path = heapq.heappop(frontier)

if current == goal:

return path, cost

if current in explored:

continue

explored.add(current)

for neighbor, neighbor_cost in graph[current].items():

new_cost = cost + neighbor_cost

heapq.heappush(frontier, (new_cost, neighbor, path + [neighbor]))

return None, None # No path found

Implementation

# Example usage:

graph = {

'A': {'B': 1, 'C': 4},

'B': {'A': 1, 'D': 2, 'E': 5},

'C': {'A': 4, 'F': 3},

'D': {'B': 2, 'G': 6},

'E': {'B': 5, 'G': 2},

'F': {'C': 3, 'G': 1},

 'G': {'D': 6, 'E': 2, 'F': 1}}

start_node = 'A'

goal_node = 'G'

path, cost = uniform_cost_search(graph, start_node, goal_node)

if path:

print("Shortest path:", path)

print("Total cost:", cost)

else:

print("No path found.")

Lab Program 5: Implementation of Iterative deepening depth-first Search:

Basic Information

The iterative deepening algorithm is a combination of DFS and BFS algorithms. This search
algorithm finds out the best depth limit and does it by gradually increasing the limit until a goal
is found.

This algorithm performs depth-first search up to a certain "depth limit", and it keeps increasing
the depth limit after each iteration until the goal node is found.

This Search algorithm combines the benefits of Breadth-first search's fast search and depth-
first search's memory efficiency.

The iterative search algorithm is useful uninformed search when search space is large, and
depth of goal node is unknown.

Advantages:

o It combines the benefits of BFS and DFS search algorithm in terms of fast search and
memory efficiency.

Disadvantages:

o The main drawback of IDDFS is that it repeats all the work of the previous phase.

Explanation:
1. dfs(graph, start, goal, depth_limit):
• Performs Depth-First Search with a given depth limit.
• Uses a stack to maintain the search frontier.
 • If the goal is found, returns the path to it.
• If the depth limit is reached, backtracks and explores other branches.
2. iterative_deepening_search(graph, start, goal, max_depth):
• Iteratively increases the depth limit for DFS.
• Starts with a depth limit of 0 and increases it until the goal is found or the
maximum depth is reached.
• Calls the dfs function for each depth limit.

Key points:
• Space efficiency:
IDDFS combines the space efficiency of DFS with the completeness of BFS.
• Optimality:
IDDFS guarantees finding the shortest path in a tree or an unweighted graph, like BFS.
Implementation:
It uses a simple loop to increase the depth limit and calls the DFS function repeatedly.
• Suitable for:
Problems where the solution is not too deep in the search tree and memory usage is a
concern.

Algorithm
from collections import deque

def dfs (graph, start, goal, depth_limit):

"""Performs depth-limited DFS starting from 'start' node."""

stack = deque ([ (start, [start])]) # Stack with (node, path) pairs

while stack:

current, path = stack.pop()

if current == goal:

return path

if len(path) - 1 < depth_limit:

for neighbor in graph[current]:

if neighbor not in path:

stack.append( (neighbor, path + [neighbor]) )

return None # No path found within depth limit

 def iterative_deepening_search(graph, start, goal, max_depth):

"""Performs iterative deepening search from 'start' to 'goal'."""

for depth in range(max_depth + 1):

result = dfs(graph, start, goal, depth)

if result:

return result

return None

Implementation

graph = {

'A': ['B', 'C'],

'B': ['D', 'E'],

'C': ['F'],

'D': [],

'E': ['F'],

'F': []

start_node = 'A'

goal_node = 'F'

max_depth_limit = 3

path = iterative_deepening_search(graph, start_node, goal_node, max_depth_limit)

if path:

print("Path found:", path)

else:

print("No path found.")

Practice Problems

1. For the given tree apply the BFS algorithm to calculate the time and space
complexity required in order to reach node K. Compare the same with DFS.

2. For the given tree apply the DFS algorithm to calculate the time and space
complexity required in order to reach node G. Compare the same with BFS.

3. For the given tree apply the DLS algorithm to calculate the time and space
complexity required in order to reach node J.
 4. For the given tree apply the UCS algorithm to calculate the time and space
complexity required in order to reach node G.

5. For the given tree apply the Iterative Deepening algorithm to calculate the
time and space complexity required in order to reach node G.

Real World Application Programming

You have been given a Tree consisting of N nodes. A tree is a fully-connected graph
consisting of N nodes and 𝑁−1 edges. The nodes in this tree are indexed from 1 to N.
Consider node indexed 1 to be the root node of this tree. The root node lies at level one in the
tree. You shall be given the tree and a single integer x . You need to find out the number of
nodes lying on level x.

Input Format
The first line consists of a single integer N denoting the number of nodes
in the tree. Each of the next 𝑛−1 lines consists of 2 integers a and b denoting an
undirected edge between node a and node b. The next line consists of a single
integer x.
 Output Format

You need to print a single integer denoting the number of nodes on level x.

2. Solve the maze problem using DFS

Note: DFS is used when there is one distinct solution.

3. Solve any state space problem using BFS.

PART II - Informed Search

The informed search algorithm is more useful for large search space. Informed search
algorithm uses the idea of heuristic, so it is also called Heuristic search.

A heuristic function helps the search algorithm choose a branch from the ones that are
available. It helps with the decision process by using some extra knowledge about the search
space.

Let’s use a simple analogy. If you went to a supermarket with many check-out counters, you
would try to go to the one with the least number of people waiting. This is a heuristic that
reduces your wait time.

Example

While playing tic tac toe, there are many placements from which one player can start, and
each placement has its own chances of winning. However, if the first player starts from the
centremost area, they have the most chances of winning. Hence, chances of winning can be a
heuristic.
Heuristics function: Heuristic is a function which is used in Informed Search, and it finds the
most promising path. It takes the current state of the agent as its input and produces the
estimation of how close agent is from the goal. The heuristic method, however, might not
always give the best solution, but it guaranteed to find a good solution in reasonable time.
Heuristic function estimates how close a state is to the goal. It is represented by h(n), and it
calculates the cost of an optimal path between the pair of states. The value of the heuristic
function is always positive.

Admissibility of the heuristic function is given as:

h(n) <= h*(n)

Here h(n) is heuristic cost, and h*(n) is the estimated cost. Hence heuristic cost should be less
than or equal to the estimated cost.

Lab Program 1: Implementation of Hill climbing Algorithm

Basic Information

Hill Climbing is a technique to solve certain optimization problems. In this technique, we start
with a sub-optimal solution and the solution is improved repeatedly until some condition is
maximized.

Hill Climbing technique is mainly used for solving computationally hard problems. It looks
only at the current state and immediate future state. Hence, this technique is memory efficient
as it does not maintain a search tree.

Algorithm

Evaluate the initial state.

Loop until a solution is found or there are no new operators left to
be applied:
- Select and apply a new operator
- Evaluate the new state:
goal → quit
better than current state → new current state
Applications

Hill Climbing technique can be used to solve many problems, where the current state allows
for an accurate evaluation function, such as Network-Flow, Travelling Salesman problem, 8-
Queens problem, Integrated Circuit design, etc.

Hill Climbing is used in inductive learning methods too. This technique is used in robotics for
coordination among multiple robots in a team. There are many other problems where this
technique is used.
Implementation

This technique can be applied to solve the travelling salesman problem. First an initial solution
is determined that visits all the cities exactly once. Hence, this initial solution is not optimal in
most of the cases. Even this solution can be very poor. The Hill Climbing algorithm starts with
such an initial solution and makes improvements to it in an iterative way. Eventually, a much
shorter route is likely to be obtained.

import random
# Distance matrix representing distances between cities
# Replace this with the actual distance matrix for your problem
distance_matrix = [
[0, 10, 15, 20],
[10, 0, 35, 25],
[15, 35, 0, 30],
[20, 25, 30, 0]
]
def total_distance(path):
# Calculate the total distance traveled in the given path
total = 0
for i in range(len(path) - 1):
total += distance_matrix[path[i]][path[i+1]]
total += distance_matrix[path[-1]][path[0]] # Return to starting city
return total
def hill_climbing_tsp(num_cities, max_iterations=10000):
current_path = list(range(num_cities)) # Initial solution, visiting cities in order
current_distance = total_distance(current_path)
for _ in range(max_iterations):
# Generate a neighboring solution by swapping two random cities
neighbor_path = current_path.copy()
i, j = random.sample(range(num_cities), 2)
neighbor_path[i], neighbor_path[j] = neighbor_path[j], neighbor_path[i]
neighbor_distance = total_distance(neighbor_path)
 # If the neighbor solution is better, move to it
if neighbor_distance < current_distance:
current_path = neighbor_path
current_distance = neighbor_distance
return current_path

def main():
num_cities = 4 # Number of cities in the TSP
solution = hill_climbing_tsp(num_cities)
print("Optimal path:", solution)
print("Total distance:", total_distance(solution))
if __name__ == "__main__":
main()
Output:
Optimal path: [1, 0, 2, 3]
Total distance: 80

Lab Program 2: Implementation of Best First Search Algorithm

Basic Information

The best first search algorithm is a version of the depth first search using heuristics. Each
node is evaluated with respect to its distance from the goal. Whichever node is closest to the
final state is explored first. If the path fails to reach the goal, the algorithm backtracks and
chooses some other node that didn’t seem to be the best before.

Algorithm

The algorithm of the greedy best first search algorithm is as follows -

• Define two empty lists (let them be openList and closeList).

• Insert src in the openList.
• Iterate while the open list is not empty, and do the following -
o Find the node with the least h value that is present in openList (let it be node).
o Remove the node from the openList, and insert it in the closeList.
o Check for all the adjacent nodes of the node, if anyone of them equals the dest.
If yes, then terminate the search process as we've reached the destination.
o Otherwise, find all the adjacent of the node that are neither present
in openList nor closeList and insert them in the openList.
• If we have reached here, it means there is no possible path between src and dest.
 • Step 1 - Initialize two empty lists 𝑖.𝑒.i.e. openList and closeList.
• Step 2- Insert src in the openList, after which we have - openList = [src] closeList = []
• Step 3 - (Iterating while the open list is not empty) -
o Iteration 1 -
▪ After this operation we will have - openList = [1, 2, 3] closeList = [src]
o Iteration 2 -
▪ After this operation we will have - openList = [1, 2, 7, 8] closeList =
[src, 3]
o Iteration 3 -
▪ Upon exploring the adjacents of node 7 we found that dest is one of
them. Hence, we return that search result in success, and print the
path src→3

Implementation

A Node class for GBFS Pathfinding

class Node:
def __init__(self, v, weight):
self.v=v
self.weight=weight

# pathNode class will help to store

# the path from src to dest.
class pathNode:
def __init__(self, node, parent):
self.node=node
self.parent=parent

# Function to add edge in the graph.

def addEdge(u, v, weight):
# Add edge u -> v with weight weight.
adj[u].append(Node(v, weight))

# Declaring the adjacency list

adj = []
# Greedy best first search algorithm function
def GBFS(h, V, src, dest):
"""
This function returns a list of
integers that denote the shortest
path found using the GBFS algorithm.
If no path exists from src to dest, we will return an empty list.
"""
# Initializing openList and closeList.
openList = []
closeList = []

# Inserting src in openList.

openList.append(pathNode(src, None))

# Iterating while the openList

# is not empty.
while (openList):

currentNode = openList[0]
currentIndex = 0
 # Finding the node with the least 'h' value
for i in range(len(openList)):
if(h[openList[i].node] < h[currentNode.node]):
currentNode = openList[i]
currentIndex = i

# Removing the currentNode from

# the openList and adding it in
# the closeList.
openList.pop(currentIndex)
closeList.append(currentNode)

# If we have reached the destination node.

if(currentNode.node == dest):
# Initializing the 'path' list.
path = []
cur = currentNode

# Adding all the nodes in the

# path list through which we have
# reached to dest.
while(cur != None):
path.append(cur.node)
cur = cur.parent

# Reversing the path, because

# currently it denotes path
# from dest to src.
path.reverse()
return path

# Iterating over adjacents of 'currentNode'

# and adding them to openList if
# they are neither in openList or closeList.
for node in adj[currentNode.node]:
for x in openList:
if(x.node == node.v):
continue

for x in closeList:
if(x.node == node.v):
continue

openList.append(pathNode(node.v, currentNode))

return []

# Driver Code
""" Making the following graph
src = 0
/ | \
/ | \
1 2 3
/\ | /\
/ \ | / \
4 5 6 7 8
/
/
dest = 9
"""
# The total number of vertices.
V = 10
## Initializing the adjacency list
for i in range(V):
adj.append([])

addEdge(0, 1, 2)
addEdge(0, 2, 1)
addEdge(0, 3, 10)
addEdge(1, 4, 3)
addEdge(1, 5, 2)
addEdge(2, 6, 9)
addEdge(3, 7, 5)
addEdge(3, 8, 2)
addEdge(7, 9, 5)

# Defining the heuristic values for each node.

h = [20, 22, 21, 10, 25, 24, 30, 5, 12, 0]
path = GBFS(h, V, 0, 9)
for i in range(len(path) - 1):
print(path[i], end = " -> ")

print(path[(len(path)-1)])

Output
0 --> 3 --> 7 --> 9

Complexity Analysis

• Time Complexity - In the worst situation, we may require to traverse through all the
edges to reach the destination. Hence in the worst case, the time complexity will
be 𝑂(𝐸log⁡𝑉)O(ElogV).
• Space Complexity - In the worst scenario, we may have all the vertices (nodes)
in openList which will make the worst case space complexity 𝑂(𝑉)O(V).
Lab Program 3: Implementation of A* Algorithm

Basic Information

The previous algorithm we discussed only considered the distance of the nodes from the goal.
A* uses the path of reaching to the current node from the starting node, and the path of
reaching the goal from the current node. So, the heuristic function becomes:
f(n) = g(n) + h(n)

where:
f(n): cost of the optimal path from start to goal
g(n): shortest path of the current node from the start
h(n): shortest path of the goal from the current node

Note: The actual distance from any node to the goal may be greater than h(n), since h(n) is
the shortest distance. This distance can be the straight line distance from the current node to
the goal. A path with the shortest distance may or may not exist.

Algorithm

1. Create an open list of found but not explored nodes.

2. Create a closed list to hold already explored nodes.
3. Add a starting node to the open list with an initial value of g
4. Repeat the following steps until the open list is empty or you reachthe target node:
a. Find the node with the smallest f-value (i.e., the node with the minor g(n) h(n)) in the
open list.
b. Move the selected node from the open list to the closed list.
c. Create all valid descendants of the selected node.
d. For each successor, calculate its g-value as the sum of the current node's g value and
the cost of moving from the current node to the successor node. Update the g-value of the
tracker when a better path is found.
e. If the follower is not in the open list, add it with the calculated g-value and calculate its
h-value. If it is already in the open list, update its g value if the new path is better.
f. Repeat the cycle. Algorithm A* terminates when the target node is reached or when the
open list empties, indicating no paths from the start node to the target node. The A* search
algorithm is widely used in various fields such as robotics, video games, network routing, and
design problems because it is efficient and can find optimal paths in graphs or networks.

Complexity Analysis

• Time Complexity - The time it takes for the A* search algorithm to find a solution
depends on how many options each step has (the branching factor) and how deep the
solution is. We express this time complexity as 𝑂(𝑏𝑑)O(bd), where b is the
branching factor and d is the depth of the solution.
• Space Complexity - In the worst scenario, we may have all the vertices (nodes)
in openList which will make the worst-case space complexity be 𝑂(𝑏𝑑)O(bd).
Practice Problems

1) You are given a partially filled 9x9 Sudoku board. Your task is to implement a
Sudoku solver using the hill climbing algorithm.

Sudoku Rules

• Each of the numbers from 1 to 9 must appear exactly once in each row.
• Each of the numbers from 1 to 9 must appear exactly once in each
column.
• Each of the numbers from 1 to 9 must appear exactly once in each 3x3
sub-grid.

Input

The input will be a 9x9 grid of integers where 0 represents an empty cell.

Output

The output should be a solved 9x9 Sudoku grid if a solution is found. If no

solution is found, output "No solution found".

Example

Input:

[
[5, 3, 0, 0, 7, 0, 0, 0, 0],
[6, 0, 0, 1, 9, 5, 0, 0, 0],
[0, 9, 8, 0, 0, 0, 0, 6, 0],
[8, 0, 0, 0, 6, 0, 0, 0, 3],
[4, 0, 0, 8, 0, 3, 0, 0, 1],
[7, 0, 0, 0, 2, 0, 0, 0, 6],
[0, 6, 0, 0, 0, 0, 2, 8, 0],
[0, 0, 0, 4, 1, 9, 0, 0, 5],
[0, 0, 0, 0, 8, 0, 0, 7, 9]
]

Output:

[
[5, 3, 4, 6, 7, 8, 9, 1, 2],
[6, 7, 2, 1, 9, 5, 3, 4, 8],
[1, 9, 8, 3, 4, 2, 5, 6, 7],
[8, 5, 9, 7, 6, 1, 4, 2, 3],
[4, 2, 6, 8, 5, 3, 7, 9, 1],
[7, 1, 3, 9, 2, 4, 8, 5, 6],
[9, 6, 1, 5, 3, 7, 2, 8, 4],
[2, 8, 7, 4, 1, 9, 6, 3, 5],
[3, 4, 5, 2, 8, 6, 1, 7, 9]
]
2) Write a program and execute to find the shortest path in an unweighted grid
using the Best-first search algorithm. You are given a 2D grid where each cell
is either an open cell (0) or a blocked cell (1). The task is to find the shortest
path from the top-left cell (0,0) to the bottom-right cell (n-1, m-1). The path can
only move in four possible directions: up, down, left, and right. If there is no
path, return -1.
Input:
The first line contains two integers n and m representing the number of rows
and columns in the grid.
The next n lines each contain m integers representing the grid cells (either 0 for
open or 1 for blocked).

• S represents the start point at (0,0).

• E represents the end point at (2,2).
• 0 represents open cells.
• 1 represents blocked cells.

Output:
Print the length of the shortest path from the top-left to the bottom-right cell. If
no such path exists, print -1.
Constraints:
▪ 1 <= n, m <= 100
▪ The grid contains only 0 and 1

Example:

Input:

0 0 0
1 1 0
0 0 0

Output:

4
3) Write and execute a program to find the shortest path in a maze using the A*
algorithm. You are given a maze represented as a 2D grid where each cell is either
passable (0 for open cell) or impassable (1 for wall). The task is to find the shortest
path from the top-left cell (0,0) to the bottom-right cell (n-1, m-1) through open cells
only. The path can move in four possible directions: up, down, left, and right. If there
is no path, return -1.

Input:

1. The first line contains two integers n and m representing the number of rows
and columns in the maze.
2. The next n lines each contain m integers representing the cells of the maze (0
for open cell, 1 for wall).

Output:

• Print the total cost of the shortest path from the top-left to the bottom-right
cell. If no such path exists, print -1.

Constraints:

• 1 <= n, m <= 100

• The maze contains integers 0 (open) and 1 (wall).

Example:

Input:

0 1 0
0 0 0
1 1 0
Output:
4
with a total cost of 4.