# Sztuczna Inteligencja 2023-04-04

| Imię i nazwisko | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|:---------------------:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:--:|
| Kacper Chmielewski | x | | x | x | x | x | x | | | |
| Jakub Cieśluk | x | x | x | x | x | x | x | | x | |
| Mateusz Marszałek | x | | x | x | x | x | x | x | | |
| Julia Matuszewska | x | | x | x | x | x | | | | |
| Jan Pułtorak | x | x | x | x | x | x | x | | | x |
| Bogdan Rychlikowski | | | x | x | x | x | x | x | x | x |
| Rafał Stochel | x | x | x | x | x | x | x | x | | |
| Cyryl Szatan | x | | x | x | x | x | x | x | | x |
| Szymon Szendzielorz | x | | x | x | x | x | x | x | | |

## Zadanie 1

Prezentuje: **Cyryl Szatan**

> Zaproponuj optymistyczną heurystykę dla zadania z końcówkami szachowymi z P1 (chodzi o heurystykę używaną w algorytmie A*). Jak zmieniaoby 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).


Heurystyka rozpatruje wszystkie stany gdzie czarny król jest na bandzie, a biały król blokuje go, żeby nie mógł z bandy uciec. Oblicza odległość taksówkową do takiego stanu (suma odległości jaką musi pokonać czarny król i biały król). Po czym bierze minimum z tych obliczonych wartości.

Heurystyka jest optymistyczna, ponieważ w tym przypadku każda partia zakończy się sytuacją gdzie czarny król jest na bandzie, a biały go blokuje. Tylko czasami będzie trzeba jeszcze zrobić ruch wieżą lub pójść królami nie po najkrótszej ścieżce

Przypadek z dwoma wieżami jest podobny. Heurystyka musi rozpatrywać dodatkowo(poza wyżej wymienionymi sytuacjami) stan gdzie jeden z króli (np czarny) jest w rogu, a biały blokuje go po skosie.

## Zadanie 2

Prezentuje: **Rafał Stochel**

> 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 potencjalnie użyteczną) funkcję heurystyki.

h(s) = b + w + k + g

odległość dla króli: odległość Czebyszewa
$max(|x_2 - x_1|, |y_2 - y_1|)$

b - odległość czarnego króla od krawędzi

w - odległość białego króla od dwóch miejsc do czarnego króla

k - odległość skoczka od szachowania bądź blokowania czarnego króla

g - odległość gońca od przekątnej do szachowania króla bądź odległość od pola, gdzie
goniec będzie blokował dwa sąsiednie pola króla


## Zadanie 3

Prezentuje: **Mateusz Marszałek**

> Pokaż, że spójna heurystyka jest zawsze optymistyczna. Podaj przykład heurystyki, która jest optymistyczna, a nie jest spójna. Uwaga: nie wymagamy, by przykład był realistyczny - może to być dowolny graf i dowolnie okreslona heurystyka.

Definicja spójnej heurystyki:
Dla każdego wierzchołka N i dla każdego potomka P zachodzi
$h(N)\leq c(N,P)+h(P)$

Dowód
$h(N)\leq c(N,p_1)+h(p_1)$
$h(p_1)\leq c(p_1,p_2)+h(p_2)$
.
.
.
$h(p_{n-1})\leq c(p_{n-1},G)+h(G)$
$h(G)=0$
$h(N)\leq c(N,p_1)+c(p_1,p_2)+....+c(p_{n-1},G)$

Przykład heurystyki która jest optymistyczna ale nie spójna
$A\rightarrow B$
$B\rightarrow C$
$c(A,B)=1$
$c(B,C)=3$
$h(A)=4$
$h(B)=2$
$h(C)=0$

## Zadanie 4

Prezentuje: **Julia Matuszewska**

> Zadanie 4. 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.

**Dowód nie wprost**
Załóżmy, że nasz algorytm zwrócił nieoptymalną ścieżkę ALG

Weźmy jakieś optymalne rozwiązanie OPT o największym wspólnym prefixie z naszym (nieoptymalnym rozwiązaniem)
Rozważmy pierwszy wierzchołek V, w którym rozwiązanie naszego algorytmu różni się od OPT (wierzchołek V').

Jeżeli wybraliśmy inny wierzchołek, to wtedy, zgodnie z naszym algorytmem, wybraliśmy go, bo się okazało, że miał mniejszą wartość, niż wierzchołek V' wybrany w rozwiązaniu OPT.

Ale to oznacza, że h(V) <= h(V'), więc musi istnieć droga z V do wierzchołka końcowego, ale do wierzchołka końcowego z założenia o tym, że mamy "drzewiastą" strukturę stanów, może prowadzić tylko jedna droga, prowadząca przez V'.

Stąd mamy cykl lub OPT nie jest optymalny (lub V' jest nie gorszy, co oznacza, że wynik naszego algorytmu jest nie gorszy z def.)

Sprzeczność z założeniami

## Zadanie 5

Prezentuje: **Szymon Szendzielorz**

> Powiedzmy, że rozwiązujemy za pomocą A* zadanie o podróżowaniu samochodem (warianty z paliwem, lub paczkami z poprzedniej listy ćwiczeniowej). 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.

n - liczba miast (rzędu 100)

Preprocessing: algorytm Floyda-Warshalla, wyznaczający długości najkrótszych ścieżek między wszystkimi parami wierzchołków.

Nasza heurystyka będzie polegać na braniu najkrótszej ścieżki między miastami, jeśli mamy wystarczająco paliwa w baku lub najkrótszej ścieżki przez miasto ze stacją beznynową.

$d(a, b)$ - najkrótsza ścieżka między miastami a i b
$T$ - miasto docelowe
$x$ - miasto ze stacją benzynową

$$ h(s) = \begin{cases} d(s,T), \text{jeśli mamy w baku w co najmniej d(s,T) paliwa} \\ \min(d(s,x) + d(x,T)) \text{ w.p.p} \end{cases}$$

## Zadanie 6

Prezentuje: **Jan Pułtorak**

> Na wykładzie (W3, okolice slajdu 35) była podana informacja o najlepszych heurystykach dla 15-ki. Przypomnij te heurystyki i zaproponuj przeniesienie ich idei do zadania o Sokobanie.

Najelpsze heurystki do 15-ki polegają na relaksacji, tzn skupiamy się na prostszym problemie i dla danego stanu liczba ruchów potrzebna do rozwiązania łatwiejszego problemu jest heurystyką.

Heurystyki do 15-ki:
Patrz zadanie 7

W sokobanie, rozważmy następującą relaksację:
1. Skrzynie ruszają się w dowolnym kierunku, oraz mogą przechodzić przez inne skrzynie.
2. Poszukujemy takiego rozwiązania, że sumaryczna ilość popchnięć jest minimalna

Przed rozwiązywaniem obliczamy odległości od pól końcowych dla każdego pola niebędącego ścianą.
W danym stanie, mamy k skrzyń i k miejsc docelowych i dla każdej skrzyni mamy obliczoną odległość do każdego z pól końcowych. Możemy na to patrzeć jak na problem min-matchingu w grafu dwudzielnym.
Możemy to zrobić w czasie O(k^3) - gdzie k to liczba skrzyń.
## Zadanie 7

Prezentuje: **Kacper Chmielewski**

> Heurystyka h3 dla 15-ki (zobacz W3, okolice slajdu 32) jest kosztem dla pewnej relaksacji tego zadania (ruch możliwy jest na wolne pole, niekoniecznie sąsiednie). Jak liczyć wartość tej heurystyki?


1. Jeśli liczba jest na swoim miejscu to przechodzimy do rozpatrzenia kolejnej liczby
2. Jeśli na miejscu docelowym jest wolne pole liczymy odległość manhatańską.
3. Jeśli miejsce docelowe jest zajęte, wtedy niech:
- H - będzie odległością manhatańską rozpatrywanej liczby od celu "C",
- G - będzie odległością manhatańską liczby znajdującej na "C" do jej rozwiązania.


## Zadanie 8

Prezentuje: **Rafał Stochel**

> W zadaniu rozważymy ogólną metodę binaryzacji, dla więzów, które są zdefiniowane za pomocą wyrażeń arytmetycznych i symboli relacyjnych (przykładowo $2A + 4B > 7C + D^2 + EF + G^3$). Pokaż, jak zamieniać takie więzy na więzy o arności 2 lub 3 (być może dodając nowe zmienne, pamiętaj o tym, że nowe zmienne muszą mieć dziedziny). A następnie pokaż, jak eliminować więzy o arności 3 (zamieniając je na binarne).


## Zadanie 9

Prezentuje: **Jakub Cieśluk**

> Przypomnij, co to jest spójność łukowa i algorytm AC-3. Osiąganie spójności łukowej może być kosztowne, zwłaszcza, gdy dziedziny zmiennych są duże (dlaczego?). Można tę spójność przybliżać, zajmując się jedynie krańcami dziedzin (czyli wartością najmniejszą i największą). Powiedzmy, że więzy mają postać: $\sum^N_{i=0} c_ix_i ◦ y$, gdzie $c_i$ są stałymi, $x_i$, $y$ to zmienne FD, a $◦ \in \{<, ≤, =\}$. Opisz algorytm wnioskowania (propagacji), który analizując kolejne więzy stara się w możliwie największym stopniu ograniczać ich dziedziny (ale zmieniając jedynie dolne i górne ograniczenia tych dziedzin). Oszacuj jego złożoność (czasową i pamięciową).


Kosztowne, bo np. weźmy dziedziny - zbiory liczb naturalnych (< 1 000 000), musielibyśmy pojedynczo wykreślać wartości.

##### 1. Dla więzu w postaci $\sum c_i x_i < y$: Chcielibyśmy usunąć Y mniejsze (lub równe) od wszystkich kombinacji X i X większe (lub równe) od wszystkich Y.

Najpierw liczymy $minSum = \sum c_i min(X_i)$, potem podnosimy ograniczenie dolne Y do $Y > minSum$. Potem zmniejszamy ograniczenie górne $X_i$ na $(max(Y) - minSum) / c_i + min(X_i)$. Robimy to dla każdego i.

##### 2. Dla więzu $\sum c_i x_i = y$ możemy zaznacząć od usunięcia X mniejszych od wszystkiego w Y i Y większych od wszystkich kombinacji X. Później robimy to samo co w 1. (ale z $Y \ge minSum$)

Czyli liczymy $maxSum = \sum c_i max(X_i)$, obniżamy górną granicę Y do $maxSum$ i podnosimy dolne $X_i$ do $max(X_i) - (maxSum - min(Y) / c_1$. Robimy to dla każdego i. (usuwamy te mniejsze od każdego Y)
Teraz usuwamy X wieksze od każdego Y:
Możemy też zrobić  to co dla $<$, ale z ograniczeniem dolnym dla Y $Y >= minSum$

##### 3. Dla więzu $\sum c_i x_i \le y$. Usuwamy Y mniejsze od każdej kombinacji X i X większe od każdej kombinacji Y.

To samo co w drugim kroku w 2.

Złożoność:
N - liczba zmiennych
K - liczba więzów
Pamięciowa O(N) + pamięć na więzy O(NK) = O(NK)
Czasowa:
Póki coś się zmienia:
Dla każdego więzu:
1.Policz minSum/maxSum O(N)
2.Podnieś/obniż ograniczenia O(N)

O(N) * liczba sprawdzeń więzu. Każda zmienna może być włożony (max(X) - min(X)) razy, przy zmianie wkładamy wszystkie węzły z nią (maksymalnie K), więc w sumie mamy N*K*d możliwych sprawdzeń więzów.
Wychodzi O(N * N * K * d), gdzie d to max - min

## Zadanie 10

Prezentuje: **Bogdan Rychlikowski**

> Pokaż, że Differential heuristic (W3, końcówka) jest optymistyczna. Zaproponuj jakiś sposób wyboru K punktów orientacyjnych inny niż losowanie z równym prawdopodobieństwem, co do którego masz nadzieję, że będzie działał lepiej niż losowy.