# AI - Lista ćwiczeniowa 2
###### tags: `AI`
## zadanie 1
:::info
Zaproponuj optymistyczną heurystykę dla zadania z końcówkami szachowymi z P1 (chodzi o heurystykę używaną w algorytmie A∗). Jak zmieniłoby się to zadanie (i heurystyka), gdyby czarne też miały wieżę i gdyby celem był jakikolwiek mat (tzn. mat białych lub czarnych)? W każdym wariancie postaraj się, by heurystyka zwracała możliwie duże wartości (i tym samym była użyteczna).
:::
| | A | B | C | D | E | F | G | H |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
| 1 | | | | | | | | |
| 2 | | | | | | | | |
| 3 | | | | | | | | |
| 4 | | | | | | | | |
| 5 | | | | | | | | |
| 6 | | | | | | | | |
| 7 | | | | | | | | |
| 8 | | | | | | | | |
| | A | B | C | D | E | F | G | H |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
| 1 | | | | | | | | |
| 2 | BW | | | | | | | |
| 3 | | | | | | | | |
| 4 | | | | | | | | |
| 5 | | | | | | | | |
| 6 | | | | | | | | |
| 7 | | | BK | | | | | |
| 8 | CK | | | | | | | |
| | A | B | C | D | E | F | G | H |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
| 1 | | | | | | | | |
| 2 | BW | | | | | | | |
| 3 | | | | | | BK | | |
| 4 | | | | | | | | |
| 5 | ← | ← | ←CK | | | | | |
| 6 | | | | | | | | |
| 7 | | | | | | | | |
| 8 | | | | | | | | |
### Biała wieża
odl. manhattańska
**$h_0(x)$ = (czarny król od najbliższej ściany) + (biały król od czarnego króla - 2)**
? $h_1(x)$ = (czarny król od najbliższej ściany $X$) + (biały król od $X$ - 2)
Własności:
- Optymistyczna, bo otrzymujemy liczbę ruchów mniejsza równa potrzebną do otrzymania mata
### Biała wieża i czarna wieża
-3 -> -4, bo?
Minimum z heurystyk dla jednego i drugiego.
**$h_0(x)$ = min(czarny król od najbliższej ściany, biały król od najbliższej ściany) + (odległość między królami (po przesunięciu?) -2)**
## zadanie 2
:::info
Zaproponuj jakąś istotnie inną końcówkę szachową (mile widziane skoczki i gońce), w której możliwy jest mat kooperacyjny. Bądź przygotowany, by wszystko wyjaśnić osobom nie znającym szachów. Podobnie jak w poprzednim zadaniu podaj dla tej końcówki optymistyczną (i użyteczną) funkcję heurystyki.
:::
```
1 czarny król, 1 biały, 2 białe skoczki.
a) Niemożliwe jest zaszachowanie króla kiedy nie jest on przy ścianie - dowód:
łączne pole w obrębie 9 polowego kwadracika 2 skoczków i jednego króla wynosi 7
niemożliwe zatem jest zaszachowanie króla i posiadaniu w polu bicia wszystkich
pól wokól niego
b) aby spełnić warunki szachu należy zatem doprowadzić czarnego króla do brzegu
niech x = odległośc czarnego króla od najbliższego brzegu
y = max(dist( czarny król, biał król) - 1, 0)
z = max(max(dist(skoczek1, czarny król) - 3, 0)
, max(dist(skoczek2, czarny król) - 3, 0)) // 3
gdzie dist to odległość taksówkowa
```
## Zadanie 3
:::info
Pokaż, że spójna heurystyka jest zawsze optymistyczna. Podaj przykład heurystyki, która jest optymistyczna, a nie jest spójna.
:::
#### Rozwiązanie 1.
Dowiedziemy to przez indukcję po odległości od stanu końcowego (od tyłu). (zakładając, że $h(t) = 0$).
Załóżmy, że h jest spójna tzn. $h(s_2) + cost(s_1, s_2) \geq h(s_1)$. Chcemy pokazać, że $h(s) \leq cost(s, t)$.
- Baza:
Weźmy dowolny stan końcowy t i rozważmy jego poprzedników (stany, z których możemy dojść do t w jednym kroku). Weźmy dowolny z tych poprzedników i nazwijmy go $n$. Wtedy ze spójności wiemy, że $h(n) \leq cost(n, t) + h(t) = cost(n, t)$. $\blacksquare$
- Krok:
Rozważmy dowolny stan $n$ i załóżmy, że $h$ jest spójne dla jego następników (tzn. stany do których możemy dojśc w jednym kroku i są one bliżej celu no wiecie o co chodzi XD). Mając te informacje możemy napisać, że $h(n) \leq cost(n, n^*) + h(n^*)$ ($n^*$ to dowolny następnik $n$). Z założenia indukcyjnego wiemy, że $h(n^*) \leq cost(n^*, t)$. Zatem możemy napisać, że $h(n) \leq cost(n, n^*) + cost(n^*, t)$. Widzimy, że prawa strona nierówności to prawdziwy koszt dotarcia z $n$ do $t$. Zapiszmy to $h(n) \leq cost(n, t)$. Jest to nierówność, którą mieliśmy udowodnić.
$\blacksquare$
###### Przykład
```graphviz
digraph{
rankdir=LR
A -> B [label=1]
B -> C [label=3]
A [shape=diamond];
C [shape=square];
}
```
$h(A) = 4, h(B) = 1, h(C) = 0$
$h(B) + cost(A, B) \geq h(A)$
$2 \geq 4$ Nie dziąłą :C
#### Rozwiązanie 2.
:::info
Uogólnienie własności spójności heurystyki:
Heurystyka $h$ spójna :
$\forall s_1, s_2\text{ sąsiadujące}. h(x_1) + count(x_1, x_2) \geq h(x_2)$
to:
$\forall \text{w spójnej składowej}(x_1, x_2). h(x_1) + d(x_1, x_2) \geq h(x_2)$
Dla $x_1 = x_2$ i dla $x_1$ i $x_2$ sąsiadującyj spełnione trywialnie
Weźmy dowolną drogę $x_1...x_nx_{n+1}$ załóżmy że:
$h(x_n) + d(x_n, x_1) \geq h(x_1)$
Ze spójności mamy:
$h(x_{n+1}) + count(x_{n+1}, x_n) \geq h(x_{n})$
Zatem:
$h(x_{n+1}) + d(x_{n+1}, x_1) = h(x_{n+1}) + count(x_{n+1}, x_n) + d(x_n, x_1)$
$\geq h(x_{n}) + d(x_n, x_1) \geq h(x_1)$
:::
Weźmy dowolną heurystykę $h$ spójną tzn. taką że:
$\forall x_1, x_2. h(x_1) + d(x_1, x_2) \geq h(x_2)$
Niech $c(x)$ będzie najbliższym punktem końcowym dla punktu $x$.
Chcemy pokazać że: $d(c(x), x) \geq h(x)$
Dla $x_1 = c(x)$ mamy: $h(c(x)) + d(c(x), x) \geq h(x)$
:::info
Trzeba zauważyć że heurystyka musi być rozsądna (tzn. $h(c(x)) = 0$) aby zadanie zadziałało inaczej istanieje kontrprzykład:
:::
Zatem mamy: $d(c(x), x) \geq h(x)$ co należało wykazać.
## Zadanie 4
:::info
Mówiliśmy (bez dowodu) na wykładzie, że heurystyka bazująca na odległości euklidesowej lub manhatańskiej jest spójna. Udowodnij nieco ogólniejsze twierdzenie, mówiące, że jeżeli na przestrzeni stanów zdefiniowana jest odległość (czyli jest to przestrzeń metryczna) to każda heurystyka, która zwraca wartość odległości od najbliższego stanu końcowego jest spójna.
:::
Definicja odległości:
$m(x,x) = 0\\
m(x,y) = m(y, x)\\
m(x, y) + m(y, z) \geq m(x, z)\\
m(x,y) \neq 0,\; x \neq y$
Heurystyka $h$ jest spójna, jeśli $h(s_2) + cost(s_1, s_2) \geq h(s_1)$.
Weźmy dowolną, ale ustaloną heurystukę $h$ taką, że $h(s) = min_{e \in SK}(m(s, e))$ (SK - zbiór stanów końcowych).
$h(s_2) + cost(s_1, s_2) \geq h(s_2) + m(s_1, s_2)$ (koszt przejścia nie jest mniejszy od odległości)
Niech $e_i$ oznacza najbliższy wierzchołek końcowy dla $s_i$ wtedy:
$m(s_2, e_2) + m(s_1, s_2) \geq m(s_1, e_1)$
Z nierówności trójkąta ($m(x, y) + m(y, z) \geq m(x, z)$)
$m(s_2, e_2) + m(s_1, s_2) \geq m(s_1, e_2)$
Skoro $e_1$ jest najbliższy dla $s_1$ to:
$m(s_1, e_2) \geq m(s_1, e_1)$
Razem mamy:
$h(s_2) + m(s_1, s_2) \geq m(s_1, e_1)$
$h(s_2) + cost(s_1, s_2) \geq h(s_1)$
## zadanie 5
:::info
Jeżeli przestrzeń stanów jest drzewem (czyli do każdego stanu da się dojść na dokładnie 1 sposób), wówczas warunkiem wystarczającym do optymalności algorytmu $A^∗$ jest, że heurystyka $h$ jest dopuszczalna (optymistyczna). Udowodnij to.
:::
Załóżmy, że $h$ jest optymistyczna tzn. $h(s) \leq cost(s, e)$. Weźmy stan końcowy $e^*$, który został znaleziony przez $A^*$ i załóżmy nie wprost, że nie jest on optymalny. Wtedy
$$
\exists e \in SK. g(e) < g(e^*)
$$
(SK stany końcowe). Oznacza to, że szukając ścieżki do stanu $e, A^*$ zatrzymał się w jakimś stanie (s to ostatni wierzochłek na trasie do e, który który jest w kolejce), nazwijmy go $s$. Tzn. $f(e*) \leq f(s)$ (bo $e^*$ został rozpatrzony wcześniej, czyli znajdował się wcześniej w kolejce priorytetowej). Wiemy też, że $h(s) \leq cost(s, e)$ (z optymistyczności heurystyki). Rozpiszmy teraz $g(e^*)$.
$$
g(e^*) \leq g(e^*) + h(e^*)\\
g(e^*) \leq f(e^*) \leq f(s) = g(s) + h(s) \leq g(s) + cost(s, e) = g(e)
$$
Otrzymujemy więc, że $g(e^*) \leq g(e)$ co jest sprzeczne z naszym założeniem, zatem A* jest optymalny.
## Zadanie 6
:::info
Powiedzmy, że rozwiązujemy za pomocą A∗ zadanie o podróżowaniu samochodem (warianty z paliwem, lub paczkami). Przyjmijmy, że liczba węzłów na mapie jest rzędu 100. Jaki preprocessing wydaje się być użyteczny dla liczenia funkcji h w każdym z tych wariantów? Dodatkowo zaproponuj optymistyczną heurystykę (o możliwie dużych wartościach) dla zadania z poprzedniej listy o podróżowaniu z paliwem.
:::
### Wariant dla paczek
Dla każdego punktu końcowego wyznaczam słownik odległości do pozostałych punktów końcowych.
```graphviz
graph{
rankdir=LR
A -- B [label=1]
B -- C [label=3]
A [shape=diamond];
C;
}
```
### Wariant dla paliwa
Tworzymy nowy graf, na którym są tylko miasta, które mają stacje, a krawędzie istnieją jak da się z jednego miasta dojechać do innego na pełny baku (plus oczywiście stań końcowy i początkowy).
Dijkstra
```graphviz
graph{
rankdir=LR
A -- B [label=1]
B -- C [label=3]
A [shape=diamond];
C [shape=rectangle];
}
```
h(s) = koniec(s) ? 0 : 100000000;
## Zadanie 7
:::info
Na wykładzie (W3, okolice slajdu 26) była podana informacja o najlepszych heurystykach dla 15-ki. Przypomnij te heurystyki i zaproponuj przeniesienie ich idei do zadania o Sokobanie.
:::
Dla **15-tki** najlepsza heurystyka to baza wzorców:
Działanie:
* znaleźć wszystkie podproblemy dla danego stanu
* maksimum tych kosztów to wartość heurystyki
W przypadku **Sokobana**:
Podproblemem będzie przesunięcie jednej spośród skrzynek ignorując położenie pozostałych skrzynek oraz magazyniera.
Dla tych skrzynek, które są pod ścianą (i w danym wierszu/kolumnie nie znajduje się pole docelowe) lub w rogu zwracamy jakąś BARDZO dużą wartość, żeby stany te nie były rozpatrywane przez A*.
#### V2
Dla każdej pozycji, na której może stać skrzynka (tj. nie ściana) i dla każdej pozycji końcowej w bazie wzorców pamiętamy liczbę ruchów potrzebną do przepchania skrzyni z danej pozycji do danej pozycji końcowej (na planszy bez innych skrzynek). Używamy tych wzorców w taki sposób: dla danej pozycji na planszy z bazy wzorców możemy odczytać jaki jest koszt przesunięcia
## Zadanie 8
:::info
Heurystyka $h_3$ dla 15-ki (zobacz W3, okolice slajdu 23) jest kosztem dla pewnej relaksacji tego zadania (ruch możliwy jest na wolne pole, niekoniecznie sąsiednie). Jak liczyć wartość tej heurystyki?
:::
Jak rozwiązywać zagadkę w ogólności:
```
Dopóki nie mamy rozwiązanej zagadki to:
jeśli pole a1 jest puste:
włóż tam dowolny klocek, który nie jest na miejscu
jeśli puste pole jest na miejscu klocka:
włóż tam klocek, który powinien tam być
```
A* z łatwiejszą heurystyką (ile nie na swoich miejscach). I liczymy długość drogi.
| | A | B | G | H |
| ----- | --- | --- | --- | --- |
| **1** | | 7 | | |
| **2** | 6 | 5 | | |
| **3** | 3 | 4 | | |
| **4** | 2 | 1 | | |
||||
|-|-|-|
||2|1|
|4|3|6|
|5|8|7|
## Zadanie 10
### a)
Spójność łukowa występuje wtedy, gdy dla więza dla zmiennych $X, Y$:
* dla każdej wartości $x$ z dziedziny $X$ istnieje wartość w dziedzinie $Y$, dla której więz jest spełniony
* dla każdej wartości $y$ z dziedziny $Y$ istnieje wartość w dziedzinie $X$, dla której więz jest spełniony
Algorytm AC-3 służy do osiągnięcia spojności łukowej. Na początku algorytmu dodajemy wszystkie więzy do kolejki. W każdym kroku bierzemy jeden więz z kolejki. Próbujemy zmniejszyć dziedziny zmiennych należących do tego więzu. Jeśli nam się to udało, np w zmiennej $x$, to dodajemy do kolejki wszystkie więzy, które zawierają w sobie $x$.
Złożoność algorytmu to $O(w \cdot d) \cdot t$, gdzie $d$ to rozmiar zmiennej, $w$ to liczba więzów, a $t$ to czas pracy z więzem
Dla danego więzu $\sum_{i=1}^n x_i \cdot c_i * y$ (gdzie $*$ oznacza operator) liczymy maksymalną i minimalną wartość sumy. Żeby policzyć maksymalną wartość bierzemy największe $x_i$ z dziedziny dla $c_i > 0$ oraz najmniejsze dla $c_i <= 0$. Żeby policzyć minimalną wartość sumy bierzemy największe $x_i$ z dziedziny dla $c_i < 0$ oraz najmniejsze dla $c_i \ge 0$. Znając skrajne wartości sumy możemy ograniczyć dziedzinę zmiennej $y$:
* gdy $*$ to $=$ to dziedzinę możemy ograniczyć z obu stron
* w przeciwnym przypadku możemy ją ograniczyć tylko z jednej.
Możemy też przeszkałcić daną nierówność w węźle, tak żeby ograniczać dziedziny zmiennych $x_i$(pamiętając o zmianie operatora na przeciwny, gdy $c_i < 0$):
$x_i * \frac{y}{c_i} - \sum_{j=1, j \ne i}^n x_j \cdot \frac{c_j}{c_i}$
Do ograniczenia zmiennej $x_i$ posłużą te same maksima i minima, które policzyliśmy dla y.
Wartości skrajne możemy raz policzyć na początku algorymu w czasie $O(w \cdot n)$, gdzie $w$ to liczba więzów, a $n$ to liczba zmiennych w węźle.
Do ograniczenia dziedzin możemy użyć algorytmu AC-3, ale do policzenia zmian w dziedzinach będziemy korzystać z kroków podanych wcześniej. Jeśli dla jakiejś zmiennej $x$ w węźle zmienimy dziedzinę to musimy do kolejki więzów dodać wszystko więzy, które zawierają $x$ oraz zaktualizować maksima i minima dla tych więzów. Taką zmianę możemy przeliczyć w czasie stałym. Sprawdzenie w których zmiennych w węźle można zmienić dziedziny trwa $O(n)$ (czas stały dla każdej zmiennej w węźle). W pesymistycznym przypadku zmienimy dziedzinę w tylko jednej zmiennej.
Podsumowując czas działania algorytmu to $O(w \cdot d) \cdot O(n) = O(w \cdot d \cdot n)$, gdzie $w$ to liczba węzłów, $d$ to rozmiar dziedziny, $n$ to liczba zmiennych w węźle.
### b)
Zmienne FD - zmienne o skończonych dziedzinach
Spójność łukowa :
Więz C dla zmiennych X i Y z dziedzinami $D_{x}$ i $D_{y}$ jest spójny łukowo, wtt:
* dla każdego $x \in D_{x}$ istnieje takie $y \in D_{y}$, że C(x, y) jest spełnione
* dla każdego $y \in D_{y}$ istnieje takie $x \in D_{x}$, że C(x, y) jest spełnione
Algorytm AC-3, idea:
Wrzucamy wszystkie więzy do kolejki. Następnie wyciągamy po jednym więzie i lecimy pętlą po wszystkich zmiennych z dziedziny X i dla każdej zmiennej z dziedziny Y spradzamy czy spełnia ona więz - jeśli nie spełnia to wyrzucamy zmienną x z dziedziny. Jeśli jakaś zmienna została usunięta z dziedziny to do kolejki wrzucamy wszystkie więzy Z, które są w jednym więzie z X.
Osiąganie spójności łukowej może być kosztowne - usuwanie zmiennej z dziedziny ma złożoność $O(d^{2})$,gdzie d jest wielkością dziedziny, a złożoność całego algorytmu ma złożoność $O(cd^{3})$, gdzie c jest ilością więzów.
$c_{i}$ są dane
$\sum c_{i}x_{i} * y$. Przechodzimy przez każdy z więzów i liczymy min i max.
Minimalizujemy więz:
1) jeśli $c_{i}$ jest ujemne to bierzemy maksymalne x z dziedziny
2) jeśli $c_{i}$ jest dodatnie to bierzemy minimalne x z dziedziny
i bierzemy minimalne y, które spełnia więz
Maksymalizujemy więz:
1) jeśli $c_{i}$ jest ujemne to bierzemy minimalne x z dziedziny
2) jeśli $c_{i}$ jest dodatnie to bierzemy maksymalne x z dziedziny
i bierzemy maksymalne y, które spełnia więz
Teraz ograniczamy dziedzinę y:
1) jeśli * to = -> wtedy dziedzina y to $<min_{y}, max_{y}>$
2) jeśli * to <= -> wtedy dziedzina y to $y <= max_{y}$
3) jeśli * to < -> wtedy dziedzina y to $y < max_{y}$
Sign in with Wallet
Connect another wallet