Úloha obchodního cestujícího, Littlův algoritmus

Littův algoritmus slouží pro nalezení minimálních (maximálních) hamiltonovských kružnic grafu. Název úlohy vychází z toho, že hamiltonovskou kružnici je možné pokládat za cestu obchodního cestujícího, který musí navštívit všechna místa (vrcholy grafu), každé pouze jednou a vrátit se do místa odkud vyšel s tím, že celková projetá vzdálenost (celkový čas strá-vený v dopravním prostředku) bude minimální. Úloha dlouhou dobu odolávala úsilí o její úspěšné řešení. Teprve v roce 1963 Little publikoval přesnou metodu optimalizace. Little v algoritmu využívá principu metody větve a hranice (Branch & Bound).