Pokud bys byl obchodník z Liberce, který se rozhodne navštívit zákazníky v devíti různých městech, vrátit se zpátky do Liberce a přitom najet co nejméně kilometrů. Jak bys postupoval?
Problém obchodního cestujícího je jedna z nejznámějších optimalizačních úloh, protože ji v praxi využívá mnoho profesí, jako například kurýr s balíky, který chce všechny adresy projít co nejdříve.
Podobný problém řešíš často i ty, například když vejdeš do nákupního centra a víš, které obchody chceš navštívit. Hledáš takovou cestu, během které navštívíš všechny a nejméně se zapotíš. Nakonec se musíš vrátit zpět ke hlavnímu vchodu.
Při problému obchodního cestujícího je úkolem, aby ses z bodu A dostal přes body B, C a D zpět do bodu A. Avšak co nejkratší trasou.
Úsečce mezi každými dvěma body (obcemi) přiřadíš hodnotu (vzdálenost v km). Potom jen hledáš nejmenší součet hodnot úseček (cest), přes které musíš projít, abys splnil úkol.
Jak postupovat?
Šli bychom na to metodou rozhodovacího stromu. Pomocí něj nakreslíme úplně každou cestu, kterou se můžeme vybrat a splňuje podmínky (každé místo navštívíme právě jednou a cestu ukončíme tam, kde jsme ji začali).
Jak by to vypadalo pro úlohu na mapě České republiky?
Jak můžěš vidět, rozhodovací strom i počet možných cest roste se zvyšováním počtu uzlů velmi prudce. Vytvoření takového stromu už pro 10 míst by člověku trvalo velmi dlouho. Proto nám v tomto pomáhají počítače, které vypočítají délku všech možných cest a najdou nejkratší.
Celý rozhodovací strom se nám na stěnu nevejde, ale pouvažuj, kolik možných cest pro našeho obchodníka existuje?
Minimálně kolik bude vždy správných řešení (nejkratších cest)?