| Abstrakt: | V tejto práci sa venujeme hre pre jedného hráča, s ktorou sa môžeme stretnúť pod názvom Net. V tejto hre má hráč pred sebou mriežku obdĺžnikového tvaru. Na každom políčku mriežky je časť potrubia, spájajúca niektoré okraje políčka. Potrubie môže byť niekoľkých typov. Na jednom z políčok sa nachádza zdrojové potrubie, ktoré produkuje vodu. Voda sa šíri medzi susednými políčkami, ktoré nasmerovali potrubie oproti sebe. Ťahy hráča spočívajú v otáčaní políčok o 90 stupňov a cieľom je, aby sa voda dostala do celej siete a aby na žiadne políčko nepritiekla z dvoch strán.
Prirodzenou otázkou je existencia riešenia pre danú mriežku. Cieľom práce je klasifikovať tento problém z hľadiska výpočtovej zložitosti. Pri uvažovaní môžeme meniť množinu prípustných typov potrubí v mriežke, čím sa nám môže meniť aj obtiažnosť úlohy. Je hypotéza, že pre štandardnú množinu potrubí, s ktorou sa stretne hráč pri implementáciach tejto hry na internete, je problém zistenia existencie riešenia NP-úplný. V našej práci sa nám to nepodarilo potvrdiť ani vyvrátiť. Súčasťou práce sú aj optimalizované algoritmy, ktoré síce majú exponenciálnu časovú zložitosť, avšak momentálne sú najlepšie známe. Okrem toho sme ukázali, že pre menšie množiny prípustných typov potrubí je problém zisťovania existencie riešenia v P.
|
|---|