Scribd
Upload
12 views

Untitled11.ipynb - Colab

Uploaded by

ipathan
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
12 views

Untitled11.ipynb - Colab

Uploaded by

ipathan
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 11

#Distance matrix setup

import itertools
import numpy as np

# Distance Matrix (same as described above)


distance_matrix = [
[0, 5, 8, 9, 6, 7, 10, 12, 6, 4, 11],
[5, 0, 3, 7, 8, 4, 9, 11, 5, 6, 7],
[8, 3, 0, 5, 6, 3, 8, 9, 4, 7, 10],
[9, 7, 5, 0, 3, 6, 4, 10, 8, 9, 12],
[6, 8, 6, 3, 0, 7, 5, 9, 4, 10, 13],
[7, 4, 3, 6, 7, 0, 5, 6, 7, 5, 8],
[10, 9, 8, 4, 5, 5, 0, 7, 3, 8, 6],
[12, 11, 9, 10, 9, 6, 7, 0, 5, 7, 4],
[6, 5, 4, 8, 4, 7, 3, 5, 0, 9, 10],
[4, 6, 7, 9, 10, 5, 8, 7, 9, 0, 11],
[11, 7, 10, 12, 13, 8, 6, 4, 10, 11, 0]
]

# Function to calculate total path cost


def calculate_path_cost(path, distance_matrix):
cost = 0
for i in range(len(path) - 1):
cost += distance_matrix[path[i]][path[i + 1]]
cost += distance_matrix[path[-1]][path[0]] # Return to the starting point
return cost

#Brute Force Algorithm


def tsp_brute_force(distance_matrix):
n = len(distance_matrix)
cities = list(range(1, n)) # Exclude the starting point (0)
min_cost = float("inf")
best_path = []

# Generate all permutations of cities


for perm in itertools.permutations(cities):
path = [0] + list(perm) # Start from the depot
cost = calculate_path_cost(path, distance_matrix)

if cost < min_cost:


min_cost = cost
best_path = path

return best_path, min_cost


# Run the Brute Force TSP
brute_force_path, brute_force_cost = tsp_brute_force(distance_matrix)
print("Brute Force - Best Path:", brute_force_path, "Cost:", brute_force_cost)

Brute Force - Best Path: [0, 4, 3, 6, 8, 7, 10, 1, 2, 5, 9] Cost: 47

#Dynamic Programming
def tsp_dynamic_programming(distance_matrix):
n = len(distance_matrix)
memo = {}

# Recursive function with memoization


def visit(city, visited):
if visited == (1 << n) - 1: # All cities visited
return distance_matrix[city][0] # Return to starting point

if (city, visited) in memo:


return memo[(city, visited)]

min_cost = float("inf")
for next_city in range(n):
if visited & (1 << next_city) == 0: # If not yet visited
new_cost = distance_matrix[city][next_city] + visit(next_city, visited | (1 << next_city))
min_cost = min(min_cost, new_cost)

memo[(city, visited)] = min_cost


return min_cost

# Reconstruct the path


def reconstruct_path():
path = [0]
visited = 1
last_city = 0

for _ in range(n - 1):


best_next = None
for next_city in range(n):
if visited & (1 << next_city) == 0:
next_cost = distance_matrix[last_city][next_city] + memo.get((next_city, visited | (1 << next_city)), float("inf"))
if best_next is None or next_cost < best_next[0]:
best_next = (next_cost, next_city)

path.append(best_next[1])
last_city = best_next[1]
visited |= (1 << best_next[1])
return path

min_cost = visit(0, 1) # Start from city 0 with visited bitmask set to 1


best_path = reconstruct_path()
best_path.append(0) # Return to starting point

return best_path, min_cost

# Run the Dynamic Programming TSP


dp_path, dp_cost = tsp_dynamic_programming(distance_matrix)
print("Dynamic Programming - Best Path:", dp_path, "Cost:", dp_cost)

Dynamic Programming - Best Path: [0, 4, 3, 6, 8, 7, 10, 1, 2, 5, 9, 0] Cost: 47

#Greedy Algorithm
def tsp_nearest_neighbor(distance_matrix):
n = len(distance_matrix)
start_city = 0
visited = [False] * n
visited[start_city] = True
path = [start_city]
total_cost = 0

current_city = start_city
for _ in range(n - 1):
nearest_city = None
min_distance = float("inf")

for next_city in range(n):


if not visited[next_city] and distance_matrix[current_city][next_city] < min_distance:
min_distance = distance_matrix[current_city][next_city]
nearest_city = next_city

path.append(nearest_city)
total_cost += min_distance
visited[nearest_city] = True
current_city = nearest_city

total_cost += distance_matrix[current_city][start_city] # Return to starting point


path.append(start_city)

return path, total_cost

# Run the Nearest Neighbor TSP


nn_path, nn_cost = tsp_nearest_neighbor(distance_matrix)
print("Nearest Neighbor - Path:", nn_path, "Cost:", nn_cost)

Nearest Neighbor - Path: [0, 9, 5, 2, 1, 8, 6, 3, 4, 7, 10, 0] Cost: 54

# prompt: generate code to construct the graph for the above three algorithms comparing path cost and one more graph for path taken

import matplotlib.pyplot as plt

# Assuming brute_force_path, brute_force_cost, dp_path, dp_cost, nn_path, nn_cost are defined from previous code

algorithms = ['Brute Force', 'Dynamic Programming', 'Nearest Neighbor']


costs = [brute_force_cost, dp_cost, nn_cost]

# Bar chart for path costs


plt.figure(figsize=(8, 6))
plt.bar(algorithms, costs, color=['skyblue', 'lightcoral', 'lightgreen'])
plt.xlabel("Algorithms")
plt.ylabel("Path Cost")
plt.title("Comparison of Path Costs for TSP Algorithms")
plt.show()

# Helper function to visualize paths (assuming a 2D space for visualization)


def visualize_path(path, title):
x = [i for i in range(len(path))]
y = path
plt.figure(figsize=(8, 6))
plt.plot(x, y, marker='o', linestyle='-')
plt.xlabel("City Index")
plt.ylabel("City")
plt.title(f"Path Taken - {title}")
plt.show()

# Visualize paths taken by each algorithm


visualize_path(brute_force_path, "Brute Force")
visualize_path(dp_path, "Dynamic Programming")
visualize_path(nn_path, "Nearest Neighbor")
pen_spark Generate the above graphs should be simple and at each point it should represent city name search Close

chevron_left 1 of 1
chevron_right thumb_up thumb_down Use code with caution

# prompt: the above graphs should be simple and at each point it should represent city name

import itertools
import numpy as np
import matplotlib.pyplot as plt

# Distance Matrix (same as described above)


distance_matrix = [
[0, 5, 8, 9, 6, 7, 10, 12, 6, 4, 11],
[5, 0, 3, 7, 8, 4, 9, 11, 5, 6, 7],
[8, 3, 0, 5, 6, 3, 8, 9, 4, 7, 10],
[9, 7, 5, 0, 3, 6, 4, 10, 8, 9, 12],
[6, 8, 6, 3, 0, 7, 5, 9, 4, 10, 13],
[7, 4, 3, 6, 7, 0, 5, 6, 7, 5, 8],
[10, 9, 8, 4, 5, 5, 0, 7, 3, 8, 6],
[12, 11, 9, 10, 9, 6, 7, 0, 5, 7, 4],
[6, 5, 4, 8, 4, 7, 3, 5, 0, 9, 10],
[4, 6, 7, 9, 10, 5, 8, 7, 9, 0, 11],
[11, 7, 10, 12, 13, 8, 6, 4, 10, 11, 0]
]

# City names corresponding to the indices in the distance matrix


city_names = ["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K"]

# Function to calculate total path cost


def calculate_path_cost(path, distance_matrix):
cost = 0
for i in range(len(path) - 1):
cost += distance_matrix[path[i]][path[i + 1]]
cost += distance_matrix[path[-1]][path[0]] # Return to the starting point
return cost

# ... (rest of your TSP algorithms: tsp_brute_force, tsp_dynamic_programming, tsp_nearest_neighbor)

# ... (your existing code for bar chart visualization)

# Helper function to visualize paths with city names


def visualize_path(path, title):
plt.figure(figsize=(8, 6))
# Convert numerical city indices to city names
city_labels = [city_names[i] for i in path]

x = np.arange(len(path))
y = [0] * len(path) # y-coordinates set to 0 for simple horizontal line representation
plt.plot(x, y, marker='o', linestyle='-') # Plot points

# Add city labels as annotations


for i, label in enumerate(city_labels):
plt.annotate(label, (x[i], y[i]), textcoords="offset points", xytext=(0,10), ha='center')

plt.xlabel("City Order")
plt.ylabel("City")
plt.title(f"Path Taken - {title}")
plt.yticks([]) # Remove y-axis ticks
plt.show()

# Example usage
visualize_path(brute_force_path, "Brute Force")
visualize_path(dp_path, "Dynamic Programming")
visualize_path(nn_path, "Nearest Neighbor")

You might also like