Drzewko możliwości przedstawia kolejne wybory jako rozgałęzienia. Pełna ścieżka od początku do końca opisuje jeden kompletny wynik, a liczba końcowych ścieżek daje liczbę wyników.
Pojęcia, od których zaczynamy
Początek drzewka nazywamy korzeniem. Gałąź oznacza jeden dopuszczalny wybór, a punkt, z którego wychodzą dalsze gałęzie, etap jeszcze nieukończony. Liść jest końcem pełnego wyniku. Nie dodajemy liczby wszystkich punktów rysunku, bo punkty pośrednie nie są dodatkowymi wynikami.
W dwóch kolejnych rzutach monetą najpierw rysujemy dwie gałęzie: orzeł O i reszka R. Z końca każdej rysujemy ponownie O oraz R. Drugi rzut odbywa się w obu przypadkach. Pominięcie rozgałęzienia po reszce usunęłoby część możliwych wyników.
Zasady i wzory
Drzewko możliwości przedstawia kolejne etapy wyboru. Każda droga od korzenia do liścia odpowiada jednemu kompletnemu wynikowi.
- Na każdej gałęzi zaznacz jeden wybór.
- Nie pomijaj etapów ani możliwości.
- Licz liście albo sumuj iloczyny w rozłącznych gałęziach.
Ten wzór skraca liczenie, gdy na każdym etapie liczba opcji jest stała niezależnie od wcześniejszych wyborów. Przy różnych liczbach opcji rozdzielamy drzewko na rozłączne przypadki i dodajemy ich liczebności. W pełnym drzewku z pojedynczymi wynikami liczymy po prostu końcowe liście.
Jak czytać rysunek?
Cztery końcowe ścieżki mają etykiety OO, OR, RO i RR. Pierwsza litera opisuje pierwszy rzut, druga kolejny. OR i RO mają po jednym orle, lecz są innymi sekwencjami. Gdy pytanie dotyczy dokładnie jednego orła, zaznaczamy dwa liście: OR oraz RO.
Przykład krok po kroku
Menu ma 2 przystawki, 3 dania główne i 2 desery. Ile pełnych zestawów można wybrać?
Co jest jednym wynikiem? Jeden liść pełnego drzewka odpowiada jednemu zestawowi: konkretnej przystawce, konkretnemu daniu i deserowi. Wypisując każdą opcję osobno, po prostu liczymy liście. Mnożenie skraca liczenie regularnych rozgałęzień; nie mnożymy ponownie liczby opcji na każdej już wypisanej kompletnej ścieżce.
- Utwórz trzy poziomy drzewa.Przystawka → danie główne → deser.
- Policz rozgałęzienia.\(2,\ 3,\ 2\)
- Policz liście.\(2\cdot3\cdot2=12\)
Typowy błąd
Suma liczby opcji na poziomach nie daje liczby pełnych ścieżek.
Dodatkowy przykład i kontrola
Drzewko nie zawsze jest regularne. Jeśli po wyborze A dostępne są trzy kontynuacje, a po B dwie, otrzymujemy \(3+2=5\) liści. Przy regularnych etapach, np. dwa napoje i trzy desery do każdego, iloczyn \(2\cdot3=6\) skraca liczenie wszystkich liści.
Rozróżnij etykiety gałęzi od liczb możliwości i prawdopodobieństw. Numer na gałęzi może oznaczać po prostu wynik rzutu; nie mnożymy numerów oczek, aby policzyć ścieżki. W drzewku prawdopodobieństw można mnożyć warunkowe prawdopodobieństwa wzdłuż ścieżki. To inna operacja niż liczenie liści w pełnym drzewku możliwości.