# Sztuczna inteligencja, grupa PUz, lista 2

## Ćwiczenia

Poniedziałek 14-16

---

# można wpisywać kod z formatowaniem python
for i in range(10):
    print (22)

Wzory wyglądają ładnie: $f(N) = \sum_1^N \frac{1}{n^2+1} + \min(a_1, \dots, a_N)$

---

## Deklaracje

* Mikołaj Balwicki SUMA: ZADANIA:
* Marcin Bieganek SUMA: 7 ZADANIA: 1, 3, 4, 5, 6, 7, 8
* Dominik Hawryluk SUMA: ZADANIA:
* Józef Kowalewicz SUMA: ZADANIA:
* Marcin Szmagara SUMA: 5 ZADANIA: 1, 3, 4, 6, 8
* Paweł Szmergała SUMA: 7 ZADANIA: 1, 3, 4, 5, 6, 7, 8
* Vladyslav Yablonskyi SUMA: 4 ZADANIA: 1, 3, 4, 5

Przydział zadań na spotkaniu 14:25
Preentacja rozwiązań 15:15

## Rozwiązania

### Zadanie 1: Marcin Bieganek

Mamy zaproponować heurystykę dla końcówek szachowych z zadania 1 z P1. Dążymy do szacha dla białych, gdzie biały gracz ma króla i wieżę, a czarny tylko króla.

W takiej sytuacji, aby wystąpił mat, biały król musi być w odległości 2 od czarnego króla oraz czarny król musi stać przy krawędzi szachownicy.
Możemy zaproponować heurystykę, która wylicza ile ruchów jest potrzebne, aby dany stan przekształcić w stan spełniający te warunki.
Taka heurystyka będzie brała maksimum z dwóch wartości:
* odległość kartezjańska pomiędzy królami - 2
* minimalna odległość czarnego króla od krawędzi

Gdy czarny gracz dostanie wieże i celem zadania będzie uzyskanie dowolnego mata, to nasza heurystyka powinna oszacowywać koszt do najbliższego mata (dla biały lub dla czarnych).
W tym celu możemy wyliczyć wartości heurystyki z poprzedniego podpunktu dla obu królów i wybrać minimum z tych wartości.

### Zadanie 2:

### Zadanie 3: Marcin Szmagara

Pierwsza część:

Niech $o(x, y)$ to odległość wierzchołków $x$ i $y$. Załóżmy nie wprost, że nie jest optymistyczna. Wtedy istnieje taki wierzchołek $v$, że $h(v) > o(v, end)$. Rozpatrzmy najkrótszą ścieżkę od $v$ do stanu końcowego $end$. Wtedy albo dla każdego $u$ na tej ścieżce $h(u) > o(u, end)$, czyli w szczególności dla sąsiada $s$ wierzchołka $end$ mamy $h(s) > o(s, end)$, czyli $h(s) > cost(s, end) + h(end)$ (z założenia, że $h(end) = 0$), albo mamy taki wierzchołek $k$, że $h(k) <= o(k, end)$ na tej ścieżce. Dodatkowo, niech $k$ będzie najbliższym takim wierzchołkiem do $v$. $k$ ma więc takiego sąsiada $l$, że $h(l) > o(l, end)$.
Dodajemy dwie ostatnie nierówności: $h(l) + o(k, end) > o(l, end) + h(k)$. Odejmując $o(k, end)$ obustronnie otrzymujemy $h(l) > h(k) + cost(l, k)$, sprzeczność.

Kontrprzykład do drugiej części:

    graph{
        1--2 [label="10, 1"];
        2--3 [label="10, 15"];
    }

Pierwsze wartości na krawędziach to rzeczywiste koszty.
$h(x)$ to suma drugiej spośród liczb na krawędziach na ścieżce od $x$ do $1$.
Rozpatrzmy wartość heurystyki dla wierzchołka $3$ w stosunku do wierzchołka $2$. Jest optymistyczna, bo $1+16 < 20$, ale nie jest spójna, bo $1 + 10 < 16$.

### Zadanie 4: Vladyslav Yablonskyi
Jeśli przestrzeń jest metryczna to zachodzi na niej nierówność trójkąta $(z < x + y)$.

