Algorithms for NP-Hard Problems (Section 20.4: The 2-OPT Heuristic for the TSP) [Part 2/2]

Introduction to local algorithms through the 2-OPT heuristic for the Traveling Salesman Problem.
Accompanies Section 20.4 of the book Algorithms Illuminated, Part 4: Algorithms for NP-Hard Problems (www.algorithmsi...)
Full playlist: • Algorithms Illuminated...

[@coemgeincraobhach236]

Thanks for that! really well explained!

[@RayRay-yt5pe]

Thank you so much

[@rippi0815]

How do you calculate the costs of the green tours?

[@timgluz]

Question, what's the described algorithm to iterate over k-opt pairs?
is it something like this:
for i in 1 to n-4:
for j in i+2 to n:
pair1 = (i, i+1)
pair2 = (j, j+1)
Thank you

[@NS-gr9cy]

Why the network with score 23 not tried to improve further?

[@eng.i8823]

Yeah right!

[@sayc1333]

the professor is showing you all the possible changes at each iteration, but he explains at 2:36 that for now we are just taking the first discovered improvement