W3

Question 1

Czym sie charakteryzuje agent celowy

Answer 1

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ą

Question 2

Jaka jest różnica między poszukiwaniem nieinformowanym, a informowanym?

Answer 2

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

Question 3

Cztery kroki przy poszukiwaniu rozwiązania

Answer 3

1. Sformułowanie celu zadania - jaki stan systemu odpowiada osiągnięciu celu?
2. Sformułowanie zadania - określenie stanów i rodzajów działań
3. Poszukiwanie - określenie optymalnych działań, które należy wykonać aby osiągnąć cel
4. Wykonanie zadania

Question 4

Rodzaje zadań poszukiwania

Answer 4

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:
• 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)

Question 5

Zadanie jednostanowe - sformułowanie

Answer 5

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.

Question 6

Co to abstrakcja?

Answer 6

Ś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.

Question 7

Poszukiwania nieinformowane: Algorytmy przeszukiwania drzew

Answer 7

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;
• 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.

Question 8

Jakie struktury wchodza w sklad algorytmow przeszukiwania nieinformowanego

Answer 8

• 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

Question 9

Strategie algorytmów przeszukiwania drzew

Answer 9

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

Question 10

Poszukiwanie wszerz (breadth-first search) BFS

Answer 10

➡️ 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ń

Question 11

Poszukiwanie w głąb (depth-first search) DFS

Answer 11

➡️ 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&raquo_space; d
• 💾 Pamięć: O(bm) - liniowa złożoność względem pamięci
• 🆗 Optymalność: Nie

Question 12

Poszukiwanie na ograniczoną głębokość (depth-limited search)

Answer 12

➡️ 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

Question 13

Poszukiwanie pogłębiane iteracyjnie (iterative deepening search)

Answer 13

➡️ 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

Question 14

Poszukiwanie dwukierunkowe (bidirectional search)

Answer 14

➡️ 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

Question 15

Podsumowanie algorytmow przeszukiwania nieinformowanego

Answer 15

• 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

Question 16

Czym jest zasada poszukiwania informowanego w sztucznej inteligencji?

Answer 16

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.

Question 17

Jak wykorzystywana jest funkcja heurystyczna h(n) w poszukiwaniach informowanych?

Answer 17

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.

Question 18

Jaka jest rola kolejki priorytetowej w implementacji algorytmów poszukiwań informowanych?

Answer 18

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)

Question 19

Zdefiniuj pojęcie “heurystyki” w kontekście poszukiwań informowanych.

Answer 19

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.

Question 20

Co sprawia, że heurystyka jest “dopuszczalna” lub “zgodna” w poszukiwaniach informowanych?

Answer 20

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’.

Question 21

Co oznacza, że jedna heurystyka dominuje nad inną?

Answer 21

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.

Question 22

Jak można stworzyć dobrą heurystykę dopuszczalną?

Answer 22

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.

Question 23

Czym różni się heurystyka dopuszczalna od zgodnej?

Answer 23

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.

Question 24

Algorytm najpierw najlepszy (best-first)

Answer 24

Algorytm rozwija węzeł który leży najbliżej celu.

Question 25

Najpierw najlepszy agresywny (greedy best-first)

Answer 25

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

Question 26

Algorytm A*

Answer 26

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

Question 27

Jakie sa inne warianty Algorytmu A* pozwalajace zachowac jego zalety a oszczedzic pamięć

Answer 27

• 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

Question 28

Co to algorytmy poszukiwań lokalnych i do czego są przydatne

Answer 28

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.

Question 29

Algorytm najszybszego wzrostu (hill-climbing)

Answer 29

💡 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

Question 30

Algorytm symulowanego wyżarzania

Answer 30

💡 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

Question 31

Algorytmy genetyczne

Answer 31

💡 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

Question 32

Jakie sa zalety poszukiwań lokalnych

Answer 32

✅ Zalety:

• nie potrzebują wielkiej pamięci
• pozwalają rozwiązywać zadania o bardzo dużym wymiarze stan

Question 33

Czym różnią się zadania poszukiwania od zadań z ograniczeniami (CSP)?

Answer 33

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.

Question 34

Jak definiowany jest cel w zadaniach CSP?

Answer 34

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.

Question 35

Jakie są cechy charakterystyczne zadań z ograniczeniami (CSP)?

Answer 35

Zadania z ograniczeniami charakteryzują się standardowym sposobem sformułowania, standardowymi funkcjami następstwa i celu oraz standardowymi heurystykami niezależnymi od specyfiki zadania.

Question 36

Jak można przedstawić zadanie binarne z ograniczeniami?

Answer 36

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.

Question 37

Podaj przykłady zadań CSP.

Answer 37

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.

Question 38

Jak sformułowane jest zadanie CSP jako zadanie poszukiwania?

Answer 38

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.

Question 39

Jaki jest podstawowy algorytm dla zadań CSP?

Answer 39

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ń.

Question 40

Jakie strategie stosuje się w poszukiwaniu wstecznym w CSP?

Answer 40

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).

Question 41

Podsumowanie wiedzy o CSP

Answer 41

• 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