ARULMURUGAN COLLEGE OF

ENGINEERING
(Approved by AICTE, New Delhi and Affiliated to Anna University, Chennai & ISO 9001:2015 Certified
Institution)

THENNILAI, KARUR - 639 206.

DEPARTMENT OF ARTIFICIAL INTELLIGENCE AND DATA SCIENCE

AD3351 - DESIGN AND ANALYSIS OF ALGORITHM

II YEAR / III SEMESTER

Name :

Reg No :

Subject name :

Academic Year :

i
 ARULMURUGAN COLLEGE OF ENGINEERING
(Approved by AICTE and Affiliated to Anna University)
THENNILAI, KARUR – 639 206.

PRACTICAL RECORD

Register Number

Name

Year / Sem

Degree / Branch

Subject Code & Name

Certified that this is a bonafide record of work done by the above student
during the year 20 - 20

Staff in-charge Head of the Department

Submitted for the University Practical Examination held on

Internal Examiner External Examiner

ii
 INDEX

Ex. Staff
Date Name of the Experiment Marks Page No
No Signature
EX.No:1 IMPLEMENT RECURSIVE AND NON-RECURSIVE
ALGORITHMS AND STUDY THE ORDER OF GROWTH
FROM log2n to n!

AIM:
The aim is to implement recursive and non-recursive algorithms and
study the order of growth from log 2N to n!

ALGORTIHM:
Step 1: Start the program.
Step 2: Implement Recursive and non-recursive algorithm using log 2n to n!
Step 3: compute the factorial n* fact (n-1), Fibonacci Series using recursive
algorithm.
Step 4: Iterate from 1 to n, multiplying the current value by the iterator using non-
recursive algorithm.
Step 5: End the program.

PROGRAM:
import time
import math
# Recursive Algorithm
def recursive_factorial(n):
if n == 0 or n == 1:
return 1
return n * recursive_factorial(n - 1)
# Non-Recursive Algorithm
def non_recursive_factorial(n):
result = 1
for i in range(1, n + 1):
result *= i
return result

# Measure time complexity

def measure_time_complexity(algorithm, n):
start_time = time.time()
algorithm(n)
end_time = time.time()
return end_time - start_time
# Main program
for i in range(1, 6):
n = int(math.pow(2, i))
recursive_time = measure_time_complexity(recursive_factorial, n)
non_recursive_time = measure_time_complexity(non_recursive_factorial, n)
print(f"n = 2^{i}")

4
 print(f"Recursive Time: {recursive_time}")
print(f"Non-Recursive Time: {non_recursive_time}")
print() # Print a blank line for better readability

OUTPUT:
n = 2^1
Recursive Time: 6.9141387939453125e-06
Non-Recursive Time: 2.86102294921875e-06

n = 2^2
Recursive Time: 1.1920928955078125e-05
Non-Recursive Time: 4.76837158203125e-06

n = 2^3
Recursive Time: 1.6927719116210938e-05
Non-Recursive Time: 5.7220458984375e-06

n = 2^4
Recursive Time: 2.9802322387695312e-05
Non-Recursive Time: 7.152557373046875e-06

n = 2^5
Recursive Time: 5.698204040527344e-05
Non-Recursive Time: 1.0013580322265625e-05

RESULT:
Thus, the recursive and non-recursive algorithms for various functions and
study their order of growth was implemented successfully.

5
EX.No:2 DIVIDE AND CONQUER – STRASSEN’s MATRIX
MULTIPLICATION

AIM:
To implement Strassen’s Matrix Multiplication using the Divide and
Conquer approach and demonstrate its application on directed acyclic graphs
(DAGs).

ALGORTIHM:
Step 1: Start the program.
Step 2: Create the matrix A&B.
Step 3: Divide the matrix A & matrix B into 4 sub-matrices of size n/2*n/2.
Step 4: Calculate the strassen’s matrix multiplication recursively.
Step 5: Compute the submatrices of C.
Step 6: Combine the submatrices into our new matrix C.
Step 7: End the program.

