Projdi bludiště, zachráníš kozu

Co se naučíš:

• Orientovat se v nakresleném stavovém prostoru
• Sestrojit stavový prostor a najít v něm řešení problému

Návrh průběhu hodiny a metodické poznámky

• Stručný průběh a poznámky
• Podrobný plán (příprava do hodiny)

Úvodní úloha

Zkuste vyřešit následující úlohu. Všímejte si, kdy řešíte metodou pokus-omyl a kdy postupujete systematicky.

Úloha:

Vracíte se domů jako každý den se svým vlkem, kozou a obrovskou hlávkou zelí. Jenže u přívozu není převozník, který vás jinak vždy postupně převeze. Musíte se přes řeku převézt sami. Na přívoz se vejde člověk a pak už jen jeden kus nákladu. Přitom ale nikdy nesmí bez dozoru zůstat vlk a koza, ani koza a zelí.

Jak převážení zorganizovat, aniž by došlo k nějaké úhoně?

Bylo to těžké? A umíte navíc ukázat, že je váš postup řešení nejlepší, a jestli existují nějaké další? Případně, pokud řešení neexistuje, umíte ukázat „Zkoušel jsem to opravdu dlouho“ žádného informatika jako důvod nepřesvědčí.

Bludiště

Úloha:

Najděte cestu mezi zelenými políčky v následujícím bludišti (klepněte na rozbalovací tlačítko).

Najdete v bludišti cestu mezi dvěma zelenými poli?

Najít cestu v bludišti se zdá mnohem jednodušší, než vyřešit úlohu s převážením. Ukážeme si ale, že je to totéž.

Podívejte se na bludiště s doplněnými popisky.

Obrázek stavového prostoru pro vlka, kozu a zelí, včetně označení stavů.

Obtížnost úlohy s převážením spočívá ponejvíce v udržení přehledu o tom, co už jsme zkoušeli (netočit se v kruzích) a nevynechání žádné možnosti, která by mohla vést k cíli.

Prvním krokem k tomu, abychom tyhle nepříjemnosti odstranili, je začít sledovat, co už jsme vyzkoušeli. Abychom si mohli zaznamenat stav, ve kterém se zrovna nacházíme, muslíme nejprve rozmyslet, čím vším je stav určen. V případě úlohy o převážení je jasné, že nás zajímá, na které straně řeky se nacházejí vlk, koza a zelí. Nesmíme ale zapomenout také na polohu lodičky (i s "převozníkem"). Tomu odpovídají označení jednotlivých stavů na obrázku výše. Svislá čára symbolizuje řeku a tím značí, na které straně se co nachází. Písmena jsou podtržená na té straně, na které je v daném stavu lodička. Chceme se tedy dopracovat ze stavu zakódovaného jako VKZ| do stavu |VKZ.

Stanovené označování stavů nám umožní vypisovat, kterých stavů jsme již dosáhli, a kontrolovat, abychom nezkoušeli totéž stále dokola. Nezjistíme ale, jestli jsme žádnou možnost nevynechali. Proto jednotlivé stavy propojíme podle toho, jak mezi nimi lze přecházet. Pak můžeme mnohem snáz zkontrolovat, jestli jsme v každém stavu vyzkoušeli všechny možnosti.

Proč právě stavový prostor?

Je to trochu zvláštní. Ve stavovém prostoru přece nechodíme doleva a doprava, dopředu a dozadu, nahoru a dolů. Matematici a informatici ale používají pojem prostor mnohem obecněji, nejen pro prostor, v němž se fyzicky pohybujeme. Existují různě abstraktní varianty. Zjednodušeně ale můžeme říct, že když někde můžeme rozlišovat místa (body, nebo jako zde stavy) a má smysl uvažovat o vzdálenosti mezi nimi, často metaforu postoru využijeme. Díky tomu pak třeba při práci se stavovými prostory můžeme mluvit o cestách mezi stavy, o jejich délkách, o jejich systematickém procházení a tak podobně.

Ve výsledném diagramu potom už poměrně snadno najdeme cestu z výchozího do cílového stavu (nebo zjistíme, že taková cesta neexistuje). Všimněte si, že v tu chvíli už nijak nezáleží na tom, jestli se jedná o kozy v řece nebo otáčení pohárů. Hledáme prostě cestu grafem, stejně jako třeba GPS navigace v autě.

Graf, jehož vrcholy odpovídají stavům nějakého systému, a hrany odpovídají přechodům mezi těmito stavy, nazýváme stavový diagram, nebo také stavový prostor.

