Stavový Diagram, Stavový Prostor

Stavový Diagram a Stavový Prostor

8. Stavový Diagram, Stavový Prostor a Jeho Prohledávání

8.1 Stavový Diagram (UML State Machine)

Definice: Standardizovaný grafický zápis vývoje informačního systému (IS) s konečným počtem stavů (např. konečný automat).
Popisuje: Chování systémů, které vyjadřují stavy objektu a přechody mezi nimi (přechodová funkce).
Modeluje: Dynamické chování reaktivního objektu.
UML State Machine:
- Poskytuje sadu elementů pro popis systému (průchod stavy řízený vnějším vstupem).
- Umožňuje přehledný náhled na entity (stav entity).
- Umožňuje sledovat funkčnost IS v reálném čase (změna stavu událostí).
Podstata: Entita se nachází ve stavu, kterého dosáhne za určitých okolností (např. dokument vytisknut, pokud tisk proběhl v pořádku).

8.1.1 Základní Prvky Stavového Diagramu

Stavy
Přechody
Události

8.1.1.1 Stavy

Určeny: Hodnotami atributů, relacemi s objekty a aktivitou.
Mohou být: Složené (vnořené stavové automaty se sekvenčním/paralelním během, synchronizace, komunikace, historie).
Stav může obsahovat:
- Vstupní akce (automaticky při vstupu do stavu).
- Výstupní akce (automaticky při opuštění stavu).
- Interní přechody.
- Pozdržené události.
- Interní aktivity.

8.1.1.2 Přechody

Viz 8.1.4.4 Transition (přechod), str. 185
Syntaxe: Trigger[Guard]/Effect
Sémantika: Při výskytu události, je-li podmínka splněna, proveď akci a přejdi do stavu.

8.1.1.3 Události

Rozlišujeme události volání, signální události, události změny a časové události.

8.1.2 Modelování Stavového Diagramu

Objekty mění stav jako důsledek události.
UML state machine rozlišuje pouze stavy, jejichž diferenciace má pro modelování chování objektu smysl (sémantický rozdíl)
UML state machine modeluje chování systému

8.1.3 Souvislost Stavového Diagramu a Diagramu Aktivit

Společné rysy: Podobná grafická notace (syntaxe).
Odlišnosti:
- Diagramy aktivit se užívají pro modelování obchodních procesů (účast objektů), šipky propojují aktivity.
- Stavové diagramy se užívají k modelování životního cyklu reaktivního objektu, šipky propojují statické stavy.

8.1.4 Grafická Notace UML State Machine Diagramu

State (stav)
Initial (počáteční bod)
Final (konečný bod)
Transition (přechod)
Submachine state
Choice (volba)
Junction (uzel)

8.1.4.1 State (stav)

Základní prvek stavového diagramu.
Reprezentuje daný stav entity.
Stav může obsahovat další stavy (složený stav).
Akce u stavu:
- entry akce (při vstupu do stavu).
- do akce (v průběhu stavu).
- exit akce (při opuštění stavu).
- Zapisují se do dolní části stavu (např. entry/ načíst nastavení).

8.1.4.2 Initial (počáteční bod)

Začíná zde přechod do stavu, obvykle do prvního počátečního stavu.

8.1.4.3 Final (konečný bod)

Změny stavů mohou skončit.
Po přechodu do bodu final nenastávají další změny.
Diagram může mít libovolný počet bodů final.

8.1.4.4 Transition (přechod)

Vazba mezi dvěma stavy.
Šipka směřuje k novému stavu.
Stav může obsahovat přechod sám na sebe.
Vlastnosti (zapisují se nad šipku ve formátu Trigger[Guard]/Effect):
- Trigger (příčina): Proč přechod nastal (např. "registrace byla potvrzena").
- Guard (podmínka): Podmínka pro přechod (např. [odkaz s id 256654221 byl otevřen]).
- Effect (akce): Akce, která nastane s přechodem (např. Prava = 2).
Příklad: startování při automobilových soutěžích změnaSemaforu(barva)[barva="zelená", závodník je na řadě]/rozjede.
Přechod je relace ve stavovém stroji. Objekt přejde do nového stavu, pokud nastane událost a jsou splněny podmínky (guards) a provede se efekt (effect).
Přechod je nepřerušitelný, říká se, že přechod je odpálen (transition is fire).
Může mít jeden nebo více zdrojových stavů a jeden nebo více cílových stavů.

