Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

YouTube

The Traveling Salesman Problem - When Good Enough Beats Perfect

Reducible via YouTube

Overview

Explore the complexities of the Traveling Salesman Problem (TSP) in this 30-minute video by Reducible. Dive into the challenges this notorious problem presents for computer scientists and discover clever methods used to solve it. Learn why brute force solutions and exact approaches fail for large instances, then explore heuristic-based approaches like nearest neighbors, greedy algorithms, and Christofides method. Understand how to improve candidate solutions through local search techniques, including 2-opt, random swapping, and 3-opt improvements. Delve into advanced search space analysis methods such as simulated annealing and ant colony optimization. Gain insights into lower bounding TSP and various tour improvement techniques, all explained through engaging animations and clear explanations.

Syllabus

Intro
Problem Definition
Why Finding Optimal Solution Is Practically Impossible
Nearest Neighbor Heuristic
Lower Bounding TSP
Greedy Heuristic
Christofides Algorithm
Sponsor CuriosityStream
Tour Improvements
Simulated Annealing
Ant Colony Optimization
Conclusion

Taught by

Reducible

Reviews

Start your review of The Traveling Salesman Problem - When Good Enough Beats Perfect

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.