Rozhodovací stromy a chytré otázky

Co se naučíš:

• Rozhodovat se podle daného stromu
• Nakreslit co nejlepší strom pro daný problém (a dané možností)
• Spočítat nejnižší a nejvyšší počet otázek podle daného stromu

• Porovnat očekávaný informační přínos daných otázek
• Vědět, čím se vyznačuje dobrá otázka, zformulovat ji pro danou situaci
• Určit myšlené číslo z daného rozsahu metodou půlení intervalů

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)

Už víme, že na informaci se můžeme dívat jako na úbytek možností. Zbývá nám tedy „jen“ najít příslušné otázky. Jenže jak určit, kolik ubude možností, když nevíme, jaká přesně přijde odpověď? Navíc bychom rádi našli obecné pravidlo, jaké otázky klást. Uměli bychom se pak ptát v různých situacích a také bychom díky obecnému pravidlu uměli klást otázky za sebou chytře tak, aby nás co nejkratší cestou vedly k cíli.

Úloha: Podrobnější zkoumání

Další kritéria

Množství získané informace samozřejmě není jediným možným kritériem kvality otázky. Otázka má být srozumitelná a jednoznačná, nemá být zbytečně komplikovaná. Je praktické, když umožňuje snadné kladení dalších dobrých otázek, např. když ji lze jen po mírné úpravě použít i v nových podmínkách.

Podívejte se do svých záznamů a připomeňte si otázky, které jste kladli v průběhu zjišťování myšleného čísla. Vzpomeňte si také, které možnosti ještě u jednotlivých otázek připadaly v úvahu.

Spočtěte pro jednotlivé otázky:

• Kolik ubude možností v případě odpovědi ANO, kolik v případě NE?
• Která z odpovědí je pro nás příznivější?
• Kdybychom hráli opakovaněPokud bychom se ve stejné situaci (tj. co už víme, a co je ještě nejisté) vyskytli např. tisíckrát, jak často bychom slyšeli ANO, a jak často NE?
• Kolik možností nám odpověď na otázku ubere v průměru?

Na základě vašich zjištění zkuste zformulovat, čím se vyznačuje dobrá otázka. Co to znamená, že je otázka dobrá? Proč?

Příklad: „Je to 11?“ a „Obsahuje to číslici 1?“

(Hledáme celé číslo z rozsahu 0-15, otázky jsme podrobněji zkoumali už v předchozí části.)

Otázka	Odpověď	Kolik možností odpověď vyloučí	Jak často(při opakovaném hraní) lze odpověď očekávat	Kolik otázka průměrně (při opakovaném hraní) vyloučí možností
„Je to 11?“	ANO	15	1/16Přibližně v jedné z šestnácti her	(1⋅15 + 15⋅1)/16 V jednom případě vyloučí 15 možností, v patnácti případech vyloučí jedinou možnost, a pro průměr je třeba vydělit počtem všech případů, tedy šestnácti. = 1,875
	NE	1	15/16
„Obsahuje to číslici 1?“	ANO	9	7/16	(9⋅7 + 7⋅9)/16 = 7,875
	NE	7	9/16

Příklady otázek

Pokud nemáte dost vlastních otázek:

• Je myšlené číslo dvouciferné?
• Je myšlené číslo sudé?
• Je myšlené číslo prvočíslem?
• Je na místě jednotek číslice 3?
• Začíná číslo na písmeno D?
• těžší otázka: Je ve dvojkovém zápisu čísla číslice 1 na místě čtyřek (tedy na 3. místě zprava)?

Rozhodovací stromy

Stromy nejsou nutné

Není to obvyklé, ale některé třídy si vystačí počítáním průměrů a zbytek si už odvodí. Rozhodovací stromy tedy nepotřebují pro řešení úlohy a z tohoto hlediska je zbytečné s nimi zdržovat. V průběhu přemýšlení nejspíš stejně padne otázka, která k zavedení stromů přirozeně povede.

Někteří už možná vhodný způsob pokládání chytrých otázek tušíteDovedete svoje tušení zdůvodnit?, někteří možná ne. Potíž je, že potřebujete uvažovat o mnoha různých posloupnostech otázek a odpovědí zároveň. Abychom si uvažování o různých cestách, jimiž se může zjišťování čísla ubírat, usnadnili, využijeme rozhodovací stromyPodobná schémata nazýváme stromy proto, že se postupně větví, a větve se nikdy znovu nespojují..

