Student World

Jedna z variant populární úlohy obchodního cestujícího zní takto: Musíte propojit body sítě (města) tak, aby síť byla celistvá (odkudkoliv se šlo dostat kamkoliv, žádné izolované „ostrovy“) a její celková délka co nejkratší. Jak vidno, oproti nejčastějšímu zadání příkladu je zde jistý rozdíl – obchodní cestující zde musí projekt všechna města, nemusí se však už vrátit.

Představte si, že máme 4 města, ležící ve vrcholcích čtverce. Jak najít optimální trasu? Spojení po obvodu má délku 3 (strana čtverce o délce 1), síť složená ze dvou protínajících se úhlopříček 2 * SQR 2, což je méně. Ani to ale není řešení. Tím je kupodivu pět úseček se dvěma průsečíky tří z nich pod úhlem 120 stupňů – viz obrázek.

(Tato síť má délku 1 + SQR 3, což spočítat není taktéž úplně triviální.)
Je jasné, že při více vrcholech narazíme i v této variantě obchodního cestujícího na známé problémy s rostoucí výpočetní složitostí.

Existuje vtipný způsob, jak tento problém řešit pomocí jakéhosi analogového počítače, kterým jsou v tomto případě mýdlové bubliny.
„Vezmeme dvě desky z průhledného plexiskla propojené čtyřmi kolíky umístěnými do vrcholů čtverce. Ponoříme-li toto zařízení do mísy s mýdlovou vodou a zase je vytáhneme, dostaneme mýdlovou blánu s povrchem menším, než by měl jakýkoli jiný tvar byť jen málo odlišný,“ píše Acheson.

Zdroj: David Acheson: 1089 a další parádní čísla, Dokořán, Praha 2006
http://www.dokoran.cz/index.php?1089_a_dalsi_paradni_cisla&p=book.php&id=185

Poznámka: Samozřejmě si nemůžeme být jisti, zda náš bublinový počítač skutečně našel nejlepší řešení (z řady důvodů). Nicméně to, zda určité řešení úlohy obchodního cestujícího je správné, již můžeme ověřit v polynomiálním čase. Bubliny nám tedy dají první nástřel.
V našem příkladu se čtvercem bychom bez bublin nejprve zjistili, že „intuitivní“ úhlopříčková síť není minimální, neměli bychom ale tušení, jak minimum nalézt.
Samozřejmě asi nikdo reálně neuvažuje, že by to bylo prakticky využitelné… ale nakonec kdo ví?

autor Pavel Houser