To tylko jedna z 21 stron tej notatki. Zaloguj się aby zobaczyć ten dokument.
Zobacz
całą notatkę
•
•
•
•
Struktury i strategie przeszukiwania stanów
Przeszukiwanie heurystyczne
Metody stochastyczne
Sterowanie i implementacje przeszukiwania stanów
√
√
?
?
Podejścia do
przeszukiwania
stanów
Ślepe
Metodyczne
Analityczne
Heurystyczne
Stochastyczne
Systematyczne
(B-FS, D-FS)
Zalety i wady podejścia heurystycznego
3. Metody stochastyczne – wprowadzenie
God does not play dice …
A. Einstein
God not only plays dice, but he sometimes throws
them where they can’t be seen …
S. Hawking
Metody stochastyczne – grupa metod ilościowych
(statystycznych, ekonometrycznych, taksonomicznych i
dyskryminacyjnych) wykorzystywanych w badaniu i analizie
m.in. procesów gospodarczych
Podstawy metodologiczne:
• teoria zbiorów (m.in. zasady wyliczania
stanów, produkt kartezjański)
• probabilistyka (w tym wnioskowanie
probabilistyczne )
• twierdzenie Bayesa
3. Metody stochastyczne – zastosowania
Obszary zastosowań metod stochastycznych:
• diagnostyka
• rozumienie języka naturalnego
• planowanie i harmonogramowanie
• automatyczne uczenie
3. Metody stochastyczne - probabilistyka
Kategorie użyteczne w rozwiązywaniu
problemów i przeszukiwaniu stanów:
• zdarzenia (elementarne i złożone; zależne i niezależne) - Z
• przestrzeń stanów (możliwych zdarzeń) – S
• zmienne losowe - T/F, dyskretne i ciągłe
• wartość oczekiwana – zmiennej, zdarzenia
• prawdopodobieństwo zdarzenia – p(Z) = |Z|/|S|
• rozkład prawdopodobieństwa zdarzeń – macierze zdarzeń
z obliczonym prawdopodobieństwem
• prawdopodobieństwo warunkowe - zdarzeń
3. Metody stochastyczne – probabilistyka cd.
Wykorzystanie teorii prawdopodobieństwa:
• obliczanie prawdopodobieństwa wystąpienia
(przewidywanych w rozwiązywaniu problemu) sytuacji
• analiza przyczyn zjawisk zakłócających rozwiązywanie
problemu (zmienne losowe, metody kombinatoryczne,
próbkowanie zdarzeń, zdarzenia warunkowe)
• wnioskowanie probabilistyczne przy generowaniu
rozwiązania
3. Metody stochastyczne – probabilistyka cd.
R – Spowolnienie ruchu ; N – Naprawa drogi; W – Wypadek
SpowolNapra- Wypadek
nienie (R) wa (N) (W)
Prawdopodobieństwo
t
t
t
.01
t
t
n
.03
t
n
t
.16
t
n
n
.12
n
t
t
.01
n
t
n
.05
n
n
t
.01
n
n
n
R
.61
.12
W
.16
.01
.01
.01
.03
N
.05
Wyjaśnienie zdarzeń drogowych
– wykorzystujące wnioskowanie probabilistyczne
[Luger 2009]
3. Metody stochastyczne – probabilistyka cd.
c∩s
choroba c
p(c|s) = p(c ∩ s) / p(s)
symptom s
p(s|c) = p(s ∩ c) / p(c)
p(s ∩ c) = p(s|c) / p(c)
p(s|c) p(c)
p(c|s) = ----------------------p(s)
3. Metody stochastyczne – przestrzeń stanów
Skończona maszyna stanów (SMS):
Skończona maszyna stanów jest uporządkowaną trójką (S,I,F) gdzie:
S – skończony zbiór stanów w połączonym grafie s 1, s2 , s3, … sn
I – skończony zbiór wartości początkowych i 1, i2 , i3, … in
F – funkcja przekształcenia stanu taka, że dla dowolnego i ∈ I
opisuje rezultat stanu S maszyny taki, że ∀ i ∈ I, Fj : (S S)
Probabilistyczna skończona maszyna stanów (PSMS)
PSMS jest taką SMS, w
... zobacz całą notatkę
Komentarze użytkowników (0)