PROGRAM:
import numpy as np
def strassen_multiply(A, B):
n = len(A)
# Base case: If the matrices are 1x1, perform standard multiplication
if n == 1:
return np.array([[A[0][0] * B[0][0]]])
# Split matrices into four equal-sized submatrices
a11 = A[:n//2, :n//2]
a12 = A[:n//2, n//2:]
a21 = A[n//2:, :n//2]
a22 = A[n//2:, n//2:]
b11 = B[:n//2, :n//2]
b12 = B[:n//2, n//2:]
b21 = B[n//2:, :n//2]
b22 = B[n//2:, n//2:]
# Recursive computation of seven products
p1 = strassen_multiply(a11 + a22, b11 + b22)
p2 = strassen_multiply(a21 + a22, b11)
p3 = strassen_multiply(a11, b12 - b22)
p4 = strassen_multiply(a22, b21 - b11)
p5 = strassen_multiply(a11 + a12, b22)
p6 = strassen_multiply(a21 - a11, b11 + b12)
p7 = strassen_multiply(a12 - a22, b21 + b22)
# Combine the products to get the result matrix
c11 = p1 + p4 - p5 + p7

6
 c12 = p3 + p5
c21 = p2 + p4
c22 = p1 - p2 + p3 + p6
# Combine the submatrices into the result matrix
result = np.vstack((np.hstack((c11, c12)), np.hstack((c21, c22))))
return result
# Main program
if name == " main ":
# Example matrices A and B
A = np.array([[1, 2], [3, 4]])
B = np.array([[5, 6], [7, 8]])
# Perform Strassen's Matrix Multiplication
result = strassen_multiply(A, B)
# Display the result
print("Matrix A:")
print(A)
print("\nMatrix B:")
print(B)
print("\nResultant Matrix C (Strassen's Multiplication):")
print(result)

OUTPUT:
Matrix A:
[[1 2]
[3 4]]

Matrix B:
[[5 6]
[7 8]]

Resultant Matrix C (Strassen's Multiplication):

[[19 22]
[3 50]

RESULT:
Thus, the Strassen’s Matrix Multiplication using the Divide and Conquer
approach was implemented successfully.

7
EX.No:3 DECREASE AND CONQUER – TOPOLOGICAL
SORTING

AIM:
To imp le me nt Top o lo gic a l Sorting using the Decrease and Conquer
approach in Python and analyze its performance.

ALGORTIHM:
1. Compute In-Degrees:
 For each vertex in the graph, compute its in-degree (the number of incoming
edges).
2. Find Vertices with In-Degree of 0:
 Identify all vertices with an in-degree of 0. These are the vertices with no
incoming edges.
3. Decrease and Conquer:
 While there are vertices with an in-degree of 0:
 Choose a vertex with an in-degree of 0.
 Output that vertex and remove it from the graph, along with its outgoing edges.
 Update the in-degree of the remaining vertices connected to the removed
vertex.
 Repeat this process until all vertices are removed.
4. Check for Cycles:
 After all vertices have been processed, check if the topological order contains
all vertices.
 if not, the graph contains a cycle and topological sorting is not possible.
5. Output:
 Return the topologically sorted order of vertices.

8
PROGRAM:
from collections import defaultdict
class Graph:
def init (self, vertices):
self.vertices = vertices
self.graph = defaultdict(list)
def add_edge(self, u, v):
self.graph[u].append(v)
def topological_sort_util(self, v, visited, stack):
visited[v] = True
for neighbor in self.graph[v]:
if not visited[neighbor]:
self.topological_sort_util(neighbor, visited, stack)
stack.append(v)
def topological_sort(self):
visited = [False] * self.vertices
stack = []
for i in range(self.vertices):
if not visited[i]:
self.topological_sort_util(i, visited, stack)
return stack[::-1]
# Main program
if name == " main ":
# Create a graph
g = Graph(6)
g.add_edge(5, 2)
g.add_edge(5, 0)
g.add_edge(4, 0)
g.add_edge(4, 1)
g.add_edge(2, 3)
g.add_edge(3, 1)
# Perform Topological Sorting
result = g.topological_sort()
# Display the result
print("Topological Sorting Order:")
print(result)

OUTPUT:
Topological Sorting Order:
[5, 4, 2, 3, 1, 0]

9
RESULT:
Thus, the Topological Sorting using the Decrease and Conquer approach was
implemented successfully.

10
11
EX.No:4 TRANSFORM AND CONQUER – HEAP SORT

AIM:
To implement Heap Sort using the Transform and Conquer approach in
Python and analyze performance.
ALGORTIHM:
Step 1: Start the program.
Step 2: Transform the input array into a max-heap.
Step 3: Repeatedly extract the maximum element (root of the heap) and swap it with
the last element of the heap.
Step 4: Reduce the heap size by 1 and heapify the remaining elements.
Step 5: Repeat the process until the heap is empty.
Step 6: End the program.

PROGRAM:
def heapify(arr, n, i):
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and arr[left] > arr[largest]:
largest = left
if right < n and arr[right] > arr[largest]:
largest = right

if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
def heap_sort(arr):
n = len(arr)
# Step 1: Build Max Heap
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
# Step 2 to 4: Transfer and Restore
for i in range(n - 1, 0, -1):
arr[i], arr[0] = arr[0], arr[i] # Transfer max element
heapify(arr, i, 0) # Restore heap property
# Step 5: Output Sorted Array
return arr
# Example usage
arr = [12, 11, 13, 5, 6, 7]
print("Input Array:", arr)
print("Sorted Array:", heap_sort(arr))

12
OUTPUT:
Input Array: [12, 11, 13, 5, 6, 7]
Sorted Array: [5, 6, 7, 11, 12, 13]

RESULT:
Thus, the Heap Sort using the Transform and Conquer
approach was implemented successfully.

13
EX.No:5A DYNAMIC PROGRAMMING –
COIN CHANGE PROBLEM

AIM:
To implement the Coin Change Problem using dynamic
programming approach in Python.

ALGORTIHM:
Step 1: Start the program.
Step 2: Create a table to store the solutions to subproblems.
Step 3: Initialize the table with base cases.
Step 4: Fill in the table using the recurrence relation.
Step 5: The final value in the table represents the solution to the original problem
Step 6: End the program.

PROGRAM:

def count_ways_to_make_change(coins, target):

n = len(coins)
table = [0] * (target + 1)
table[0] = 1 # There is one way to make a change of 0
for coin in coins:
for i in range(coin, target + 1):
table[i] += table[i - coin]
return table[target]
if name == " main ":
coins = [1, 2, 5]
target = 5
ways = count_ways_to_make_change(coins, target)
print(f"Number of ways to make change for {target} is: {ways}")

OUTPUT:

Number of ways to make change for 5 is: 4

RESULT:
Thus, the Coin Change Problem using dynamic programming approach
was implemented successfully.

14
EX.No:5B DYNAMIC PROGRAMMING –
WARSHALL’S AND FLOYD’S ALGORITHM

AIM:
To implement the Warshall’s and Floyd’s Algorithm usin dynamic
programming approach in Python.
ALGORTIHM:
Step 1: Initialization:
 Initialize a matrix dist with the same dimensions as the adjacency matrix,
initialized with the distances between vertices (dist[i][j] = weight of edge (i,
j)). Initialize diagonal elements (dist[i][i]) to 0.
Step 2: Dynamic Programming:
 For each intermediate vertex k:
 For each pair of vertices (i, j):
 If vertex k is on the shortest path from vertex i to j, update dist[i][j] to
min(dist[i][j], dist[i][k] + dist[k][j]).
Step 3: Output:
 The dist matrix contains the shortest path distances between all pairs of
vertices.
PROGRAM:
def floyd_warshall(graph):
n = len(graph)
dist = [[0 if i == j else graph[i][j] if graph[i][j] != float('inf') else float('inf') for j in
range(n)] for i in range(n)]
for k in range(n):
for i in range(n):
for j in range(n):
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
return dist
# Example usage
graph = [
[0, 3, float('inf'), 7],
[8, 0, 2, float('inf')],
[5, float('inf'), 0, 1],
[2, float('inf'), float('inf'), 0]
]
shortest_paths = floyd_warshall(graph)
for row in shortest_paths:
print(row)

15
OUTPUT:

[0, 3, 5, 6]
[5, 0, 2, 3]
[3, 6, 0, 1]
[2, 5, 7, 0]

RESULT:
Thus, the Warshall’s and Floyd’s Algorithm using dynamic programming
approach was implemented successfully.

16
EX.No:5C DYNAMIC PROGRAMMING –
KNAPSACK PROBLEM

AIM:
To implement the Knapsack Problem using dynamic programming approach in
Python.

ALGORTIHM:
Step 1: Initialization:
Create a 2D array dp[][] with dimensions (n+1) x (W+1), where n is the number of
items and W is the capacity of the knapsack. Initialize the array with zeros.
Step 2: Dynamic Programming:
Iterate over each item from 1 to n and each capacity from 1 to W.
For each item i and capacity w:
If the weight of the current item is less than or equal to the current capacity,
choose the maximum value between:
The value of selecting the current item plus the value of the best solution for the
remaining capacity (dp[i-1][w - weights[i-1]]).
The value of not selecting the current item (dp[i-1][w]).
Otherwise, the value remains the same as the value obtained without considering
the current item (dp[i-1][w]).
Step 3: Output:
The value of dp[n][W] represents the maximum value that can be obtained by
selecting items to fit into the knapsack.

17
PROGRAM:
def knapsack(W, weights, values):
n = len(weights)
dp = [[0] * (W + 1) for _ in range(n + 1)]

for i in range(1, n + 1):

for w in range(1, W + 1):
if weights[i - 1] <= w:
dp[i][w] = max(values[i - 1] + dp[i - 1][w - weights[i - 1]], dp[i - 1][w])
else:
dp[i][w] = dp[i - 1][w]
return dp[n][W]
# Example usage
W = 10
weights = [5, 4, 6, 3]
values = [10, 40, 30, 50]
print("Maximum value in knapsack:", knapsack(W, weights, values))

OUTPUT:

Maximum value in knapsack: 90

RESULT:
Thus, the Knapsack Problem using dynamic programming approach
was implemented successfully.

18
.No:6A GREEDY TECHNIQUE – DIJKSTRA‘S ALGORITHM
HUFFMAN TREE AND CODES

AIM:
To implement Dijkstra's Algorithm using Greedy Technique in Python for
finding the shortest path in a weighted graph.
ALGORTIHM:
Step 1: Initialize the distance of all vertices from the source as infinity, and
the distance of the source vertex to itself as 0.
Step 2: Create a priority queue to store vertices and their distances.
Step 3: While the priority queue is not empty, extract the vertex with the
minimum distance.
Step 4: Update the distances of adjacent vertices if a shorter path is found.
Step 5: Repeat until all vertices are processed.
PROGRAM:
import heapq
def dijkstra(graph, source):
n = len(graph)
distances = [float('inf')] * n
distances[source] = 0
visited = [False] * n
pq = [(0, source)] # (distance, vertex)
while pq:
dist_u, u = heapq.heappop(pq)
if visited[u]:
continue
visited[u] = True
for v, weight in graph[u]:
if not visited[v] and dist_u + weight < distances[v]:
distances[v] = dist_u + weight
heapq.heappush(pq, (distances[v], v))
return distances
graph = {
0: [(1, 4), (2, 2)],
1: [(2, 5), (3, 10)],
2: [(3, 3)],
3: []
}
source = 0
print("Shortest distances from source vertex", source, ":", dijkstra(graph, source)

19
OUTPUT:

Shortest distances from source vertex 0 : [0, 4, 2, 5]

RESULT:
Thus, the Dijkstra's Algorithm using Greedy Technique was implemented
successfully.

20
EX.No:6B GREEDY TECHNIQUE – HUFFMAN TREE AND CODES

AIM:
To implement Huffman tree and codes using Greedy Technique in Python for finding
the shortest path in a weighted graph.

ALGORTIHM:
Step 1: Create a leaf node for each unique character and build a min heap of
all leaf nodes (Min Heap is used as a priority queue. The value of frequency
field is used to compare two nodes in min heap. Initially, the least frequent
character is at root)
Step 2: Extract two nodes with the minimum frequency from the min heap.
Step 3: Create a new internal node with a frequency equal to the sum of the
two nodes frequencies. Make the first extracted node as its left child and the
other extracted node as its right child. Add this node to the min heap.
Step 4: Repeat steps#2 and #3 until the heap contains only one node. The
remaining node is the root node and the tree is complete.

PROGRAM:
import heapq
from collections import defaultdict
class Node:
def init (self, freq, symbol=None):
self.freq = freq
self.symbol = symbol
self.left = None
self.right = None
def lt (self, other):
return self.freq < other.freq
def build_huffman_tree(symbols_freq):
pq = [Node(freq, symbol) for symbol, freq in symbols_freq.items()]
heapq.heapify(pq)
while len(pq) > 1:
left = heapq.heappop(pq)
right = heapq.heappop(pq)
merged = Node(left.freq + right.freq)
merged.left = left
merged.right = right
heapq.heappush(pq, merged)

21
 return pq[0]
def generate_huffman_codes(root, prefix="", codes={}):
if root is None:
return
if root.symbol is not None:
codes[root.symbol] = prefix
generate_huffman_codes(root.left, prefix + "0", codes)
generate_huffman_codes(root.right, prefix + "1", codes)
# Example usage
symbols_freq = {'A': 5, 'B': 9, 'C': 12, 'D': 13, 'E': 16, 'F': 45}
huffman_tree = build_huffman_tree(symbols_freq)
huffman_codes = {}
generate_huffman_codes(huffman_tree, "", huffman_codes)
print("Huffman Codes:")
for symbol, code in huffman_codes.items():
print(symbol, ":", code)

OUTPUT:

Huffman Codes:
A : 1100
B : 1101
C : 100
D : 101
E : 111
F:0

RESULT:
Thus, the Huffman tree and codes using Greedy Technique was
implemented successfully.

22
EX.No:7 ITREATIVE IMPROVEMENT – SIMPLEX METHOD

AIM:
To implement the Simplex Method using Iterative Improvement in Python for solving
linear programming problems.

ALGORTIHM:
Step 1: Formulate the initial tableau.
Step 2: Iterate through the tableau until an optimal solution is found or it is
determined that the solution is unbounded.
Step 3: Choose a pivot column and pivot row.
Step 4: Update the tableau using pivot operations.
Step 5: Repeat until an optimal solution is achieved.

PROGRAM:
import numpy as np
def simplex_method(c, A, b):
m, n = A.shape
tableau = np.hstack((A, np.eye(m)))
c = np.hstack((c, np.zeros(m)))
basic_vars = np.arange(n, n + m)
while True:
# Check if the current solution reaches the optimal solution
if np.all(c <= 0):
optimal_solution = tableau[:-1, -1]
optimal_value = -tableau[-1, -1]
return optimal_solution[:n], optimal_value
# Choose the pivot column (minimum coefficient in the objective function)
pivot_col = np.argmin(c)
# Check for unbounded solution
if np.all(tableau[:, pivot_col] <= 0):
raise Exception("The solution is unbounded.")
# Choose the pivot row (minimum ratio test)
ratios = tableau[:-1, -1] / tableau[:-1, pivot_col]
pivot_row = np.argmin(ratios)
# Update the tableau using pivot operations
pivot = tableau[pivot_row, pivot_col]
tableau[pivot_row, :] /= pivot

23
 for i in range(m + 1):
if i != pivot_row:
tableau[i, :] -= tableau[i, pivot_col] * tableau[pivot_row, :]
# Update basic variables
basic_vars[pivot_row] = pivot_col
# Main program
if name == " main ":
# Example linear programming problem
c = np.array([-2, -3, 0, 0])
A = np.array([[1, -1, 1, 0],
[3, 1, 0, 1]])
b = np.array([2, 5])
optimal_solution, optimal_value = simplex_method(c, A, b)
print("Optimal Solution:", optimal_solution)
print("Optimal Value:", optimal_value)

OUTPUT:

Optimal Solution: [2. 0.]

Optimal Value: -6.0

RESULT:
Thus, the Simplex Method using Iterative Improvement was
implemented successfully.

24
EX.No:8A BACKTRACKING – N-QUEEN PROBLEM

AIM:
To implement the N-Queen Problem using the Backtracking algorithm in
Python.
ALGORTIHM:
The N-Queen problem is to place N chess queens on an \(N \times N\)
chessboard in such a way that no two queens threaten each other.
Step 1: Start with an empty chessboard.
Step 2: Place queens one by one in different columns, starting from the
leftmost column.
Step 3: Check if the current placement is safe. If not, backtrack and try the
next position.
Step 4: Repeat the process until all queens are placed or it's determined
that no solution exists.
PROGRAM:
def is_safe(board, row, col, N):
for i in range(row):
if board[i][col] == 1:
return False
# Check upper left diagonal
for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
if board[i][j] == 1:
return False
# Check upper right diagonal
for i, j in zip(range(row, -1, -1), range(col, N)):
if board[i][j] == 1:
return False
return True
def solve_n_queens_util(board, row, N):
if row == N:
return True
for col in range(N):
if is_safe(board, row, col, N):
board[row][col] = 1
if solve_n_queens_util(board, row + 1, N):
return True
board[row][col] = 0

25
 return False
def solve_n_queens(N):
board = [[0] * N for _ in range(N)]
if solve_n_queens_util(board, 0, N):
return board
else:
return None
def print_board(board):
for row in board:
print(" ".join(str(cell) for cell in row))
N=4
solution = solve_n_queens(N)
if solution:
print("Solution for {}-Queens Problem:".format(N))
print_board(solution)
else:
print("No solution exists for {}-Queens Problem.".format(N))

OUTPUT:

Solution for 4-Queens Problem:

0010
1000
0001
0100

RESULT:
Thus,the N-Queen Problem using the Backtracking algorithm was implemented
successfully.

26
27
EX.No:8B BACKTRACKING – SUBSET SUM PROBLEM

AIM:
To implement the Subset Sum Problem using the Backtracking algorithm in
Python.

ALGORTIHM:
Given a set of positive integers and a target sum, determine if there is a subset
of the set that adds up to the target sum.
Step 1: Start with an empty subset.
Step 2: Include an element in the subset and recursively check if the
remaining sum can be obtained.
Step 3: Exclude the element from the subset and recursively check if the sum
can be obtained without the element.
Step 4: Repeat the process for each element in the set.

PROGRAM:
def subset_sum_util(nums, target, current_sum, start, path, result):
if current_sum == target:
result.append(path[:])
return
for i in range(start, len(nums)):
if current_sum + nums[i] <= target:
path.append(nums[i])
subset_sum_util(nums, target, current_sum + nums[i], i + 1, path, result)
path.pop()
def subset_sum(nums, target):
result = []
subset_sum_util(nums, target, 0, 0, [], result)
return result
# Main program
if name == " main ":
nums = [1, 2, 3, 4, 5]
target = 7
subsets = subset_sum(nums, target)
print(f"Subsets with sum equal to {target}:")
for subset in subsets:
print(subset)

28
OUTPUT:

Subsets with sum equal to 7:

[2, 5]
[3, 4]
[1, 3, 4]

RESULT:
Thus, the Subset Sum Problem using the Backtracking algorithm
was implemented successfully.

29
EX.No:9A BRANCH AND BOUND – ASSIGNMENT PROBLEM

AIM:
To implement the Assignment Problem using the Branch and Bound
algorithm in Python.

ALGORTIHM:
Given a set of cities and the distances between each pair of cities, find the
shortest possible tour that visits each city exactly once and returns to the starting
city.
Step 1: Create a cost matrix for the assignment problem.
Step 2: Implement the Branch and Bound algorithm to find the optimal assignment.

PROGRAM:

import numpy as np
from itertools import permutations
def assignment_cost(assignment, cost_matrix):
total_cost = 0
for worker, task in enumerate(assignment):
total_cost += cost_matrix[worker, task]
return total_cost
def branch_and_bound_assignment(cost_matrix):
n = len(cost_matrix)
min_cost = float('inf')
optimal_assignment = None
for assignment in permutations(range(n)):
current_cost = assignment_cost(assignment, cost_matrix)
if current_cost < min_cost:
min_cost = current_cost
optimal_assignment = assignment
return optimal_assignment, min_cost
# Main program
if name == " main ":
# Example cost matrix for the assignment problem
cost_matrix = np.array([
[9, 2, 7, 8],
[6, 4, 3, 7],
[5, 8, 1, 8],

30
 [7, 6, 9, 4]
])
optimal_assignment, min_cost = branch_and_bound_assignment(cost_matrix)
print("Optimal Assignment:", optimal_assignment)
print("Minimum Cost:", min_cost)

OUTPUT:

Optimal Assignment: (1, 2, 0, 3)

Minimum Cost: 10

RESULT:
Thus, the Assignment Problem using the Branch and Bound algorithm was
implemented successfully.

31
EX.No:9B BRANCH AND BOUND – TRAVELING SALESMAN
PROBLEM

AIM:
To implement the Traveling Salesman Problem using the Branch and
Bound algorithm in Python.

ALGORTIHM:
Given a set of cities and the distances between each pair of cities, find the
shortest possible tour that visits each city exactly once and returns to the starting
city.
Step 1: Create a distance matrix for the TSP.
Step 2: Implement the Branch and Bound algorithm to find the optimal tour.

PROGRAM:

import numpy as np
def tsp_cost(tour, distance_matrix):
total_cost = 0
for i in range(len(tour) - 1):
total_cost += distance_matrix[tour[i], tour[i + 1]]
# Add cost to return to the starting city
total_cost += distance_matrix[tour[-1], tour[0]]
return total_cost
def branch_and_bound_tsp(distance_matrix):
n = len(distance_matrix)
optimal_tour = None
min_cost = float('inf')
initial_tour = list(range(n))

def tsp_recursive(tour, cost):

nonlocal optimal_tour, min_cost
if len(tour) == n:
# Completed a full tour, update optimal solution if needed
if cost < min_cost:
min_cost = cost
optimal_tour = tour[:]
return
for city in range(n):
if city not in tour:

32
 tsp_recursive(tour + [city], cost + distance_matrix[tour[-1], city])
tsp_recursive(initial_tour, 0)
return optimal_tour, min_cost
# Main program
if name == " main ":
# Example distance matrix for the TSP
distance_matrix = np.array([
[0, 10, 15, 20],
[10, 0, 35, 25],
[15, 35, 0, 30],
[20, 25, 30, 0]
])
optimal_tour, min_cost = branch_and_bound_tsp(distance_matrix)
print("Optimal Tour:", optimal_tour)
print("Minimum Cost:", min_cost)

OUTPUT:
Optimal Tour: [0, 1, 3, 2]
Minimum Cost: 80

RESULT:
Thus, the Traveling Salesman Problem using the Branch and Bound
algorithm was implemented successfully

33