Problém obchodního cestujícího je známý optimalizační oříšek teoretické informatiky. Přesné řešení lze dosáhnout jen hrubou silou, přitom počet možných kombinací však roste s počtem měst jako jejich faktoriál, proto je toto řešení nepraktické již od zhruba 20 měst.
V roce 1979 nezávisle na sobě objevili Christofides a Serdyukov algoritmus přibližného řešení, které je v nejhorším případě jen 1,5 krát horší než optimální řešení. Tento algoritmus byl doposud nejlepším přibližným řešením. Výzkumníci z university ve Washingtonu však přišli s novým algoritmem, který je v nejhorším případě 1,5–10-36 krát horší než optimální řešení. Vylepšení sice není zásadní, je ale možné, že odstartuje nová řešení starého problému. Více detailů v článku.
(zdroj: slashdot)