8.1.4.5 Submachine State

Stav, který se skládá ze složité struktury podstavů, ale tváří se jako jeden stav.
Stavy vložené do Submachine State nejsou viditelné.
Grafická notace je stejná jako u stavu, ale má v pravém dolním rohu ikonu brýlí.
Kliknutím na ikonu brýlí se otevře další stavový diagram, který reprezentuje Submachine State.
Používá se pro složité diagramy.

8.1.4.6 Choice (volba)

Pomocí Choice se určuje, jakého stavu entita nabude.
Princip je založen na uvedení guardů (podmínek) pro větve.
Grafická notace je kosočtverec, do kterého přichází přechod a další z něj vychází.

8.1.4.7 Junction (uzel)

Umožňuje sjednotit přechody.
Grafická notace je vyplněný kruh.
Z uzlu může vycházet několik přechodů s guardem (větvení).
Na rozdíl od Choice do něj může vcházet více přechodů.

8.2 Stavový Diagram – Matice Přechodu

Každý model se nachází v určitém stavu (stavy se mění).
Přechody mezi stavy lze zaznamenat do matice (viz kap. 7.2.1 Matice sousednosti, str. 139).

8.3 Stavový Prostor

Konfigurace diskrétních stavů sloužících jako výpočetní model.
Formálně: Úloha ve stavovém prostoru je definována jako čtveřice $[N, A, S, G]$ , kde:
- $N$ je množina stavů.
- $A$ je množina přechodů mezi stavy.
- $S$ je neprázdná podmnožina $N$ obsahující počáteční stavy.
- $G$ je neprázdná podmnožina $N$ obsahující cílové stavy.
Na procházení stavového prostoru je založena metoda řešení úloh: Prohledávání stavového prostoru.

Hanojské Věže

Viz kap. 2.3.3.5 Hanojské věže, str. 58 v kap. Rekurze (Algoritmy).
Příkladem stavového prostoru jsou možná rozložení disků u hlavolamu „Hanojské věže“.
Tento hlavolam je tvořen třemi tyčkami, na kterých je navlečeno několik různě velikých disků.
Velikost stavového prostoru záleží na počtu disků. Pro $n \in \mathbb{N}$ disků je to $3^n$ (každý z $n$ disků může být na jedné ze tří tyček), pro tři disky je stavový prostor znázorněn na Obrázek 8-11: Stavový prostor Hanojských věží.
Stavový prostor $Sp = (S, \Phi)$ je dvojice tvořená:
- Množinou stavů: $S = {s}$
- Množinou operátorů (přechodů mezi stavy): $\Phi = {\phi}, sk = \phi{ik}(s_i), \forall i, k \in \mathbb{Z}$
V případě 3 disků $n=3 \implies 3^3 = 27$
Operátory se odvodí na základě pravidla, že se postupně přesouvají disky mezi tyčkami:
- Může se přesouvat vždy jeden disk.
- Větší disk se nelze položit na menší.
Celkem je k dispozici 6 operátorů: $\phi{12}, \phi{13}, \phi{21}, \phi{23}, \phi{31}, \phi{32}$ , kde $\phi_{ki}$ znamená přesuň volných disk z $k$ na $i$ .

Hlavolam Lišák (Loydova Patnáctka)

