iwtu wrote:Pokial je mi zname, tak je to iba prehladavanie stavoveho priestoru a neprechadzat stavy, v ktorych sme uz boli alebo ktorych je zle (deadlock). Nieco na principe Sokoban.
Je to přesně tak. Pokusím se to trochu rozvést.
Místnosti si pro přehlednost očíslujeme. S názvy by se pracovalo špatně. A na základě vstupního souboru vytvořím nějakou reprezentaci grafu. Nejlepší je asi seznam sousedů pro každý vrchol.
Každý z hrdinů je po skončení kola (v celou minutu) vždy právě v jedné místnosti. Tedy pozici každého hrdiny můžeme popsat pomocí číslice od 1 do 100 (číslo místnosti), mám tři hrdiny. Tedy celkem mám 100^3 = 10^6 možných stavů, které mohou nastat. To je dost, ale ne tak moc, abych je nemohl všechny projít. Počáteční i koncový stav znám.
Budu prohledávat do šířky. Přitom si budu navíc udržovat trojrozměrné pole 100x100x100 booleanů, kde si o každém stavu (ona trojice čísel) zapamatuji, jestli jsem se do něj už dostal. Pokud bych chtěl přejít do nějakého stavy, tak tedy v O(1) snadno zjistím, jestli jsem ho už neprozkoumal nebo jestli jeho prozkoumání už není v plánu.
Skončím ve chvíli, kdy se dostanu do cílového stavu nebo až projdu všechny možné (fronta se vyprázdní).
Zbývá se ještě nějak vypořádat s paměťovou složitostí. Omezení 4MB je akorát hraniční. Na trojrozměrné pole všech stavů spotřebuji akorát 1MB. Uložení vlastního grafu bludiště je zanedbatelné. Stejně tak nějaké pomocné proměnné.
Zbývají tedy cca 3MB na frontu. Frontu při prohledávání do šířky bude lepší reprezentovat polem - při použití spojového seznamu přibývají navíc ukazatelé. Celkově může být ve frontě až 10^6 záznamů (třeba pro úplný graf), tedy potřebuji pole délky 10^6. Pro jeden záznam mi tedy zbývají 3B paměti, což je akorát na trojici čísel určující stav. Nemohu si tedy u stavu pamatovat, kolik minut už uplynulo (což by bylo také dost prostorově neekonomické, neboť číslo minuty je 1 až milion a spousta po sobě jdoucích stavů má toto číslo stejné). To vyřeším tak, že ve chvíli, kdy se dostanu do další minuty, si do fronty uložím nějaký speciální oddělovač. Třeba nějaký stav, který nemůže nastat. Pokud narazím na tento oddělovač, zvýším si centrální čítač kol.Zároveň vím, že všechny stavy jsou teď ze stejné minuty. Další ale budou až o minutu později, proto oddělovač znovu přidám na konec fronty. V každém okamžiku může být ve frontě jen jeden oddělovač, tedy na požadovanou maximální délku fronty to nemá vliv (rozmysli si, že to vyjde i pro úplný graf).
Časová složitost v mé implementaci vyšla O(M^6), kde M je počet místností. Pro M = 100 tak dostáváme řádově 10^12 operací. To je opět akorát tak na hranici. Procesor s frekvencí 1GHz vykoná 10^12 instrukcí přibližně za 20 minut. Musíme si ale uvědomit, že tato složitost odpovídá grafům se spoustou hran. Typické bludiště bude mít z každé místnosti třeba maximálně 10 chodeb. Pak lze složitost omezit na O(M^3). (Rozmysli si matematický trik.)
