Dnešní hádanka po vás zase bude chtít vymyslet způsob, jak zachránit svět. Je to problém, související s tzv. NP-úplností, o které si více můžete počíst třeba zde. Poznámka na konci o obchodním cestujícím je narážka na zcela klasickou úlohu, která do této kategorie problémů spadá. Podělte se s námi v komentářích o to, jak snadno či nesnadno se vám (ne)podařilo najít řešení.
PRAVIDLA:
1. Do budovy musíte vstoupit vstupem a odejít z ní musíte východem.
2. Každá místnost, s výjimou vstupu, je kontaminována.
3. Jakmile vstoupíte do kontaminované místnosti, musíte zatáhnout za páku autodestrukce.
4. Po zatažení za páku musíte místnost okamžitě opustit.
5. Do místnosti, kde jste již autodestrukci aktivovali, se již nemůžete vrátit.
Váš výzkumný tým našel prehistorický virus,
který byl uchován v permafrostu, a izoloval ho pro následné zkoumání. Po dlouhé noci v práci
zrovna zavíráte laboratoř, když najednou udeří zemětřesení
a způsobí výpadek elektřiny. Když naběhnou záložní generátory, alarm potvrdí vaše nejhorší obavy. Všechno zkumavky s virem se rozbily. Virus je zatím izolován,
ale pokud ho nezničíte, zanedlouho se spustí klimatizace,
která tento smrtící virus vypustí do světa.
Bez váhání popadnete ochranný oblek a připravíte se zachránit svět. Laboratoř je tvořena 16 místnostmi,
v mřížce 4 krát 4 místnosti. Vstup do ní je na severozápadním rohu
a východ je v jihovýchodním. Každá místnost je spojena s vedlejšími
pomocí přetlakové komory a virus byl vypuštěn
ve všech místnostech, s výjimkou vstupu. Abyste ho zničili, musíte
vstoupit do každé kontaminované místnosti a zatáhnout za páku autodestrukce.
Ale má to háček. Protože je aktivní karanténa, jakmile vstoupíte
do kontaminované místnosti, nemůžete odejít,
aniž byste za páku zatáhli. A jakmile to uděláte, nebudete se do této místnosti
moci vrátit. Začnete si na papír kreslit možné cesty, ale zdá se, že se nemůžete
dostat k východu, aniž byste nevynechali
aspoň jednu místnost.
Jak tedy můžete zničit virus
v každé kontaminované místnosti a přežít toto dobrodružství? POKUD CHCETE NA ŘEŠENÍ PŘIJÍT SAMI,
VIDEO SI NYNÍ ZASTAVTE PRAVIDLA JSOU V POPISKU
ODPOVĚĎ ZA: 3, 2, 1. Pokud je vaším prvním instinktem
udělat si graf možných cest, jdete na to správně.
Tato hádanka souvisí
s problémem hamiltonovské cesty. Ta je pojmenována po irském matematikovi
z 19. století, Williamu Rowan Hamiltonovi. Problémem hamiltonovské cesty je zjistit, má-li daný graf
tzv. hamiltonovskou cestu. To je cesta, která navštíví každý bod
tohoto grafu právě jednou. Tento typ problému,
který je klasifikován jako NP-úplný, je nesmírně obtížný,
je-li graf dostatečně veliký. Přestože lze jakékoliv
navrhované řešení jednoduše ověřit, nemáme žádný spolehlivý vzorec
či zkratku, jak k němu dojít.
Nebo jak zjistit, zda vůbec existuje. A nejsme si ani jisti, jestli je možné,
aby počítač spolehlivě takové řešení našel. Tato hádanka přidává do problému
hamiltonovské cesty další podmínku, protože musíte začít
a skončit na konkrétních místech. Ale než vyplácáte tunu papíru, měli byste vědět,
že hamiltonovská cesta není s těmito body možná.
To proto, že místnosti tvoří mřížku
se sudým počtem místností na obou stranách. V každé mřížce,
která je takto nastavena, je nemožné vytvořit
hamiltonovskou cestu, jejíž začátek a konec
jsou v protilehlých rozích. Zde je příklad, který to může osvětlit. Představte si šachovnici,
která má na každé straně sudý počet polí. Na každé cestě se budou
střídat černá a bílá pole. Tyto mřížky budou také mít
sudý celkový počet polí, protože sudé číslo krát sudé číslo
dává sudý výsledek.
Takže hamiltonovská cesta
na mřížce o sudém počtu polí, která začíná na černém poli,
bude muset skončit na bílém poli. A ta, která začíná na bílém poli,
musí skončit na černém. Avšak v každé mřížce
o sudé velikosti stran mají protilehlé body stejnou barvu, takže je nemožné začít a skončit
hamiltonovskou cestu v protilehlých rozích. Zdá se, že máte smůlu, pokud se pořádně nepodíváte na pravidla a nevšimnete si důležité výjimky.
Je pravda, že jakmile aktivujete
páku v kontaminované místnosti, je místnost zničena
a vy se nemůžete vrátit. Ale jedna místnost kontaminována nebyla. Vstup. To znamená, že z ní můžete jednou odejít,
aniž byste za páku zatáhli, a vrátit se do ní poté, co jste zničili
jednu z těchto dvou místností.
Je možné, že byla tato místnost
tímto krokem kontaminována. Ale to nevadí, protože vstup
můžete nyní zničit. Tato zpáteční cesta
vám dává čtyři možnosti cesty, a podobné možnosti,
pokud jste nejprve zničili tuto místnost. Gratulujeme, zabránili jste
epidemii apokalyptických rozměrů. Ale po tak náročné akci potřebujete pauzu. Možná byste měli přijmout
pracovní nabídku a stát se obchodním cestujícím.
XardassPublikováno: 8 let