Znázorňují totiž celé dotazování vizuálně, všechny možnosti jsou vidět zároveň. Můžete se setkat s různými variantami, ale základ je vždy stejný:

NahořeSkutečně, informatici kreslí stromy zásadně převrácené. Kořen nahoru, listy dolů. Je to proto, že v kořeni obvykle začíná nějaká práce se stromem, a postup shora dolů je praktičtější. je výchozí uzel, tzv. kořen stromu. Obsahuje první otázku. Podle získané odpovědi pokračujeme po odpovídající hraně do příslušného podstromu a tak dál, až dojdeme ke konečné odpovědi. Ta je zapsaná v tzv. listu, tedy uzlu, ze kterého nevedou další hrany (protože neklade další otázky). Počet úrovní stromu od kořene k nejzazšímu listu nazýváme výškou stromu.

Příklad: Ukázkový rozhodovací strom pro určení jazyka z psaného textu

Kolik je nanejvýš potřeba otázek pro určení jazyka podle tohoto stromu? Kolik přinejmenším? S jakými texty nebude fungovat správně? Jak by bylo možné jej vylepšit?

Příklad: Rozhodovací strom z praxe

Strom pro určení vhodné autorské licence k dílu, které se chystáte publikovat.

I tohle je rozhodovací strom. Porovnáním s předchozím příkladem můžete odhadnout, na čem v rozhodovacím stromu záleží, a na čem nikoliv.

Mezipředmětové vazby

Rozhodovací strom je skoro totéž co klasifikační strom. Zařazení klasifikačních stromů v dalších předmětech prospěje nejen nám v informatice. Úloha na sestavení klasifikačního stromu pro rovinné útvary, světové jazyky, organismy v biologii atd. přinutí studenty dobře promyslet strukturu daných jevů, a tím prohloubí jejich porozumění.

Podle rozhodovacího stromu může rozhodovat takřka kdokoliv — ve srovnání se slovním popisem postupu hrozí menší riziko popletení. Navíc díky stromu hned vidíme:

• jestli nám někde něco nechybí (Vedou od každé otázky větve se všemi možnými odpověďmi? Najdeme v listech všechny možné výsledky?);
• jak dlouho trvá hádání kterého čísla (stačí spočítat otázky na cestě od kořene do příslušného listu);
• při použití stromu jednoduše vidímeZamysli se: jak je to ve stromu vidět?, které možnosti ještě připadají v úvahu, a které už ne.

Stromy a paralelní vesmíry

Paralelní vesmíry jsou užitečným myšlenkovým nástrojem. Představ si, že se s každým rozhodnutím vesmír rozštěpí, začnou existovat jeho různé varianty. V každé variantě je zrealizováno jedno z možných výsledků rozhodnutí. Každý z těch vesmírů se samozřejmě opět štěpí, s každým dalším rozhodnutím, které v něm probíhá. Takže zatímco ty máš třeba objednaný oběd č. 1, v paralelním vesmíru máš objednanou dvojku. V dalším vesmíru vůbec neexistuješ, protože se rodiče (nebo jejich rodiče...) přeci mohli rozhodnout i jinak. Rozhodnutí probíhá obrovské množství, obrovské množství je tak i (smyšlených) paralelních vesmírů (a navíc se pořád dál větví). Paralelní vesmíry nutí uvažovat o tom, která rozhodnutí jsou skutečně svobodná, co je vskutku nemožnéNeuskutečnilo se to v žádném z vesmírů, a co je naopak nutnéJe to ve všech vesmírech.

Jistou útěchu v životě ti může přinést např. myšlenka, že v některém paralelním vesmíru si v rámci tělocviku právě užívášAle jsi to ještě ty? skok padákem. Motivační může být uvědomění, že jsi to právě ty, kdo si při každém rozhodnutí vybírá, ve kterém z potenciálních vesmírů chceš žít.

Ale proč to sem píšeme: Paralelní vesmíry a jejich větvení si lze představit (tedy až na to množství) právě jako rozhodovací strom.

Úloha: Strom pro zjišťování čísla

Sestroj rozhodovací strom zachycující tvůj postup zjišťování čísla 0-15.

Stromy můžeš kreslit ručně, nebo použij nějaký program, např.:

