Deník N

Na tohle je každý počítač příliš pomalý

Kam teď, aby se cesta vyplatila? Zbývá ještě hodně měst. Foto: Adobe Stock
Kam teď, aby se cesta vyplatila? Zbývá ještě hodně měst. Foto: Adobe Stock

Problém obchodního cestujícího je velmi snadný. Právě proto je tak strašidelný. Nechce se po vás nic víc než najít nejkratší trasu spojující několik měst.

Nejspíš ho znáte, ale velmi stručně si zopakujeme, oč jde. Máme obchodního cestujícího, po česku cesťáka (v američtině to je obráceně, cestující obchodník neboli traveling salesman, odtud běžně používaná zkratka TSP, traveling salesman problem). Jeho úkolem je vyjet z domova, navštívit postupně N měst a zas se vrátit domů. Přitom chce, aby celková trasa byla nejmenší možná. Zkusme to pro N = 3. Obchodník vyjíždí z Brna, má navštívit Uherské Hradiště, Zlín a Olomouc a vrátit se do Brna. Vzdálenosti (po silnici, podle Google Maps) jsou:

  • Brno – Zlín: 98
  • Brno – Uherské Hradiště: 79
  • Brno – Olomouc: 80
  • Zlín – Uherské Hradiště: 27
  • Zlín – Olomouc: 74
  • Uherské Hradiště – Olomouc: 92

Možné cesty jsou tři:

  • B-Z-U-O-B: 297
  • B-Z-O-U-B: 343
  • B-O-Z-U-B: 260

Obchodník tedy musí jet buď v pořadí Uherské Hradiště, Zlín, Olomouc, anebo naopak Olomouc, Zlín, Uherské Hradiště, protože na směru nezáleží. (Mohlo by – v některých variantách TSP jsou vzdálenosti mezi městy jedním a druhým směrem obecně různé. Například kvůli jednosměrkám. Pak musíme počet cest vynásobit dvěma.)

Čtyři města, žádný problém. Obr. Deník N.

Tenhle výsledek jsme spočetli snadno a nejspíš bychom ho dokázali uhodnout pohledem na mapu. Za povšimnutí však spojí použitý postup: spočetli jsme délky všech myslitelných cest a podívali se, která z nich je nejkratší. Museli jsme tedy spočítat 1 × 2 × 3 / 2 = 3 cesty, kde 3 je počet navštívených měst (matematik by řekl: počet uzlů grafu, na němž TSP řešíme).

Faktoriál? To je konečná

Matematik by také řekl, že příslušný výpočet můžeme zapsat jako N!/2. Výraz N! se čte „en faktoriál“ a je to zkratka pro součin čísel 1, 2, 3 až N. Potíž spočívá právě v tom faktoriálu, roste totiž

Tento článek je exkluzivní obsah pro předplatitele Deníku N.

V tomto okamžiku nejčtenější