Hlavolam „lišák“ je jednodušším ekvivalentem Loydovy patnáctky.
Loydova patnáctka je sestrojena na poli 4x4, Lišák je omezen do pole 3x3.
Stavový prostor obsahuje $9! = 362880$ stavů.
V tomto stavovém prostoru jsou definovány 4 operátory:
- $\varphi_1$ : právě tehdy když $\ell$ není v horním řádku; přesun $\ell$ nahoru
- $\varphi_2$ : právě tehdy když $\ell$ není v dolním řádku; přesun $\ell$ dolů
- $\varphi_3$ : právě tehdy když $\ell$ není v levém sloupci; přesun $\ell$ vlevo
- $\varphi_4$ : právě tehdy když $\ell$ není v pravém sloupci; přesun $\ell$ vpravo
Úloha ve stavovém prostoru $(S, \Phi, s0, G)$ je definována jako stavový prostor, tj. * množina stavů $S = {s}$ * množina přechodů mezi stavy $\Phi = {\phi}$ * úloha ve stavovém prostoru pak dále musí obsahovat: * počáteční stav $s0$
* množina koncových stavů $G = {g}$ .
Volba operátoru pro daný stav může být založena na myšlence postupně zkusit aplikovat všechny použitelné operátory, může být založena na nějakém kritériu, které hodnotí vhodnost jednotlivých operátorů, nebo může být volba operátoru náhodná.
Strom řešení úlohy je grafová reprezentace procesu hledání řešení kde uzly odpovídají stavům a hrany odpovídají přechodům mezi stavy daných aplikací operátorů.

8.4 Prohledávání Stavového Prostoru

Uzly $V$ reprezentují stav
Hrany $E$ reprezentují přechody mezi stavy
Jedná se o skupinu metod řešení úloh, které spadají do oblasti AI.
Princip je založen na vhodném procházení stavů určité domény (entity) s účelem nalezení požadovaného stavu, tedy nalezení přijatelné cesty v orientovaném grafu z počátečního uzlu (kořene stromu) k některému listu.
Stavový prostor lze reprezentovat orientovaným grafem $G = (V, E)$ . Graf $G$ je stromem.
Stavy jsou v drtivé většině případů generovány v průběhu algoritmu (nejsou předpočítány).
Nechť tedy máme úlohu ve stavovém prostoru $(S, \Phi, s0, G)$ , kde $S$ je množina stavů, $\Phi$ je množina operátorů, $s0$ je počáteční stav a $G$ je množina koncových stavů.
Stav = dvojice $(cA, cB)$ , množství vody v nádobách A, B
Počáteční stav: $(0, 0)$
Množina koncových stavů: ${(0, 2a − b)}$

Operátory

Vylití nádoby $A$ : $(cA, cB) \rightarrow (0, c_B)$
Vylití nádoby $B$ : $(cA, cB) \rightarrow (c_A, 0)$
Naplnění nádoby $A, B$
Přelití $A$ do $B$ : $(cA, cB) \rightarrow (max(cA − (b − cB), 0); min(cA + cB, b))$

Metody prohledávání lze rozdělit do 3 základních skupin:

Slepé
- úplné prohledávání nevyužívající žádné dodatečné informace
- zde postupně aplikujeme všechny použitelné operátory
- příklad: BFS, DFS, uniform-cost, iterativní prohlubování, …
Heuristické
- úplné nebo částečné prohledávání využívající hodnocení zvolené cesty
- Zde operátory vybíráme na základě daného kritéria
- příklad: beam-search, hill-climbing, best-first search, algoritmus A*,
Náhodné
- volíme operátory náhodně

Způsob hodnocení metod

Různé metody jsou pro rozdílná procházení jinak efektivní. Pro správnou volbu požadované metody je nezbytné umět zhodnotit její účinnost. Existují 3 základní vlastnosti, podle kterých lze metody hodnotit:

Časová složitost
- Minimální/maximální/průměrný čas potřebný k vyřešení úlohy danou metodou
- Čas je přímo závislý na výpočetním výkonu
- V praxi se často reprezentuje např. jako počet prozkoumaných stavů v daném čase (objektivnější hodnota)
Prostorová složitost
- Minimální/maximální/průměrné množství operační paměti, potřebné k vyřešení úlohy danou metodou
- Nezávislost na platformě ⇒ náhrada údaje o počtu MB → počet stavů současně uchovaných v paměti
Kvalita získaných výsledků
- Hodnota, která udává výpověď o tom, zda je daná metoda:
  - úplná (tj. vždy, když existuje řešení, tak jej nalezne),
  - optimální (tj. nalezené řešení je nejlepší ze všech).

