Problem komiwojażera, czyli jak obliczyć coś, czego nie da się obliczyć

Chcemy odwiedzić n miast tak, aby przebyta przez nas trasa była jak najkrótsza. Jest to słynny problem NP-trudny, co oznacza, że najprawdopodobniej nie da się napisać programu komputerowego, który zawsze w rozsądnym czasie znajdowałby najkrótszą trasę. A jednak powstał program komputerowy, który znalazł najkrótszą trasę dla 49603 "historycznych" miejsc w USA. Czy praktyce udało się oszukać teorię? Podczas wykładu zobaczymy, że w rzeczywistości był to efekt współpracy teorii i praktyki. Dowiemy się, jak działa algorytm zastosowany we wspomnianym programie i skąd wiadomo, że znaleziona trasa jest faktycznie najkrótsza.