• draw.io nebo LucidChart - on-line prostředí pro tvorbu všemožných schémat a diagramů

• yEd - online i off-line program pro tvorbu grafů
• Inkscape - univerzální vektorový grafický editor. Je tedy určen především ke kreslení, méně už na diagramy, ale taky jde použít.

Bitmapové editory jako např. Malování jsou naopak pro vytváření stromů zcela nevhodné a nejspíš by ti jen přidělaly práci.

Konkrétní detaily (tvary různých typů uzlů, styly čar atd.) se mohou lišit. Podstatné je, aby byl strom srozumitelný a jednoznačný. Rozhodovací uzly bývají ve tvaru kosočtverce, větve mívají šipky (a musí být samozřejmě nadepsané). Dobrým zvykem je systematické uspořádání, např. tak, aby byla výsledná rozhodnutí nějak seřazená, nebo tak, aby stejná odpověď šla vždy na stejnou stranu.

Nápověda

Uvědom si, že první otázka by měla být vždy stejná. Na začátku každé hry jsi ve stejné situaci, nevíš o čísle nic. Není tedy důvod upřednostnit pokaždé jinou otázku. Při sestrojování stromu tedy začni první otázkou své dotazovací strategie, zapiš ji jako kořen stromu.

Od kořene (tedy první otázky) pak povedeš větve s možnými odpověďmi, každá bude končit uzlem s další otázkou a postupně se tak propracuješ ke všem možným výsledkům, uvedeným v listech stromu.

Úloha: Srovnání stromů, tedy herních strategií

Porovnej svůj strom se stromy spolužáků. Které stromy ukazují lepší strategii? Shodnete se na odpovědi? Jak je na stromu vidět, která dotazovací strategie je lepší?

Srovnáním různých stromů vedoucích ke stejnému rozhodnutí tedy vidíme, který strom je pro která myšlená čísla efektivnější. Různé strategie se liší v nejnižším i nejvyšším počtu potřebných otázek. Už jsme ale odhalili, že dobří hráči jsou efektivní nezávisle na tom, které číslo zrovna zjišťují. Formulují otázky tak, aby se co nejvíce přiblížili výsledku, i když mají zrovna smůlu. Snaží se totiž dosáhnout co nejnižšího průměrného počtu otázek. Ten je rozhodující, když hrajeme několik her za sebou, a také když chceme maximalizovat naše šance na výhru.

Zamysli se a odpověz:

Rozhodni o pravdivosti následujících tvrzení a své rozhodnutí zdůvodni:

Pro libovolný rozhodovací strom platí, že...

...průměrný počet potřebných otázek je vždy vyšší, než nejnižší počet potřebných otázek.

...průměrný počet potřebných otázek není nikdy vyšší, než nejvyšší počet potřebných otázek.

...nejnižší počet potřebných otázek je vždy nižší, než nejvyšší počet potřebných otázek.

...pokud se průměrný počet potřebných otázek shoduje s nejnižším, pak se shoduje i s nejvyšším počtem potřebných otázek.

Nápověda

Nenech se zmást tím, že jsme v kapitole o rozhodovacích stromech. Jedná se o známé vlastnosti průměru. Pozor na speciální případ: co se stane, když počítám průměr několika stejných hodnot?

Řešení

Ne, ano, ne, ano.

Úloha: Vylepšení

Jestli chceš, svůj strom vylepši. Jak se pozná, že už to nejde (tedy ne, že to nejde tobě, ale že to není možné)?

Nápověda

Snaž se přeskupit listy a uzly tak, aby byly listy co nejblíže kořeni.

Optimální rozhodovací strom

Nejlepším řešením je pěkně rovnoměrně vystavěný strom. Všimni si, že každá otázka odstraní vždy právě polovinu zbývajících možností. Úbytek možností tak nezávisí na tom, jestli dostaneme odpověď ANO nebo NE. Úspěch ve hře tak nijak nezáleží na tom, jestli máme štěstí, nebo ne.

Optimální tvar rozhodovacího stromu.

Počty otázek potřebných k dosažení libovolného listu se téměř neliší. Na obrázku si také můžeme zkontrolovat, že listy není možné ve stromě vměstnat nikam výš a tím hledání zkrátit. Všechna větvení jsou plně využita. Kdybych chtěl k některému číslu dojít dřív, musel bych několik jiných čísel přesunout dál od kořene stromu, a k jejich zjištění by tak bylo potřeba více otázek. Vylepšit situaci jednoho čísla na úkor několika jiných čísel se ale v souhrnu nevyplatí.