8.4.1 Slepé metody prohledávání stavového prostoru = Neinformované metody

Nemají k dispozici žádné vhodné znalosti o stavovém prostoru, které by mohly urychlit cestu k cíli (nejsou informované)
Systematické procházení všech uzlů
Jednotlivé algoritmy se od sebe liší jen způsobem, jakým systematické procházení provádějí

8.4.1.1 Prohledávání do šířky (BFS) = breadth-first search

Následníci vybíráni pro expanzi ze seznamu typu fronta, viz kap. 6.2 Fronta (Queue), str. 119
Postupně se prochází strom řešení po vrstvách (prohledáme veškeré uzly, které mají nižší hloubku, než je hloubka koncového stavu)
Každý uzel je navštíven nejvýše jednou.
Vždy je nalezeno optimální řešení (koncový stav s nemenší hloubkou)

8.4.1.2 Prohledávání do hloubky (DFS) = depth-first search

Následníci jsou vybíráni vybírání pro expanzi ze seznamu typu zásobník, viz 6.4 Zásobník, str. 123
Na rozdíl do BFS, zde můžeme některými uzly procházet vícekrát (často se musíme vracet (tzv. backtracking))
Nemusíme nalézt optimální řešení (koncový stav s nejmenší hloubkou) či dokonce žádné řešení (pokud má stavový prostor nekonečnou větev)
V úlohách s konečným stavovým prostorem a s jedním koncovým stavem nalezneme stejné řešení jako u BFS.

8.4.1.3 Prohledávání se stejnou cenou (uniform cost)

V každém kroku expanduje uzel, která má nejnižší cenu cesty od počátku
Jde o zobecnění slepého BFS
BFS je de facto prohledávání s jednotnou cenou (cena = hloubka uzlu)

8.4.1.4 Prohledávání do hloubky s omezením (depth-limited search)

Omezené DFS se od klasického liší v tom, že je dána maximální hloubka, do které se prohledává. Uzly této hloubky se již dále nerozvíjejí.
Užití: Eliminace problematiky DFS prohledávání u stromů s nekonečnou větví

8.4.1.5 Iterativní prohlubování (iterative deepening search)

De facto depth-limited search s rozdílem, že maximální hloubka není pevně stanovená (⇒ postupně se zvětšuje maximální hloubka)
Nejprve se prohledává (do hloubky) stavový prostor hloubky 1, pak do hloubky 2, pak do hloubky 3, atd.
Iterative deeping search dokáže odstranit jednak problém nekonečných větví, jednak též problém klasického DFS (nalezne optimální řešení, pokud existuje)

8.4.2 Heuristické metody prohledávání stavového prostoru = Informované metody

Mají znalosti o stavovém prostoru (umožňují jim odhadnout délku cesty koncového stavu od aktuálního)
Odhad reprezentuje tzv. heuristická funkce $h(n)$ : Čím nižší hodnoty $h(n)$ nabývá, tím je vyšší pravděpodobnost, že cesta k řešení povede skrze stav $n$
Heuristickou funkci dodává člověk (na základě znalostí), informované metody jsou na heuristické funkci kriticky závislé
Čím je heuristika (kritérium) lepší, tím rychleji a s menším zatížením paměti dojde k nalezení řešení.
Heuristická funkce je funkce, která každému stavu $s$ přiřadí číslo, které vyjadřuje jeho kvalitu z hlediska řešení úlohy.
Vhodnost operátorů (tedy kvalita následníka) může být v dané úloze definována různě.
Různé podoby heuristiky mají vliv na volbu operátorů, a tedy také na celkové hodnocení metod (časová složitost, prostorová složitost, kvalita získaných výsledků).

Manhattan Metrika