rozpatrzmy 2 przypadki.
1) s1 i s2 mają ten sam najbliższy punkt docelowy
h(s1) = z
h(s2) = y
c(s1, s2) = x
Wprost z definicji nierówności trójkąta wynika, że $h(s2) + c(s1, s2) \geq h(s1)$
2) s1 i s2 mają rożne najbliższe punkty docelowe
h(s1) = x
h(s2) = y
c(s1, s2) = c
czy $h(s2)+c(s1, s2) \geq h(s1)$?
z nierówności trójkąta wynika, że $y + c \geq z$
$z \geq x$ bo $e_1$ jest najbliszym punktem docelowym dla s1.
Więc $y+c \geq x$ i $h(s2) + c(s1,s2) \geq h(s1)$

### Zadanie 5: Vladyslav Yablonskyi
**Jeśli przestrzeń stanów jest drzewem i $h$ jest optymistyczna wtedy algorytm $A^*$ jest optymalny?**.

(1) Skoro przestrzeń stanów jest drzewem to do każdego stanu da się dojść na dokładnie 1 sposób.

Załóżmy, że $p^*$ ściżka wyprodukowana z $A^*$ nie jest optymalną ścieżką. Wtedy z (1) wynika, że w jakimś kroku s musieliśmy pojść niepoprawną ścieżką, a póżniej wrócić do stanu s, ale wtedy ($h(s) >$ prawdziwy koszt dotarcia ze stanu $s$ do stanu końcowego) więc $h$ nie jest optymistyczna. **Sprzeczność**

### Zadanie 6: Paweł Szmergała

$n$ --- liczba miast; w tym zadaniu rzędu 100

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

Heurystyka dla zadania o podróżowaniu z paliwem.
Zdefiniujmy:
* $FW(a,b)$ --- długość najkrótszej ścieżki między miastami a i b, wyliczona w preprocessingu
* $t$ --- miasto docelowe

$h(s) =
\begin{cases}
FW(s,t) \text{, jeśli w baku mamy co najmniej } FW(s,t) \text{ paliwa} \\
\min\{FW(s,x) + FW(x,t) \mid x \text{ jest miastem ze stacją benzynową}\} \text{ w p.p.}
\end{cases}$

### Zadanie 7: Paweł Szmergała

#### Najlepsze heurystyki dla 8-ki

Najlepsze heurystyki dla 8-ki polegają na utworzeniu bazy danych minimalnej liczby ruchów potrzebnych do rozwiązania każdego z podproblemów.
Podproblemem 8-ki nazywamy taką jej modyfikację, w której wybrane klocki (np. 1, 2, 3, 4) pozostawiamy bez zmian, a pozostałych nie rozróżniamy (zastępujemy symbolem \*). Zliczamy tylko ruchy rozróżnialnych klocków.


Bazy danych wzorców tworzymy dla rozłącznych podproblemów, np. dla (1, 2, 3, 4) oraz (5, 6, 7, 8).
Jako wartość heurystyki dla danego stanu bierzemy sumę wartości dopasowanych wzorców z baz danych dla wszystkich rozłącznych podproblemów.

#### Podobna idea dla Sokobana

Tutaj analogicznie będziemy tworzyć bazy wzorców dla podproblemów.
Podproblemy tworzymy, usuwając część skrzynek z głównego problemu.
Wartością heurystyki dla stanu z ogólnego problemu jest maksymalna wartość z bazy danych wzorców jednego z podproblemów.
Rozwiązanie podproblemu wymaga mniejszej liczby ruchów niż rozwiązanie głównego problemu, dlatego taka heurystyka jest dopuszczalna.

### Zadanie 8: Marcin Bieganek


Heurystyka $h_3$ jest kosztem rozwiązania relaksacji tego zadania, polegającej na tym, że ruch klocka jest możliwy na wolne pole, ale niekoniecznie sąsiednie.

Mamy powiedzieć jak policzyć wartość takiej heurystyki, czyli tego kosztu, przy tak zmodyfkiowanych zasadach.

Wartość $h_3$ dla danego stanu możemy policzyć wykonując symulację rozwiązywania tego zadania:

koszt <- 0
Dopóki nie doszliśmy do stanu końcowego:
    Jeśli wolne pole w obecnym stanie jest polem docelowym jakiegoś klocka:
        przenosimy ten klocek na to wolne pole
    Wpp:
        przenosimy dowolny klocek, który nie jest na swojej pozycji docelowej na to wolne pole
    koszt <- koszt + 1

### Zadanie 9:

### Zadanie 10: