To tylko jedna z 39 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
1. Struktury i strategie przeszukiwania stanów
– fazy rozwiązywania problemu
Identyfikacja i analiza
problemu
Generowanie
potencjalnych rozwiązań
Weryfikacja rozwiązań i
podjęcie decyzji
Formułowanie problemów i
rozwiązania w realizowanych
projektach
1. Struktury i strategie przeszukiwania stanów
– scenariusz realizacji
Określenie celu
Identyfikacja stanu początkowego
Zdefiniowanienie możliwych operacji
Szukanie rozwiązań
Ocena wariantów
Wybór rozwiązania i wykonanie akcji
prowadzących do osiągnięcia celu
1. Struktury i strategie przeszukiwania stanów
– kwestie
Czy jest gwarancja rozwiązania
problemu?
Czy rozwiązania problemu nie
generują akcji powtarzalnych?
Czy znalezione rozwiązanie
problemu jest optymalne?
Jaka jest złożoność poszukiwania
rozwiązań (czas, zasoby)?
Czy można redukować przestrzeń
rozwiązań?
…
1. Struktury i strategie przeszukiwania stanów
-
przykład funkcji wspomagającej rozwiązywanie problemów
function PROBLEM-SOLVING-AGENT (fakt) returns action
inputs: fakt, obserwacja
static: seq, lista akcji (wstępnie pusta)
state, opis bieżącego stanu
goal, cel (wstępnie nieokreślony)
problem, sformułowany problem
state UPDATE-STATE (state, fakt)
if seq is empty then do
goal FORMULATE-GOAL(state)
problem FORMULATE-PROBLEM(state, goal)
seq SEARCH(problem)
action FIRST(seq)
seq REST(seq)
return action
1. Struktury i strategie przeszukiwania stanów
– definiowanie i rozwiązywanie problemów
Rodzaje problemów
Dobrze
zdefiniowane
Słabo
zdefiniowane
Precyzyjnie określone:
Niejasno określone:
cel, stan początkowy, akcje
cel, stan początkowy, akcje
Podać przykłady problemów dobrze
i słabo zdefiniowanych
1. Struktury i strategie przeszukiwania stanów
– definiowanie i rozwiązywanie problemów
Problem dobrze
zdefiniowany
Określony stan
początkowy
Pełna lista
możliwych akcji
Jednoznaczny test
osiągnięcia celu
Strategie
algorytmiczne
Łatwa ocena
rozwiązania
1. Struktury i strategie przeszukiwania stanów
– definiowanie i rozwiązywanie problemów
Problem słabo
zdefiniowany
Różne stany
początkowe
Niekompletna lista
możliwych akcji
Nieprecyzyjny test
osiągnięcia celu
Strategie
heurystyczne
Trudna ocena
rozwiązania
1. Struktury i strategie przeszukiwania stanów
– przykład rozwiązywania problemu
Abstrakcja
(ignorowanie szczegółów):
• oferty przewoźników
• warunki pogodowe
• obserwacja ruchu
• nawigacja urządzeń
• koszty przejazdu
• czas przejazdu
• …
Initial state = In(Gliwice)
dla stanu x
{, ,}
Initial state oraz Successor-Fn = przestrzeń stanów problemu
Test celu = aktualny stan jest celem?
Ocena = koszt akcji x do y c(x,a,y)
1. Struktury i strategie przeszukiwania stanów
– przykład rozwiązywania
(…)
… stanów
- teoria grafów w przeszukiwaniu stanów
Graf = zbiór węzłów i połączeń między nimi
(teoria L.Eulera – problem połączeń między
brzegami rzeki w Koenigsberg)
Reprezentowanie przestrzeni stanów rozwiązań
Węzły – odpowiadają stanom rozwiązań problemu (rezultat
wnioskowania, możliwe konfiguracje komponentów)
Łuki - wyrażają przejścia między stanami (wnioskowanie
lub możliwe akcje)
Student
posiada…
… przeszukiwania stanów
- problemy reprezentowania przestrzeni stanów
Przeszukiwanie przestrzeni stanów
rozwiązywanie problemu jako procesu znajdowania
przejścia od stanu początkowego do osiągnięcia celu
Różne formy wyrażania celu:
• stan (O i X)
• konfiguracja (puzzle)
• właściwości rozwiązania (problem komiwojażera)
• skuteczna analiza tekstu (boty)
Przestrzeń stanu jest reprezentowana przez: [W,L,S,C…
…
wnioskowania
1. Struktury i strategie przeszukiwania stanów
- strategia przeszukiwania w głąb (Depth-First
Search: D-FS)
A
A1
A11
A12
A A1 A11 A12
A2 A21
A3 A31 A32
A2
A21
A3
A31
A32
A
Efektywna
przy dużej
liczbie
rozgałęzień,
G-DS
1. Struktury i strategie przeszukiwania stanów
- strategia przeszukiwania wszerz (BreadthFirst Search: B-FS)
A
A1
A11
A12
A2
A21
A3
A31
A32
Efektywna przy
małej liczbie…
…
%initialize
% states remain
% goal found
% loop check
% no states left
1. Struktury i strategie przeszukiwania stanów
- algorytm przeszukiwania grafów and/or (lokalizacja)
1. Azor jest owczarkiem.
owczarek(azor).
2. Andrzej jest właścicielem Azora.
wlasciciel(azor,andrzej).
3. Dzień jest poniedzialek.
4. Jest zimno w poniedzialek.
dzien (poniedziałek).
¬ (cieplo(poniedziałek)).
5. Azor jest trenowany…
... zobacz całą notatkę
Komentarze użytkowników (0)