Též newyorská metrika (obojí dle pravoúhlého systému ulic na Manhattanu v New Yorku) je metrika na množině $\mathbb{R}^n$ definovaná vztahem:
$\rho(x, y) = |x1 − y1| + |x2 − y2| + \cdots + |xn − yn|$
Tato metrika odpovídá představě nejkratší vzdálenosti, kterou musí urazit automobil (v populární verzi vůz newyorské taxislužby) při cestě z jedné křižovatky na jinou – předpokládáme-li, že systém ulic je pravoúhlý.

Heuristiky pro hlavolam Lišák

$H1$ : počet chybně umístěných číslic
$H2$ : Manhattan vzdálenost od koncového stavu
Význam heuristiky $H1$ – zřejmý.
Heuristika $H2$ vyjadřuje kolik tahů je každá chybně umístěná číslice vzdálena od své správné pozice.
Algoritmus heuristického prohledávání se nazývá přípustný, jestliže pro libovolně ohodnocený graf ukončí svoji činnost nalezením optimální cesty k cíli.

8.4.2.1 Paprskové prohledávání (beam search)

Heuristické prohledávání do šířku (heuristika = odhad vzdálenosti ke koncovému stavu)

8.4.2.2 Gradientní prohledávání globální (hill climbing) = též horolezecký algoritmus

Heuristické prohledávání do hloubky (heuristika = odhad vzdálenosti ke koncovému stavu)
Následníky rozvinutého uzlu nejprve uspořádáme dle heuristiky a pak zařadíme do zásobníku.
Jestliže heuristická funkce každému uzlu přiřadí hodnotu, která je nezáporným dolním odhadem skutečné ceny, pak algoritmus je přípustný (a příslušná funkce se nazývá přípustná).
Algoritmus využívající přípustnou heuristickou funkce $H1$ je informovanější než algoritmus využívající přípustnou heuristickou funkci $H2$ , právě když:
\forall s \in S: H1(s) \geq H2(s) \wedge \exists si \in S: H1(si) > H2(s_i)
O heuristice $H1$ pak řekneme že je dominuje heuristice $H2$ .

8.4.2.3 Gradientní prohledávání lokální

Vychází z globálního gradientního prohledávání (= heuristické prohl. do hloubky)
Založena na faktu, že pro daný stav volíme dle heuristiky nejlepšího následníka a pracujeme pouze s ním (lokálně).
Seznam NEROZVIN je jednoprvkový.
Lokální gradientní prohledávání hledá pouze lepší uzel, než je ten současný, což může vyvolat řadu dilemat:
- Uvíznutí v lokálním extrému (na listu) – žádný následník (syn) není lepší než původní uzel (nevede k řešení problému), nebo následník vůbec neexistuje
- Tzv. plošinové dilema –rozvíjený uzel i jeho následníci jsou stejně kvalitní (není zřejmé kterým směrem pokračovat)

8.4.2.4 Uspořádané prohledávání (best-first search)

Úplné heuristické prohledávání do hloubky (doplnění gradientního prohledávání o paměť).
Prohledávání do hloubky (DFS) = vždy pokračuje v hledání v nejvzdálenějším dostupném stavu
Prohledávání do šířky (BFS) = vždy pokračuje naopak z jednoho k počátku nejbližších stavů
Přirozená implementace best-first search aplikuje k ukládání prioritní frontu
- BFS používá obyčejnou frontu
- DFS využívá zásobník (obvykle se jedná v rámci rekurze o zásobník volání)
V porovnání algoritmy DFS a BFS je best-first search algoritmem informovaným, neboť se při uspořádávání vrcholů opírá vstupní data.
Vstupní data mohou obsahovat:
- známou cenu vrcholů nebo hran
- heuristiku, kterou se odhaduje jejich slibnost.
Obdobnou myšlenku má nebo rozvíjí řada specializovanějších vyhledávacích algoritmů, například Dijkstrův algoritmus, A* nebo paprskové prohledávání. Naopak na samotný algoritmus uspořádaného prohledávání se lze dívat jako na rozšíření gradientního prohledávání o paměť.

8.4.2.5 Algoritmus A* = a-star

vyhledávání optimálních cest v kladně ohodnocených grafech.
Používá stejné principy jako Dijkstrův algoritmus, ale přidává navíc heuristický prvek.