Úlohy na procvičení – grafy
Cesta králem na šachovnici (délka)
Řešte úlohu Cesta králem na šachovnici (délka) v ReCodExu. Program bude hledat nejkratší cestu šachovým králem na šachovnici \(8 \times 8\), kde na některá políčka nelze vstoupit.
Můžete použít šablonu, která za vás vyřeší načítání vstupu (v původním vstupu jsou souřadnice políček 1 až 8, ale v reprezentaci v šabloně jsou 0 až 7). Do šablony stačí doplnit procházení možných tahů krále (metoda get_neigbors) a dokončit předpřipravený kód pro bfs.
Nejkratší cesta v ohodnoceném grafu
Problém nejkratší cesty lze zobecnit na grafy s nezáporným ohodnocením hran, kde je délka cesty měřena součtem ohodnocení hran.
Nalezne algoritmus BFS nejkratší cestu i v tomto případě? Pokud ano, vysvětlete proč, pokud ne, sestrojte protipříklad.
Přelévání vody
Řešte úlohu Přelévání vody v ReCodExu. Program bude prohledávat stavový prostor při přelévání vody mezi třemi nádobami.
Společně si na cvičení rozmyslíme, jak stavový prostor reprezentovat jako graf (jaké informace potřebujeme pro reprezentaci stavu) a jaké budou přechody (hrany) mezi stavy.
Pro implementaci pak můžete použít šablonu. V ní už je implementován algoritmus BFS a je potřeba doplnit kód pro přechody mezi stavy (funkce get_neighbors) a pro následné zpracování vypočtených vzdáleností (funkce get_volumes).