# GPT2

## Zadanie 1
No ogólnie to pewnie byśmy chcieli sprawdzać jakoś kiedy król będzie na bandzie (a drugi jakoś przed nim)

Czyli pewnie coś w stylu:
### Wariant 1
$\forall k \in Pola.skrajne \quad \{cz + min(b_1, b_2) + moves\}$
Gdzie
cz - pozycja czarnego króla
b - pozycja białego króla
Mamy $b_1, b_2$, bo jesli czarny będzie w rogu to biały ma 2 pola z których może zmatować

### Wariant 2
$\forall k \in Pola.skrajne \quad \{ min(cz + min(b_1, b_2) , \quad b + min(cz_1, cz_2)) + moves \}$

## Zadanie 2
Możemy na przykład zaproponować mat z 2 gońcami
Chcemy, aby czarny król znalazł się w rogu, więc pomysł analogicznie jak w zadaniu 1
$\forall k \in Rogi \quad \{cz + min(b_1, b_2) + moves \}$
*możliwe, że nie rogi tylko pola obok rogów, ale i tak analogicznie

## Zadanie 3

Baza
$h(s_{end}) = 0 \leq real(s_{end}, s_{end})$

Izba
Załóżmy, że $h(s_n)$ jest optymistyczny. Pokażmy, że $h(s_{n+1})$ też

Ze spójności
$h(s_n) + cost(s_n, s_{n+1}) \geq h(s_{n + 1})$, ale wiemy też
$h(s_n) \leq real(s_{end}, s_n)$ z optymistyczności $h(s_n)$
$h(s_n) + cost(s_n, s_{n+1}) \leq real(s_{end}, s_n) + cost(s_n, s_{n+1}) \leq real(s_{end}, s_{n+1})$ więc
$h(s_{n + 1}) \leq h(s_n) + cost(s_n, s_{n+1}) \leq real(s_{end}, s_{n+1})$


## Zadanie 4
*AISD*
Weźmy jakieś optymalne rozwiązanie o największym wspólnym prefixie.
Rozważmy pierwszy wierzchołek V w którym nasz algorytm idzie inną ścieżką niż opt.
1. Jeśli wybraliśmy jakiś inny, bo się okazało, że ma mniejszą wartość
Ale jeśli tak się stało to oznacza, że $h(V) \leq h(V')$, więc musi istnieć droga z V do końcowego, ale do końcowego powinna przebiegać tylko jedna droga (prowadząca przez V'), stąd otrzymaliśmy cykl albo opt nie jest optymalny
2. Wybranie wierzchołka o większej heurystyce byłoby sprzeczne z samym algorytmem A*, więc nie rozważamy tego przypadku

## Zadanie 5

### Wariant 1
Puśćmy dijkstrę z końcowego wierzchołka
Dlaczego?
No możemy mieć heurystykę, która próbuje brać wierzchołki które najbardziej zbliżają nas do celu. Jest ona optymistyczna, bo zawsze bierzemy najkrótszą ścieżkę do celu (czasem nie będzie ona odpowiedzią, bo braknie nam paliwa), ale to nas nie boli, bo mamy spełniony przez to warunek optymistyczności.

### Wariant 2
Dijkstra z każdego wierzchołka (ewentualnie początkowego i tych k różnych zależy od interpretacji)

## Zadanie 6
### Pomysł 1
W Sokobanie zliczamy ile skrzynek jest nie na swoim miejscu uwu

### Pomysł 2
Sprawdźmy ile ruchów musimy wykonać, żeby postawić skrzynkę na najbliższym polu docelowym (tylko że dla każdego pola docelowego szukamy najbliższej skrzynki) (Heura to suma po tych odległościach)

## Zadanie 7

|1 |2 |3 |4 |
|5 |6 |7 |8 |
|9 |10|11|12|
|13|14|15|x |

No to bierzemy najmniejszy możliwy cykl i symulujemy go (albo znajdujemy zależność i mamy wzór, ale kto by o tym myślał)

## Zadanie 8

A + B > C + D
=>
X > Y
X = A+B
Y = C+D

Jeśli możemy dostać wyrażenia z wieloma symbolami relacyjnymi

## Zadanie 9


Chcemy wrzucić parę, minimalną i maksymalną wartość z każdej dziedziny. Potem puszczamy fora po więzach $O(c)$ i robimy te warunki
a) Jeśli minimum z jakiejś dziedziny nie spełnia -> usuń i wrzuć nową minimalną na kolejkę
b) analogicznie do a), ale maksimum
Po każdym z warunków znowu puszczamy fora OD NOWA

* Mamy n zmiennych, dziedziny mają wielkość $O(d)$. Mamy c więzów.
* Obsługa więzu to $O(2)[?]$
* Każdy więż może być włożony do kolejki co najwyżej $O(d)$ razy.
Czasowo chyba $O(cd)$?
Pamięciowo $O(c + d)$

## Zadanie 10

W takim razie h(n) $\le$ dojechanie do G a nawet czasem równe (od trasy do L odejmujemy (L,G) operacje na wektorach czy coś)

NA PEWNO bedzie to mniejsze niż (N,G) bo znowu operacje na wektorach i chuj