Hlavní navigace

Nové řešení problému obchodního cestujícího

Sdílet

Jan Fikar 9. 10. 2020
Problém obchodního cestujícího

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)

Našli jste v článku chybu?