Minesweeper je videohra z roku 1990. Nalezení řešení jedné její instance nebo důkaz jeho neexistence je NP úplný problém. V této práci prozkoumám algoritmy, které tento problém řeší v polynomiálním nebo exponenciálním čase s různou úspěšností. Implementuji svůj vlastní algoritmus s důrazem na vysokou úspěšnost a využitelnost při generování pole. Nakonec také implementuji algoritmus, který je schopný generovat pole hry minesweeper, které je vždy řešitelné a zavedu nové hodnocení obtížnosti, které tento algoritmus využívá. NP úplné a NP těžké problémy jsou velmi frekventované, lze se s nimi setkat při zajišťování kybernetické bezpečnosti, vývoji nových léků, alokaci zdrojů nebo například při obecném prohledávání stavového prostoru. Hodně NP problémů jde řešit pomocí algoritmů s polynomiální složitostí, které je řeší s vysokou úspěšností, ale nikomu se nepodařilo dokázat, že lze NP problémy v polynomiálním čase vyřešit deterministickým automatem nebo naopak možnost řešení deterministicky v polynomiálním čase vyloučit, proto je každé jejich studium přínosné.
展开▼
