TSP Approximation Algorithms | Solving the Traveling Salesman Problem

This video explores the Traveling Salesman Problem, and explains two approximation algorithms for finding a solution in polynomial time. The first method explained is a 2-approximation that uses a minimum spanning tree (MST) and depth first search (DFS). The second method is Christofides' algorithm, which combines perfect matching with a minimum spanning tree. TSP is a classic NP-Hard problem.
I recommend you first watch the following videos on MSTs and DFS, which I reference in this video:
► Kruskal's Algorithm: • Kruskals Algorithm for...
► Prim's Algorithm, • Prims Algorithm for Mi...
► Depth First Search, • Depth-First Search Alg...
Some of my other related graph videos:
► Dijkstras Intro • Dijkstras Algorithm fo...
► Dijkstras on Directed Graph • Dijkstras Algorithm Di...
► Bellman-Ford • Bellman-Ford Single-So...
► Bellman-Ford Example • Bellman Ford Algorithm...
► Floyd-Warshall • Floyd Warshall Graph T...
► Floyd-Warshall on Undirected Graph • Floyd Warshall Algorit...
► Breadth First Search • Breadth First Search -...

[@aysearslan2819]

nice jumpscare with the plane

[@MrFlipflops4]

Give this man a raise!! So helpful!

[@daanvandenberg4056]

I think you're doing great work in making these algorithms widely understandable for a broad class of people. Might use your video's sometime in a course for my students or so.

[@andrewhudson3723]

A great description of a hard problem.

[@MarcoAurelio-zu7sd]

Thank you for sharing!

[@kushagragupta6354]

that plane crash effect was amazing!!😂😂👍👍

[@oggiai]

glad you liked it!

[@lorossi1196]

Jump to 8:48 to see what happens when you don't go the optimal route and the airplane runs out of fuel

[@oggiai]

LOL>

[@ZapOKill]

and now the trivial part of solving min-weight perfect match

[@oggiai]

I was thinking of doing the 0-1 Knapsack problem next

[@daanvandenberg4056]

I think there might be a few slight mistakes in the OPT

[@darrenyeung2234]

Yea its wrong. It should be OPT >= MST and Approximation

[@ashrafyawar1039]

@Joe James, could you help me out on generalized version of christofies algorithm ?

[@christopherlperezcruz1507]

Doing Hungarian Method on excel. Using row and column reduction then penalty for each 0. When the penalties are equal I end up marking both bc I can't figure how to choose. Will this affect my optimality?

[@dorsamotiallah3998]

Thank you so much ❤️

[@kunalgarg1187]

Can you solve my problem...i have question related to this

[@darbyl3872]

What algorithm allows a node to be visited more than once? The one-time restriction does not always give the optimal route (in real life).

[@kMuhammadRayanAli]

8:50 why 😭😭😭😭

[@srishtiarora6424]

how can we add edges of M to T? Won't it change the original graph?

[@Kuchenklau]

No, as the original graph is a complete graph. Any edges added have already been there in the first place.

[@chinitatuntun]

Thanks for the Traveling Sales PERSON problem! :)

[@amerm.alnajada7442]

hello I found the exact solution of this problem . How can I send it to win a prize and get the right of possession?

[@anuragturkar7927]

Why the plane crash, I thought it was an Ad.

[@oggiai]

Oh, just for fun

[@randy4443]

Didn't we violate the rule of not visiting a node more than once?

[@oggiai]

No, the goal is to find a circuit that visits each node exactly once. But we may visit each node multiple times to find that circuit.