Příklad: Alternativní vysvětlení

Jestli se chcete podívat na vysvětlení s více obrázky a jinými slovy, doporučujeme tato dvě.

Shlédnutí různých variant téhož pomůže rozpoznat, co je při řešení pomocí stavového prostoru důležité a co nikoliv.

Poháry

Úloha: Otáčení pohárů

Na stole stojí pět pohárů, prostřední je překlopený dnem vzhůru. V jednom kroku se smí otočit vždy přesně 3 poháry: stojící se překlopí, překlopené se postaví.

Jak poháry otáčet, aby nakonec všechny poháry stály?

Nápověda

Postupuj podle kroků z předchozího popisu:

1. Rozhodni, čím přesně je definován stav, a jak to zaznamenávat.
2. Popiš výchozí stav.
3. Popiš cílový stav.
4. Postupně podle pravidel (otáčení tří pohárů) vytvářej další stavy a propojuj je do stavového prostoru, dokud se nedopracuješ do cílového stavu, nebo nevyčerpáš možnosti.

Přelívání vody a uspořádání stavového prostoru

Úloha:

Potřebujeme naměřit přesně 4 litry vody, jenže máme jen dvě nádoby, o objemu 5 a 3 litry. Jak postupovat?

Samotné řešení už by pro vás mělo být jednoduché. Ne každému se ale lehce hledalo mezi již zaznamenanými stavy (aby jeden stav nezaznamenali vícekrát). K tomu pomůže si stavy v nakresleném stavovém prostoru nějak systematicky uspořádat. V případě přelívání je stav definován objemem vody ve dvou nádobách, tedy dvěma celými čísly v rozsahu 0—5 a 0—3. Dvojice seřazených hodnot uspořádat umíme! Vzpomeňte si na šachovnici, tabulkový kalkulátor nebo na kreslení a vůbec pohyb ve Scratchi. Na dvojice hodnot se můžeme dívat jako na souřadnice.

Počáteční stav, kdy jsou obě nádoby prázdné (obsahují 0 litrů vody), umístíme do počátku (souřadnice [0,0]). Čtyři litry se vejdou jen do pětilitrové nádoby, takže konečné stavy budou (zakreslené na souřadnicích) [4,0], [4,1], [4,2], [4,3] (obsah druhé nádoby není pro splnění úkolu důležitý).

Stavy uspořádané podle souřadnic.

Zamysli se a odpověz:

Jak uspořádat stavové prostory v předchozích úlohách?

Velikost stavového prostoru

Důležitým kritériem pro rozhodnutí, jestli k řešení problémů využít stavové prostory, je jejich velikost. Pokud je stavový prostor příliš velký, může nám jeho prohledávání trvat příliš dlouho. Uvedené problémy jsou cvičné, ve skutečném světě se snadno setkáme s případy, kdy lze z každého stavu pokračovat třeba do osmi nových stavů a řešení vyžaduje desítky takových kroků.

Příklad: Velký stavový prostor

Celkem bychom tak dostali např. 8⁵⁰ stavů, což je (2³)⁵⁰ = 2¹⁵⁰ stavů. Když víme, že 2¹⁰ je o něco více než 10³, máme přibližně 2^15*10 ≈ 10^15*3 = 10⁴⁵ stavů. Kdybychom každý z nich zkontrolovali během jediného tiku gigahertzového procesoru, který tedy tikne miliardkrát (10⁹) za sekundu, potřebovali bychom 10^45-9 = 10³⁶ sekund. I kdybychom s tím začali na počátku samotného vesmíru, zdaleka bychom ještě nebyli hotovi. Museli bychom pokračovat ještě trilionkrát déle. I kdybychom použili všechny počítače na světě, výsledku bychom se nedožili.

Nechceme-li se zaplést do nezvládnutelného úkolu, vynasnažíme se počet stavů odhadnout předem.

Pro začátek si ukážeme dvě jednoduchá pravidla.

1. Pokud lze prostor rozdělit na několik částí, může být výhodné odhadnout velikost každé části a odhady následně sečíst.
2. Pokud je stav dán hodnotami několika proměnných se známým rozsahem, odhadneme celkový počet stavů součinem velikostí těchto rozsahů.

Příklad: Počet stavů při přelívání nádob

Máme nádoby, které plníme po celých litrech v rozsahu 0—3 a 0—5. Třílitrová nádoba se tedy může nacházet nanejvýš ve čtyřech různých stavech, pětilitrová v šesti.