Zelený list můžeme přesunout libovolně blízko ke kořeni a uspíšit tak jeho uhodnutí, jenže tím neúměrně prodloužíme cestu k červenému podstromu a celkovou situaci tak v průměru zhoršíme.

Chcete vědět víc?

Odpovědi ANO a NE ne jsou z informačního hlediska rovnocenné, samy o sobě žádný význam nemají. Lidé ale nejsou jednoduché stroje a při vzájemné komunikaci nepřijímají informace zdaleka jen z obsahu sdělovaných slov. Jistě postřehnete zásadní rozdíl ve vyznění těchto informačně téměř rovnocenných otázek:

• „Je vynesený koš?“
• „Vynesl jsi koš?“
• „Že jsi pořád nevynesl koš?“

Stroje jsou v tomto ohledu pro leckoho příjemnější, než lidé: Nepoužívají ke komunikaci žádné neurčité náznaky.

V případě zjišťování jednoho z šestnácti čísel tedy snadno zjistíme, že potřebujeme pokaždé čtyři otázky. Nejlepší, průměrný a nejhorší počet se neliší.

Může se ovšem stát, že je hledaných možností např. jen dvanáct, a nelze sestavit strom, v němž by každé hledání bylo stejně dlouhé.

Úloha: Rozhodovací strom pro 12 možností

Sestav co nejlepší rozhodovací strom pro 12 možností.

• Co v tomto případě znamená „co nejlepší“ strom?
• Jaké v něm bude nejdelší a nejkratší dotazování? O kolik se budou lišit?
• Jak takový strom systematicky a spolehlivě sestavit?

Nemusíš pracovat v hlavě, strom si nakresli, nebo sestroj na počítači!

Co je příčina, co je důsledek?

Zajímavé je, že lze optimální rozhodovací strom popsat i naopak. Platí tedy oba směry:

1. Pokud se nejkratší a nejdelší dotazování ve stromu liší nanejvýš o jedinou otázku, je strom optimálníPrůměrná délka dotazování v něm je nejkratší možná.
2. Je-li strom optimálníPrůměrná délka dotazování v něm je nejkratší možná, liší se nejkratší a nejdelší dotazování v něm nanejvýš o jedinou otázku.

Kritéria kvality stromu jsou stejná jako doposud: chceme co nejkratší dotazování nezávisle na štěstí, tedy v průměrném případě. I v takovém případě se tedy držíme zásady vměstnat co nejvíce možností co nejblíže ke kořeni, a co nejvíce větvení tak plně využít. Výsledkem pro libovolný počet možností (takže i 12) je, že se rozdíl nejkratšího a nejdelšího dotazování liší nanejvýš o jedinou otázku (a průměrná délka dotazování proto bude „někde mezi“).

Tři optimální a jeden neoptimální rozhodovací strom pro 12 možností - který to je?

Optimální dotazovací strategie

Chcete vědět víc?

Myšlenku půlení intervalů lze samozřejmě zorganizovat i jinak. Můžeme se např. ptát, jestli je hledané číslo menší než medián atp. Výhody půlení intervalů zůstanou zachovány.

Už víme, jak optimální dotazovací strategie vypadá, tedy jaký je tvar příslušného stromu. Jaké ale konkrétně pokládat otázky, aby rozdělovaly zbývající možnosti na poloviny a vyšel tak pěkně rovnoměrný strom? Oblíbenou strategií informatiků je tzv. půlení intervalůMůžete se setkat i s názvem binární vyhledávání, to je obdobný princip.. Předpokladem je, že pracujeme s kompletním rozsahem čísel (bez „děr“).

Pamatuj si: Postup půlení intervalů

Zeptáme se, jestli je hledané číslo větší nebo rovno číslu uprostředPři sudém počtu možností žádná „prostřední“ neexistuje. Zvolíme tedy třeba jednu ze dvou prostředních. zbývajícího rozsahu. Odpověď vyloučí přesně polovinu čísel (ledaže jich byl lichý počet). Navíc budou zbývající čísla opět tvořit nepřerušenou posloupnost, takže na ně můžeme požít stejný postup, dokud se nedostaneme ke hledanému číslu.

Příklad rozhodovacího stromu pro nalezení celého čísla v rozsahu 0—15, který využívá princip půlení intervalů.

Úloha: Zkus si to!

Postup půlení intervalů vyzkoušej, nejlépe ve dvojici. Můžeš vyzkoušet různé rozsahy čísel. Byl potřeba správný počet otázek?

Polovina z poloviny z poloviny

Všimněte si zajímavého „triku“ v popisu postupu půlení intervalů: „Zjisti, ve které polovině prohledávaného intervalu je hledané číslo, a pak pokračuj prováděním tohoto postupu od začátku, a pracuj při tom už jenom se správnou půlkou původního intervalu“. Totéž je vidět i na rozhodovacím stromu: jakmile se rozhodneme pro jednu ze dvou odpovědí a část stromu, kterou už jistě nebudeme potřebovat, si odmyslíme, zbyde nám sice menší, ale opět strom (navíc odpovídající stejným pravidlům). Takové použití „sebe sama“ nazýváme rekurze. Je to neskutečně užitečný a mezi informatiky proto oblíbený nástroj. S rekurzí se ještě mnohokrát setkáme.

Postup půlení intervalu nijak nezávisí na tom, kolik máme možností. Lze použít stejně dobře na čísla 0—15, jako na čísla 1—100, ale také -23465—1,23654756⋅10¹². To je jistě ulehčující zjištění — jen si představ, že by bylo nutno sestrojit příslušný rozhodovací strom!

Ve variantě se zvířaty zůstává princip stejný. Každou otázkou se snažíme rozdělit zbývající zvířata (alespoň přibližně) na poloviny a ptáme se, ve které polovině se zvíře nachází. Postup opakujeme, dokud nezbyde jediné zvíře. Samozřejmě k účinnému dělení zvířat na potřebné skupiny je třeba se ve zvířatech poměrně dobře vyznat — přinejmenším vědět, kolik je asi tak zvířat s různými vlastnostmi a jejich kombinacemi. Pak si můžeme v každé situaci vybrat tu vlastnost, která rozdělí zbylé možnosti co možná nejrovnoměrněji.

I kdybychom o zvířatech věděli jen málo, jako informatici si poradíme. Když budeme opravdu chtít, vzájemně se domluvíme a všechna myslitelná zvířata očíslujeme. A tím jsme vlastně hotovi — zjišťovat efektivně čísla už přeci umíme. Přitom očíslovat v principu dovedeme cokoliv, co lze použít v naší hře. Původní zadání (zjišťování myšleného zvířete) jsme převedli na zadání, které dovedeme pohodlně řešit (zjišťování myšleného čísla). To je další z oblíbených informatických „triků“.

Shrnutí

Rozhodovací stromy umožňují přehledně znázornit celý rozhodovací proces. Zároveň umožňují zkoumat a porovnávat, jak jsou různá rozhodování efektivní. Rozhodování začíná v kořeni, z jednotlivých uzlů se pokračuje do příslušných větví podle získaných odpovědí (informací), dokud se nedojde ke konečnému rozhodnutí, zapsanému v listu stromu. Co do počtu položených otázek rozlišujeme nejkratší, průměrné a nejdelší rozhodování (to odpovídá tzv. výšce stromu).

Optimální rozhodovací strom pro stejně pravděpodobné možnosti je vyrovnaný, každé rozhodování vyžaduje téměř stejný početPočet se liší nanejvýš o jedna, a to v případě, kdy zcela vyrovnaný strom pro daný počet možností sestavit nelze. otázek. Zbývající možnosti tak dělí vždy na stejně početné skupiny, v případě otázek se dvěma možnými odpověďmi (např. ANO a NE) tedy na poloviny.

Optimální herní strategie pro hádání myšleného číslaNebo čehokoliv jiného, co dovedeme seřadit, nebo si jinak pomoci k možnosti dělení možností na poloviny. spočívá v půlení intervalů. Opakovaně dělíme zbývající možnosti na poloviny a zjišťujeme, ve které z nich se nachází to, co hledáme - s touto polovinou pak postup opakujeme, dokud nezbyde jediná možnost.

Půlení intervalů lze využít i pro řešení mnoha dalších vyhledávacích problémů. V informatice jde o jeden z nejpoužívanějších postupů.