Traveling Salesman Problem (TSP) Presentation
Slide 1: Title Slide
Title: Dynamic Programming Approach to the Traveling Salesman Problem (TSP) Subtitle: An Optimal
Solution for the TSP Using Bitmasking and Memoization Presented By: [Your Name]
Slide 2: Introduction to TSP
Title: What is the Traveling Salesman Problem? Content:
The Traveling Salesman Problem (TSP) is a classic optimization problem.
Objective: Find the shortest route that visits all given cities exactly once and returns to the
starting city.
Input: A cost matrix representing distances between cities.
Output: The minimum cost and the optimal path.
Slide 3: Algorithm Overview
Title: Dynamic Programming Approach Content:
Key Techniques:
o Bitmasking: Represents the set of visited cities.
o Memoization: Stores solutions to overlapping subproblems.
Steps:
1. Start with the first city.
2. Explore all unvisited cities recursively.
3. Use memoization to avoid redundant calculations.
Optimal path is reconstructed using a parent table.
Slide 4: Flowchart
Title: Algorithm Flowchart Content: (Include a flowchart diagram)
1. Start at the first city.
2. Check if all cities have been visited (base case).
3. If not, recursively visit unvisited cities.
4. Update the memoization table with the minimum cost.
5. Reconstruct the path from the parent table.
6. End.
Slide 5: Pseudo Code (Part 1)
Title: TSP Recursive Function Content:
function tsp(i, mask):
if mask == (1 << n) - 1:
return dist[i][0] // Return to starting city
if dp[i][mask] != -1:
return dp[i][mask] // Return cached result
min_cost = INF
for each city j:
if j is not visited (mask & (1 << j) == 0):
cost = dist[i][j] + tsp(j, mask | (1 << j))
if cost < min_cost:
min_cost = cost
parent[i][mask] = j // Update parent
dp[i][mask] = min_cost
return min_cost
Slide 6: Pseudo Code (Part 2)
Title: Path Reconstruction Content:
function printPath():
mask = 1 // Starting city is visited
i=0 // Starting city index
print(i + 1) // Print starting city
while mask != (1 << n) - 1:
next_city = parent[i][mask]
print("--->", next_city + 1)
mask |= (1 << next_city)
i = next_city
print("--->", 1) // Return to starting city
Slide 7: Time Complexity Analysis
Title: Time Complexity of the Algorithm Content:
State Space:
o Number of states = n * 2^n (city and bitmask combination).
Recursion Per State:
o Each state makes O(n) recursive calls.
Overall Complexity:
o O(n^2 * 2^n)
Suitable for small to medium-sized problems (e.g., n <= 20).
Slide 8: Real-Life Applications
Title: Applications of TSP Content:
Logistics and Delivery: Optimizing delivery routes for vehicles.
Circuit Design: Minimizing the length of wiring in PCB layouts.
Travel Planning: Finding the shortest route for visiting tourist attractions.
Robotics: Efficient movement of robotic arms.
Slide 9: Graphical Working Example (aita ektu valo koira dekhte hobe madam bolchilo)
Title: Visualizing the Algorithm Content:
1. Initial State: Start at City 1.
2. Recursive Exploration: Visit unvisited cities.
3. Update Memoization: Store minimum cost for each state.
4. Path Construction: Trace back the optimal path from the parent table. (Include a graphical
example with cities and edges labeled with distances.)
Slide 10: Conclusion
Title: Conclusion Content:
Dynamic programming effectively solves TSP for up to 20 cities.
The algorithm ensures optimal solutions by using memoization and bitmasking.
Practical applications span logistics, robotics, and more.
Slide 11: Questions
Title: Thank You Content:
Feel free to ask questions.
Contact: [Your Email/Contact Info]