Celkem tedy jistě neexistuje více než 4*6 = 24 různých stavů naplnění nádob. Nezapomeňte, že se jedná o horní odhad. Nikde není dáno, že bude všech 24 stavů opravdu dosažitelných. Určitě jich ale nebude víc.

Shrnutí

• Některé problémy můžeme modelovat pomocí stavových prostorů. Ty zachycují různé stavy, do kterých se při řešení problému můžeme dostat, a přechody mezi nimi.
• Ve stavovém prostoru se nebudeme točit v kruzích a zároveň žádný možný postup neopomeneme. Díky tomu můžeme např. rozhodnout, které řešení vyžaduje nejméně kroků, nebo např že žádné neexistuje.
• Nehledě na to, o čem vlastně konkrétní problém je, postupujeme pokaždé stejně:

1. Rozhodneme, čím přesně je definován stav, a jak to zaznamenávat. Přitom se snažíme pracovat právě jen s tím, co potřebujeme k vyřešení úlohy.
2. Popíšeme výchozí a cílový stav.
3. Postupně podle charakteru daného problému přidáváme do prostoru další stavy a jejich vzájemná propojení.
4. Nakonec buď narazíme na řešení (cílový stav), nebo zjistíme, že jsme vyzkoušeli všechny možnosti, do cíle nedošli, a řešení tedy neexistuje.

• Využití stavových prostorů k řešení problémů má své meze. Například může být stavový prostor nezvládnutelně velký (když je stavů příliš mnoho).

Další úlohy

Úloha: Další úlohy

Poháry 2
Na stole stojí pět pohárů, jeden je překlopený. V jednom kroku se smí otočit vždy přesně 2 poháry: stojící se překlopí, překlopené se postaví.
Kolik nejméně kroků je potřeba, aby všechny poháry stály?

Přesýpací hodiny
Máte 2 přesýpací hodiny – jedny sedmiminutové, jedny čtyřminutové.
Jak s jejich pomocí změřit přesně 9 minut?

Přesýpací hodiny 2
Máte 2 přesýpací hodiny – jedny sedmiminutové, jedny jedenáctiminutové.
Jak s jejich pomocí změřit přesně 15 minut?

Šňůry
Máme zapalovač a dva provazy. Každý z nich hoří půl hodiny, jenže nerovnoměrně (některé úseky hoří pomaleji, některé rychleji).
Jak odměřit tři čtvrtě hodiny?

Delší šňůry
Máme zapalovač a dva provazy. Každý z nich hoří jednu hodinu, jenže nerovnoměrně (některé úseky hoří pomaleji, některé rychleji).
Jak odměřit čtvrt hodiny?

Odměřování tekutin 49-6
Potřebujeme naměřit přesně 6 litrů vody, jenže máme jen dvě nádoby, o objemu 4 a 9 litrů. Jak postupovat?

Odměřování tekutin 45-2
Potřebujeme naměřit přesně 2 litry vody, jenže máme jen dvě nádoby, o objemu 4 a 5 litrů. Jak postupovat?

Odměřování tekutin 34-2
Potřebujeme naměřit přesně 2 litry vody, jenže máme jen dvě nádoby, o objemu 3 a 4 litry. Jak postupovat?

Odměřování tekutin 743-223
7, 4 a 3-litrová nádoba, 7 litrů vody v největší nádobě. Rozděl vodu na 2, 2 a 3 litry.

Odměřování tekutin 2073-15
20, 7 a 3-litrová nádoba, 20 litrů vody v největší nádobě. Odměř 15 litrů, nic nesmíš vylít.

Rodinka na výletě
Rodiče a dvě děti se potřebují dostat přes řeku. Všimnou si rybáře, který souhlasí, že jim půjčí svou lodičku. Lodička je ovšem malá, pojme buď jednoho dospělého, nebo dvě děti.
Jak se rodina dostane na druhý břeh a vrátí lodičku?

Rodinka v tunelu
Tatínek, maminka, syn a dcera potřebují projít tunelem. Tatínek projde tunelem za jednu minutu, maminka za dvě, syn za čtyři a dcera za pět. Jenže v tunelu je tma a oni nemají moc svíček nazbyt. Bez svíčky se ovšem do tunelu nedá, a i se svíčkou mohou projít nanejvýš dva lidé.
Jak zorganizovat průchod tunelem tak, aby spotřebovali co nejméně svíčky?

Váhy a závaží