W3 Flashcards
Czym sie charakteryzuje agent celowy
Agent celowy poszukuje rozwiązania realizującego cel w zbiorze rozwiązań dopuszczalnych.
Na takiej zasadzie opiera się działanie wielu agentów, np.:
- agenci - obiekty w grach komputerowych, symulatorach
- oprogramowanie przewodników drogi wykorzystujących system GPS
- agenci poszukujący w Internecie stron z żądaną zawartością
Jaka jest różnica między poszukiwaniem nieinformowanym, a informowanym?
Podstawową zasadą poszukiwań nieinformowanych jest korzystanie wyłącznie z definicji zadania - bez wykorzystywania dodatkowych informacji.
Wada: przypominają one próbę dojechania w mieście samochodem na podany adres gdy zna się tylko ten adres oraz reguły prowadzenia samochodu. 🚗
Strategie poszukiwania wykorzystujące dodatkowe informacje o zadaniu nazywa się informowanymi
Idea: dodatkowa informacja może posłużyć do najkorzystniejszego uporządkowania węzłów
przed ich rozwinięciem
Cztery kroki przy poszukiwaniu rozwiązania
- Sformułowanie celu zadania - jaki stan systemu odpowiada osiągnięciu celu?
- Sformułowanie zadania - określenie stanów i rodzajów działań
- Poszukiwanie - określenie optymalnych działań, które należy wykonać aby osiągnąć cel
- Wykonanie zadania
Rodzaje zadań poszukiwania
Zadanie najprostsze:
-
Deterministyczne, obserwowalne ⇒ zadanie jednostanowe
- agent wie w jakim jest stanie i w jakim stanie się znajdzie;
rozwiązanie jest ciągiem stanów
Zadania znacznie trudniejsze:
- agent wie w jakim jest stanie i w jakim stanie się znajdzie;
-
Nieobserwowalne ⇒ zadanie bez czujników (conformant problem)
- agent nie wie gdzie jest
-
Niedeterministyczne lub obserwowalne częściowo ⇒ (contingency problem)
- obserwacje dostarczają nowych informacji o stanie bieżącym
- poszukiwania często przeplatają się z działaniami
- Nieznana przestrzeń stanów ⇒ (exploration problem)
Zadanie jednostanowe - sformułowanie
Zadanie jednostanowe zdefiniowane jest za pomocą czterech elementów:
- stan początkowy, np. „jestem w Arad”
- działanie lub funkcja następstwa
S(x) = zbiór par 〈działanie, stan po działaniu〉$
np. S(Arad) = {〈Arad → Zerind, Zerind〉, …}
-
test osiągnięcia celu
- jawny, np. x = ”w Bukareszcie”
- niejawny, np. w szachach Mat(x);
-
koszt drogi (addytywny)
- np. suma odległości, liczba podjętych działań, etc.
- c(x, a, y) jest kosztem kroku x → y, z założenia c ≥ 0
Rozwiązaniem zadania jednostanowego jest ciąg działań
prowadzących ze stanu początkowego do stanu docelowego.
Rozwiązanie optymalne cechuje najmniejszy koszt.
Co to abstrakcja?
Świat rzeczywisty jest krańcowo skomplikowany, dlatego przestrzeń stanów musi być
abstrakcją stanów rzeczywistych. Abstrakcja oznacza pominięcie szczegółów.
Działanie abstrakcyjne to złożona kombinacja działań rzeczywistych,
np.
Arad→Zerind reprezentuje złożony zbiór możliwych tras, objazdy, parkingi, etc.
Aby zapewnić istnienie rozwiązania, każdy stan rzeczywisty (np.
Arad)
musi prowadzić do jakiegoś stanu rzeczywistego (np. Zerind).
Rozwiązanie abstrakcyjne to zbiór rzeczywistych dróg, które
są rozwiązaniami w świecie rzeczywistym.
Każde działanie abstrakcyjne powinno być łatwiejsze niż rzeczywiste.
Poszukiwania nieinformowane: Algorytmy przeszukiwania drzew
Idea algorytmów przeszukujących:
-
ślepe poszukiwania: analiza wszystkich możliwych sekwencji stanów
- koszt rośnie gwałtownie ze wzrostem liczby możliwych
stanów;
- koszt rośnie gwałtownie ze wzrostem liczby możliwych
-
poszukiwania poprzez budowę drzewa stanów:
- korzeń - stan początkowy
- węzły i gałęzie - generowane są funkcją następstwa
Algorytm przeszukiwania tworzy (”rozwija”) nowe węzły, wypełnia odpowiednie pola,
a następnie tworzy stany w nowych węzłach.
Jakie struktury wchodza w sklad algorytmow przeszukiwania nieinformowanego
- Stan określa jednoznacznie konfigurację fizyczną obiektu
- Węzeł jest to struktura danych określająca część drzewa poszukiwań, obejmująca np.: stan, węzeł rodzica, węzły dzieci, koszt gałęzi, aktualną głębokość, podejmowane działanie, itp.
- Brzeg (fringe) to zbiór wszystkich węzłów, które nie zostały jeszcze rozwinięte
Strategie algorytmów przeszukiwania drzew
Strategia poszukiwania jest określona kolejnością rozwijania węzłów
Strategie są oceniane wg następujących kryteriów:
- zupełność: możliwość znalezienia rozwiązania, jeżeli istnieje
- złożoność czasowa: proporcjonalna do liczby rozwijanych węzłów
- złożoność pamięciowa: największa liczba węzłów w pamięci
- optymalność: możliwość wyznaczenia najtańszego rozwiązania
🚨 Największą wadą poszukiwań nieinformowanych jest wykładniczy wzrost kosztu obliczeń.
Krytyczna jest zwłaszcza ilość wymaganej pamięci, gdyż może ona być gigantyczna
nawet dla zadań o umiarkowanych wymiarach
Złożoność czasowa i pamięciowa są szacowane za pomocą następujących wielkości:
- b: maksymalny współczynnik rozgałęzienia drzewa poszukiwań
- d: głębokość na której jest rozwiązanie optymalne
- m: maksymalna głębokość przestrzeni stanów
Poszukiwanie wszerz (breadth-first search) BFS
➡️ Zasada: rozwinąć najpłytszy nierozwinięty węzeł na brzegu
Brzeg jest kolejką FIFO, tzn. nowy węzeł wstawiany jest na koniec kolejki
Własności algorytmu:
- ✅ Zupełność: Tak, jeżeli b jest ograniczone
- ⏰ Czas: O(bd+1) (1+b+b2+b3+… +bd + b(bd-1))
- 💾 Pamięć: O(bd+1) (przechowywanie wszystkich węzłów w pamięci)
- 🆗 Optymalność: Tak, jeżeli koszt kroku jest stały
🚨 Pamięć jest największym problemem, większym niż czas poszukiwań
Poszukiwanie w głąb (depth-first search) DFS
➡️ Zasada: rozwinąć najgłębszy nierozwinięty węzeł na brzegu
Brzeg jest kolejką LIFO, tzn. nowy węzeł wstawiany jest na początek kolejki
Własności algorytmu:
- ✅ Zupełność:
- Tak w przestrzeniach skończonych
-
Nie w przestrzeniach nieskończonych, z pętlami (wymaga wtedy modyfikacji
w celu uniknięcia powtarzających się stanów)
- ⏰ Czas: O(b^m) - ogromny jeżeli m»_space; d
- 💾 Pamięć: O(bm) - liniowa złożoność względem pamięci
- 🆗 Optymalność: Nie
Poszukiwanie na ograniczoną głębokość (depth-limited search)
➡️ Zasada: jak w algorytmie poszukiwania w głąb ale z głębokością ograniczoną do poziomu l
Własności algorytmu:
- ✅ Zupełność: Tak, jeżeli l ≥ d
- ⏰ Czas: O(b^l)
- 💾 Pamięć: O(bl)
- 🆗 Optymalność: Tak, jeżeli l ≤ d
Poszukiwanie pogłębiane iteracyjnie (iterative deepening search)
➡️ Zasada: wyznaczyć iteracyjnie najlepszą głębokość l
Cel jest osiągnięty na głębokości d odpowiadającej najpłytszemu węzłowi docelowemu.
Algorytm łączy zalety algorytmów poszukiwania wszerz i w głąb.
Własności algorytmu:
- ✅ Zupełność: Tak
- ⏰ Czas: O(b^d)
- 💾 Pamięć: O(bd)
- 🆗 Optymalność: Tak, jeżeli koszt kroku jest stały
Poszukiwanie dwukierunkowe (bidirectional search)
➡️ Zasada: jednoczesne poszukiwanie z początku i końca
Własności algorytmu:
- ✅ Zupełność: Tak, jeżeli oba poszukiwania wszerz
- ⏰ Czas: O(b^{d/2})
- 💾 Pamięć: O(b^{d/2})
- 🆗 Optymalność: Tak, jeżeli oba poszukiwania wszerz
Podsumowanie algorytmow przeszukiwania nieinformowanego
- Rozwiązywanie zadań poprzez przeszukiwanie wymaga
sformułowania zadania w postaci abstrakcyjnej. - Jeżeli zadanie jest deterministyczne i obserwowalne
(jednostanowe), to do jego rozwiązania można użyć
algorytmu poszukiwania nieinformowanego. - Istnieje wiele algorytmów poszukiwania nieinformowanego:
- wszerz
- w głąb
- kosztu jednorodnego
- stałej głębokości
- pogłębiania iteracyjnego
- poszukiwań dwukierunkowych
- Algorytm poszukiwania poprzez pogłębianie iteracyjne jest
najlepszym algorytmem ogólnym - wymaga liniowej pamięci
a czas obliczeń jest niewiele większy niż w przypadku innych
algorytmów. - Agenci działający na zasadzie poszukiwania rozwiązania
są używani w wielu dziedzinach:- wyznaczaniu drogi
- planowaniu układów VLSI
- nawigacji robotów
- poszukiwań internetowych
Czym jest zasada poszukiwania informowanego w sztucznej inteligencji?
Algorytmy poszukiwań informowanych wykorzystują funkcję heurystyczną do szacowania najniższego kosztu ścieżki do celu. Wybór węzła do rozwinięcia opiera się na szacowanej funkcji kosztu f(n) = g(n) + h(n), gdzie g(n) to koszt ścieżki od początku do węzła n, a h(n) to szacowany koszt od n do celu.
Jak wykorzystywana jest funkcja heurystyczna h(n) w poszukiwaniach informowanych?
h(n) jest kluczową częścią poszukiwań informowanych, nie występuje w oryginalnym sformułowaniu problemu. Oszacowuje koszt od węzła n do celu, opierając się na dodatkowych informacjach heurystycznych, co upraszcza proces podejmowania decyzji w skomplikowanych sytuacjach.
Jaka jest rola kolejki priorytetowej w implementacji algorytmów poszukiwań informowanych?
W poszukiwaniach informowanych brzeg drzewa wyszukiwania zarządzany jest jako kolejka priorytetowa, gdzie węzły są priorytetyzowane na podstawie ich szacowanego całkowitego kosztu dotarcia do celu, ocenianego przez funkcję heurystyczną f(n)
Zdefiniuj pojęcie “heurystyki” w kontekście poszukiwań informowanych.
Heurystyka, czyli „reguła kciuka”, to strategia lub metoda ułatwiająca podejmowanie decyzji lub rozwiązywanie problemów bardziej efektywnie poprzez uproszczenie procesu, zwłaszcza gdy dokładne rozwiązanie jest skomplikowane lub nieznane.
Co sprawia, że heurystyka jest “dopuszczalna” lub “zgodna” w poszukiwaniach informowanych?
Heurystyka jest dopuszczalna, jeśli nigdy nie przeszacowuje prawdziwego kosztu dotarcia do celu (h(n) ≤ h^*(n)). Jest zgodna, jeśli spełnia nierówność trójkąta h(n) ≤ c(n,a,n’) + h(n’) dla każdej akcji a prowadzącej od n do n’.
Co oznacza, że jedna heurystyka dominuje nad inną?
Jeśli istnieją dwie dopuszczalne heurystyki h_1(n) i h_2(n) takie, że h^*(n) ≥ h_2(n) ≥ h_1(n) dla każdego węzła n, to h_2 dominuje nad h_1. Dominująca heurystyka jest bardziej efektywna, gdyż dostarcza bliższe oszacowanie prawdziwego kosztu.
Jak można stworzyć dobrą heurystykę dopuszczalną?
Dobrą heurystykę dopuszczalną można stworzyć przez rozluźnienie warunków zadania (rezygnacja z niektórych ograniczeń), co pozwala na wykorzystanie funkcji rozwiązującej problem w uproszczonej formie. Takie podejście zapewnia, że użyta heurystyka nigdy nie przeszacowuje rzeczywistego kosztu, prowadząc do optymalnego rozwiązania.
Czym różni się heurystyka dopuszczalna od zgodnej?
Heurystyka dopuszczalna nigdy nie przeszacowuje kosztów rzeczywistego osiągnięcia celu, podczas gdy heurystyka zgodna dodatkowo spełnia nierówność trójkąta, co oznacza, że koszt szacowany przez heurystykę dla każdego węzła n jest mniejszy lub równy sumie kosztu kroku do następnika n’ i heurystyki tego następnika.
Algorytm najpierw najlepszy (best-first)
Algorytm rozwija węzeł który leży najbliżej celu.
Najpierw najlepszy agresywny (greedy best-first)
Funkcja szacująca: f(n) = h(n)
Własności algorytmu:
- ✅ Zupełność: Nie, mogą powstawać zapętlenia
- ⏰ Czas: O(b^m), ale dobra heurystyka może go znacznie zmniejszyć
- 💾 Pamięć: O(b^m) (przechowywanie wszystkich węzłów w pamięci)
- 🆗 Optymalność: Nie
Algorytm A*
Najlepsza wersja algorytmu najpierw najlepszy (best-first)
Funkcja szacująca: f(n) = g(n) + h(n)
Do oszacowania h(n) algorytm A* używa heurystyki.
Przykład: h(n) nigdy nie jest większa od odległości drogowej z n do celu
Własności algorytmu:
- ✅ Zupełność: Tak, chyba że istnieje nieskończenie wiele celów o tym samym koszcie
- ⏰ Czas: Wykładniczy
- 💾 Pamięć: Wykładniczy (przechowywanie wszystkich węzłów w pamięci)
- 🆗 Optymalność: Tak
Jakie sa inne warianty Algorytmu A* pozwalajace zachowac jego zalety a oszczedzic pamięć
- IDA* (Iterative-Deepening A) - A pogłębiany iteracyjnie
- RBFS (Recursive Best-First Search) - połączenie algorytmu best-first i BT
- SMA* (Simplified Memory-Bounded A) - A ograniczony pamięciowo
Co to algorytmy poszukiwań lokalnych i do czego są przydatne
Algorytmy poszukiwań lokalnych to kluczowy element rozwiązywania problemów optymalizacyjnych, szczególnie tych, gdzie przestrzeń rozwiązań jest bardzo duża i złożona. Ich głównym celem jest znajdowanie jak najlepszego rozwiązania, często poprzez minimalizowanie lub maksymalizowanie określonej funkcji celu.
Algorytm najszybszego wzrostu (hill-climbing)
💡 Idea: zmiana stanu powinna najlepiej poprawić jakość stanu
Zmiany stanu są dobierane tak, aby funkcja celu osiągnęła największą wartość w otoczeniu stanu aktualnego.
🚨 Problem: algorytm może znajdywać maksima lokalne funkcji celu
✅ Rozwiązanie: Losowy wybór pomiędzy kierunkami wspinaczki pozwala uniknąć maksimum lokalnego
Algorytm symulowanego wyżarzania
💡 Idea: dopuszczenie “złych” zmian stanu w celu ominięcia maksimów lokalnych
Pozwala to “przeskoczyć na następny pagórek” i w ten sposób uniknąć minimum lokalnego
Złe zmiany stanu muszą być coraz mniejsze i zachodzić coraz rzadziej
Jeżeli temperatura maleje dostatecznie wolno, to algorytm symulowanego wyżarzania znajduje maksimum globalne
Algorytmy genetyczne
💡 Idea: naśladowanie natury poprzez dobór naturalny najlepiej przystosowanych “osobników” – rozwiązań zadania
- Algorytm operuje na zbiorze k stanów (populacji)
- Stan jest reprezentowany przez łańcuch (gen) utworzony z liter alfabetu skończonego (często alfabet jest binarny: (0 i 1)
- Funkcja szacująca (funkcja dopasowania) - większe wartości odpowiadają stanom “lepiej dostosowanym”
- Start ze zbiorem k stanów wygenerowanych losowo
- Stan potomny jest generowany przez kombinację dwóch stanów rodzicielskich
- Nowa generacja stanów uzyskiwana jest za pomocą selekcji, krzyżowania i mutacji
Jakie sa zalety poszukiwań lokalnych
✅ Zalety:
- nie potrzebują wielkiej pamięci
- pozwalają rozwiązywać zadania o bardzo dużym wymiarze stan
Czym różnią się zadania poszukiwania od zadań z ograniczeniami (CSP)?
W zadaniach poszukiwania stan może być dowolną strukturą umożliwiającą wyznaczanie następników i obliczanie funkcji kosztu. W zadaniach z ograniczeniami (CSP) stan jest zbiorem zmiennych X_i z określonych dziedzin D_i, a cel jest definiowany przez spełnienie ograniczeń C_i takich jak C_2: X_1 ≥ X_2.
Jak definiowany jest cel w zadaniach CSP?
Cel w zadaniach CSP jest zdefiniowany poprzez ograniczenia C_i, które muszą być spełnione przez wartości zmiennych stanu. Rozwiązaniem jest zbiór wartości zmiennych, które spełniają wszystkie te ograniczenia.
Jakie są cechy charakterystyczne zadań z ograniczeniami (CSP)?
Zadania z ograniczeniami charakteryzują się standardowym sposobem sformułowania, standardowymi funkcjami następstwa i celu oraz standardowymi heurystykami niezależnymi od specyfiki zadania.
Jak można przedstawić zadanie binarne z ograniczeniami?
Zadanie binarne z ograniczeniami można przedstawić w formie grafu, gdzie węzły reprezentują zmienne, a krawędzie to ograniczenia między nimi. Uproszcza to proces poszukiwania rozwiązania.
Podaj przykłady zadań CSP.
Przykłady zadań CSP to: kolorowanie map, kompozycja parkietów, kryptografia, układanie planu zajęć, planowanie transportów, organizacja produkcji, dyslokacja wojsk, szeregowanie obserwacji dla teleskopu Hubble’a.
Jak sformułowane jest zadanie CSP jako zadanie poszukiwania?
W zadaniu CSP stan początkowy to puste przypisanie. Funkcja następnika przypisuje wartości wolnym zmiennym bez naruszania ograniczeń. Test celu sprawdza, czy przypisanie jest kompletne. Koszt drogi jest stały na każdym kroku.
Jaki jest podstawowy algorytm dla zadań CSP?
Podstawowym algorytmem nieinformowanym dla zadań CSP jest poszukiwanie wsteczne (backtracking search), gdzie przypisuje się wartości zmiennym jedna po drugiej i cofa się kroki, gdy nie można przypisać wartości następnej zmiennej bez naruszenia ograniczeń.
Jakie strategie stosuje się w poszukiwaniu wstecznym w CSP?
Strategie stosowane w poszukiwaniu wstecznym w CSP to wybór najbardziej ograniczonej zmiennej (most constrained variable), wybór najmniej ograniczającej wartości (least constraining value) oraz sprawdzanie w przód (forward checking).
Podsumowanie wiedzy o CSP
- Poszukiwania z ograniczeniami stanowią szczególny rodzaj zadań, w których:
- stan jest zbiorem zmiennych, którym przypisane są wartości z określonego zbioru - dziedziny
- cel zdefiniowany jest poprzez ograniczenia nałożone na wartości zmiennych
- Metoda poszukiwania wstecznego to odmiana poszukiwań w głąb stosowana w zagadnieniach CSP
- Efektywność metody poszukiwania wstecznego znacznie poprawiają uporządkowanie zmiennych i dobre heurystyki wyboru wartości.
- Przy rozwiązywaniu zadań praktycznych bardzo efektywny jest algorytm minimalnych konfliktów
