# SI - Ćwiczenia 3 - JULITA OSMAN

| 1| 2| 3| 4| 5| 6| 7| 8| 9|10|
|--|--|--|--|--|--|--|--|--|--|
| X| X| X| X| X| X| X| X| X| |

## Zadanie 1

**hill climbing**
* dla stanu znajdujemy wszystkie następniki i wybieramy ten, który ma największą wartość
* powtarzamy do momentu, w którym nie możemy nic poprawić

**local beam search**
* zamiast pamiętać pojedynczy stan, pamiętamy ich k (wiązkę)
* generujemy następniki dla każdego z k stanów
* pozostawiamy k liderów

**stochastic hill climbing**
* wybieramy losowo ruchy w górę (p-stwo stałe lub zależne od wielkości skoku)

**first choice hill climbing**
* losujemy następnika tak długo, aż będzie on ruchem w górę (dobre, jeśli następników jest bardzo dużo)

**symulowane wyżarzanie**
* przykładowa implementacja bazuje na first choice hill climbing
* jeśli wykonywany ruch jest lepszy (czyli prowadzi do lepszego stanu, ΔF > 0), to go wykonujemy (maksymalizując w ten sposób F)
* wwp. (ΔF ≤ 0) wykonujemy ruch z p-stwem $p = e ^{\frac{ΔF}{T}}$ (Im większe pogorszenie, tym mniejsze p-stwo, a im większa temperatura, tym większe p-stwo)
* pilnujemy, żeby T zmniejszało się w trakcie działania (i było cały czas dodatnie)


http://algorytmy.ency.pl/tutorial/symulowane_wyzarzanie
https://jakubnowosad.com/ahod/11-simulated-annealing.html#8

**algorytm ewolucyjny (genetyczny)**
stan = osobnik
zbiór stanów = populacja osobników

* zarządzamy populacją osobników
* mamy dwa rodzaje operatorów
* mutacja (z jednego osobnika robimy innego, podobnego)
* krzyżowanie (z dwóch osobników robimy jednego, podobnego do rodziców)
* nowe osobniki oceniane są względu na wartość funkcji przystosowania
* przeżywa k najlepszych

a) **hill climbing**
w local beam search mamy k-stanów i zostawiamy k najlepszych z ich następników. skoro k = 1, to pamiętamy pojedynczy stan i wybieramy najlepszy z jego następników, a to jest algorytm hill climbing

b) **bfs**
zaczynamy z jednym stanem początkowym i nie odrzucamy żadnego wygenerowanego stanu

c) **first choice hill climbing**
w każdej iteracji będziemy wybierać tylko te ruchy, które będą niegorsze. nie mamy jak policzyć prawdopodobieństwa, więc algorytm sprowadza się do wykonywania ruchu tylko jeśli jest on lepszy

d) **random walk**
wiemy, że im większa temperatura, tym większe p-stwo, więc skoro $T = \inf$, to p-stwo będzie równe 1. w takim razie za każdym razem kiedy będziemy brać kolejny stan, to będziemy go wykonywać bez względu na to czy jest lepszy czy gorszy.

e) **wariant local beam search (gdzie mutację traktujemy jako krok w przestrzeni stanów)**
robimy mutację i robimy lepszego osobnika
## Zadanie 2

**A***
* g(n) - koszt dotarcia do węzła n
* h(n) - szacowany koszt dotarcia od n do najbliższego punktu docelowego (h(s) > 0)
* f(n) = g(n) + h(n)
* przeprowadź przeszukiwanie, wykorzystując f(n) jako priorytet węzła (czyli rozwijamy węzły od tego, który ma najmniejszy f)

**taboo search**
* dodajemy pamięć algorytmowi, zabraniamy powtarzania ostatnio odwiedzanych stanów

**a)** mutacja w algorytmie ewolucyjny to hill climbing
Możemy oceniać mutacje i potomków i wybierać tylko tych, którzy są "lepsi" od np. osobnika z którego zmutował, albo rodziców, których jest potomkiem.

**b)** A* bierze kolejne stany korzystając z funkcji f, ale zostawia wszystkie z nich. zmodyfikujemy go w taki sposób, żeby podobnie jak beam search zostawiał tylko k najlepszych stanów. dzieki temu A* będzie bardziej optymalny pamięciowo (bo zapamiętujemy mniej stanów), ale może się zdarzyć, że nie zawsze znajdzie rozwiązanie (bo możemy odrzucić stan prowadzący do rozwiązania)

**c)** będzie to zwykły algorytm ewolucyjny, tylko czasem z jakimś prawdopodobieństwem będziemy wybierać gorszych osobników. Im gorszy osobnik tym mniejsze prawdopodobieństwo że go weźmiemy.

**d)** zapamiętujemy osobników których stworzyliśmy i w momencie kiedy tworzymy nową populację, sprawdzamy w tym zbiorze czy taki osobnik już kiedyś istniał. dzięki temu będziemy mieć zawsze nowych osobników w populacji
alternatywne rozwiązanie: do następnej populacji wybieramy liderów jedynie spośród dzieci

## Zadanie 3*
**Cykl Hamiltona** to taki cykl w grafie, w którym każdy wierzchołek grafu odwiedzany jest dokładnie raz.

**Graf pełny** – graf prosty, nieskierowany, w którym dla każdej pary węzłów istnieje krawędź je łącząca.

**Problem komiwojażera** - problem polegający na znalezieniu minimalnego cyklu Hamiltona w pełnym grafie ważonym.

Problem komiwojażera jest jednym z trudniejszych problemów optymalizacji. Jest określany jako NP-zupełny. Klasyczna metoda rozwiązania opiwera się na sprawdzeniu długości każdego cyklu Hamiltona co prowadzi do złożoności $O(n!)$. Z uwagi na wykładniczą klasę złożoności obliczeniowej w rozsądnym czasie możemy nzaleźć rozwiązanie tylko dla grafów o niedużej liczbie węzłów.

:::info
Nazwa pochodzi od typowej ilustracji problemu, przedstawiającej go z punktu widzenia wędrownego sprzedawcy (komiwojażera): dane jest n miast, które komiwojażer ma odwiedzić, oraz odległość / cena podróży / czas podróży pomiędzy każdą parą miast. Celem jest znalezienie najkrótszej / najtańszej / najszybszej drogi łączącej wszystkie miasta, zaczynającej się i kończącej się w określonym punkcie
:::

Stosując algorytm mrówkowy można znaleźć optymalne, bądź bliskie optymalnemu, rozwiązanie problemu komiwojażera. Można stworzyć populację mrówek, które będą poruszały się zgodnie z następującymi zasadami:

* każde miasto odwiedzone jest tylko raz (sztuczna mrówka wyposażona jest w pamięć w celu zapamiętania, które miasto już odwiedziła, aby uwzględnić je tylko jeden raz w swojej trasie)
* miasto bliższe jest atrakcyjniejsze niż dalsze
* prawdopodobieństwo wybrania ścieżki rośnie wraz z natężeniem feromonów

1. Najpierw każda krawędź ma takie samo prawdopodobieństwo zostania wybraną do ścieżki
2. Puszczamy kilka mrówek
3. Patrzymy na długości ścieżek jakie dostały; liczymy z nich np średnią. Dla ścieżek krószych niż średnia odrobinę zwiększamy prawdopodobieństwo wybrania krawędzi do nich należących, dla dłuższych - zmniejszamy

Mrówka przemieszcza się do kolejnego punktu z prawdopodobieństwem, które jest funkcją odległości do celu oraz wielkości śladu feromonowego pozostawionego na krawędzi łączącej dwa punkty


**Algorytm mrówkowy**

:::info
https://www.ii.pwr.edu.pl/~kwasnicka/tekstystudenckie/algorytmymrowkowe.pdf
+pdf

Do znalezienia najkrótszego cyklu będziemy używać cyber-mrówek, które w przeciwieństwie do tych prawdziwych potrafią dodatkowo:

Pamiętać już odwiedzone miasta.
Widzieć odległości między miastami.
Algorytm będzie wyglądał w ten sposób:

(Ten punkt można na wiele sposobów wykonać) Ustawiamy w każdym mieście po $m$ nowych cyber-mrówek.
Każda mrówka będzie przemieszczać się między miastami, aż wykona cały cykl. Poruszanie odbywa się według zasad:
Mrówka odwiedza każde miasto tylko raz.
Mrówka wybiera częściej miasta, które są od niej bliżej.
Mrówka wybiera częściej miasta, gdy na ścieżkach do nich prowadzących jest więcej feromonu.
Dla każdego wykonanego cyklu na drogach (z tego cyklu) pojawia się ilość feromonu uzależniona od sumarycznej długości cyklu (im krótszy cykl, tym więcej feromonu).
Na każdej drodze część feromonu wyparowuje.
W ten sposób po $n$ iteracjach w naszym grafie zacznie się wyłaniać optymalny cykl.
:::
## Zadanie 4

**Zmienne i dziedziny**
Dla każdego piksela tworzymy zmienną $Pij$
taką, że $D(Pij) = \{0,1\}$

Dla każdego rzędu oraz kolumny, których opis ma postać $(w_1, w_2, ..., w_n)$ tworzymy $n$ zmiennych.
$D(w_i)=\{0, 1, ..., szerokość-m\}$ gdzie m to długość bloku

**Więzy**
Żeby zapewnić właściwą kolejność bloków i odstęp minimum równy 1 między nimi:
$\forall{i\in{2, ..., n}} \space \space w_i > w_{i-1} + len(w_{i-1})$

Ostatni więz będziecie dotyczył korelacji między pikselami, a rzędami. Dla każdej zmiennej $w_i$, która reprezentuje blok pikseli odpowiednie piksele muszą być zamalowane:

$P_{w_i,j} = 1, P_{w_i+1,j} = 1, ..., P_{w_i+len(w_i) - 1,j} = 1$

Analogicznie dla kolumn.

## Zadanie 5

Krotki $(Przedmiot, Nauczyciel, Klasa)$ przerabimy na zmienne, których wartościami będą liczby z dziedziny $[1,50]$.

$T_{Przedmiot\_Nauczyciel\_Klasa} = termin$

Stwórzmy poprawny plan lekcji.
- Jeden nauczyciel bedzie miał maksymalnie jedną lekcję w jednym terminie.
- Jedna klasa bedzie miała jeden przedmiot w jednym terminie.

Generujemy ciąg węzłów o warunku dla każdego nauczyciela X

$T_{Przedmiot\_X\_Klasa} \quad\#/= \quad T_{Przedmiot\_X\_Klasa}$

I podobnie dla każdej klasy Y

$T_{Przedmiot\_Nauczyciel\_Y} \quad\#/= \quad T_{Przedmiot\_Nauczyciel\_Y}$

---

Aby pozbyć się problemu okienek, stwórzmy zmienne pomocnicze: $L_{Klasa\_DzienTygodnia\_NumerGodzinyLekcyjnej}$
Ich wartości będą definiowane przez spełnialność następującego węzła:
:::info
poniedziałek - 0, wtorek - 1, środa - 2...
:::
Przykłądowo dla klasy 2C, wtorek i trzeciej godziny tego dnia mamy:

$L_{2C\_WT\_3} \quad\#=\quad (T_{JAngielski\_JakubKowalski\_2C} \quad \#=\quad 13 \quad\#\lor\\\quad\quad\quad\quad\quad\quad\quad\quad T_{Matematyka\_MarekPodajmitalerz\_2C} \quad \#=\quad 13 \quad\#\lor\\\quad\quad\quad\quad\quad\quad\quad\quad T_{Przedmiot\_Nauczyciel\_2C} \quad \#=\quad 13)$

Czyli $L_{Klasa\_DzienTygodnia\_NumerGodzinyLekcyjnej}$ to alternatywa wszystkich przedmiotów (przedmiot, nauczyciel) danej klasy zrównanych do numeru godziny + numer dnia tygodnia przemnożony przez 10 (zaczynamy od 0).

Otrzymane więzy tworzą swego rodzaju ciągi binarne o stałej długości $10$ odpowiadające rozkładowi zajęć na dany dzień. Pozostaje tylko sprawdzić dla tych ciągów, czy nie wystepują w nich układy niedozwolone.

Możemy to zrobić generujac odpowiednie ciągi węzłów.
Musimy wziąć każdy zestaw zmiennych i ustalić, że nie mogą one być równe układowi zabronionemu.

Możemy każdej zmiennej nadać predykat $L_{2C\_WT\_3}$ tuples_in[...].
Znamy oczywiście wszystkie dozwolone wariacje których jest 45.
Dla na przykład 8 przedmiotów jednego dnia bedą to:
$1111111100, 0111111110, 0011111111$

## Zadanie 6
Wymagania:
1. Prowadzący ma tylko jedne zajęcia w danym czasie.
2. Sala jest zajęta tylko przez jedną grupę.
3. Jest wystarczająco miejsc dla studentów na wszystkich grupach zajęć obowiązkowych
4. Zajęcia obowiązkowe dla danego rocznika nie pokrywaja się, albo jeżeli odbywają się w różne dni o różnych porach - wtedy musi być zachowana własność, ze każdy student może się zapisać na zajęcia obowiązkowe.
5. Jeżeli istnieje jakiś limit zajęć dla prowadzącego to nie jest on przekroczony
6. Liczba studentów, którzy mogą sie zapisać na zajęcia ćwiczeniowe nie przekracza limitu
7. Pracownie odbywają się w pracowniach komputerowych
8. Ćwiczenia odbywaja się w salch ćwiczeniowych

Wymagania dodatkowe:
1. Zajęcia są umiarkowanie równomiernie rozdzielone między prowadzących - względem ich preferencji
2. Przedmioty na które głosowali ci sami studenci mają grupy, które nie pokrywają się godzinowo
4. Prowadzący nie mają dużych okienek
5. Nie przydzielamy sali wykładowej na ćwiczenia

Funkcja wartościuje plan według podanych kryteriów:
Jeżeli nie jest spełniony warunek twardy - zwraca (na przykład) wartość -100.
W przeciwnym razie dla punktów 1-3 zwraca zero, a dla punktu 4 zwraca wartości ujemne dla każdego przedmiotu, dla którego istnieje ryzyko wyścigu.

Dla wymagań miękkich wartościujemy. Przyznajemy każdemu przedmiotowi wartości przeliczajac głosy i dzieląc na 100. Pamiętamy jakie przedmioty dostały głosy od tych samych studentów.
Następnie za każde niepokrywające się ćwiczenia 2 przedmiotów z największą liczbą głosów tych samych studentów - przyznajemy 0,1 punkta. Dla takie zestawu 3 przedmiotów - 0,5 punkta, itd. Wyliczamy wyniki według rankingu studentów, którzy zagłosowali na dany przedmiot. Skale przemnażamy przez liczbe studentów, którzy zagłosowali na dany przedmiot podzieloną przez 100 - w ten sposób za ulokowanie przedmiotów obowiązkowych, na które zagłosowali studeńci (np 2 roku) dostaniemy nieujemną premię za warunek zwykły i dodatni za ulokowanie tych przedmiotów w sposób niekolidujący ze sobą, a dodatkowo dla przemiotów wybieranych typowo przez ten rocznik premie większą, za ustawienie obowiązków niekolidujących z tymi zajęciami)

Do całości jako punkty minusowe doliczamy warunki dotyczące prowadzących:
1. minus 5 za każda godzinę powyżej 5 z rzędu dla danego prowadzącego
2. minus 1 za każdą godzinę okienka między zajeciami

Całośc sumujemy i porównujemy wyniki.

## Zadanie 7

**Skoczki**

Celem gry jest przestawienie wszystkich swoich pionków na pozycje zajmowane na początku przez przeciwnika, czyli przeciwległe, skrajne dwie linie pól. Gracz, który pierwszy tego dokona − wygrywa. Nie ma możliwości gry remisowej.

Ruch polega na:

- przesunięciu swojego pionka na dowolne sąsiednie pole wolne poziomo lub pionowo (do przodu, do tyłu lub na boki),
- przeskoczeniu przez pionek własny lub przeciwnika z pola bezpośrednio sąsiadującego z przeskakiwanym pionem na pole bezpośrednio za nim,
- przeskoczeniu kilku pionów swoich lub przeciwnika z pola bezpośrednio sąsiadującego z przeskakiwanym pionem na pole bezpośrednio za nim,
- wykonaniu całej serii skoków jednym pionkiem zgodnie z dwiema poprzednimi zasadami – zmiana kierunku kolejnych skoków jest możliwa.

**Heurystyka**
:::info
Nasza funkcja heurystyczna będzie brała pod uwagę 3 parametry:

Sumaryczną odległość naszych pionów od docelowego rzędu (odległość w pionie) oraz jednocześnie analogiczną sumaryczną odległość, ale dla przeciwnika.
Nadmiar skoczków w kolumnie, każdy nadmiarowy (więcej niż 2) skoczek w dowolnej z kolumn wymaga co najmniej jednego ruchu, żeby to poprawić. Analogicznie liczymy ten nadmiar dla przeciwnika.
Najlepszy (dowolny z najlepszych) ruchów jakie możemy wykonać. Bierzemy pod uwagę czy taki ruch nie ułatwi przeciwnikowi wykonania względnie lepszego ruchu (niż jego najlepszy).
:::

:::info
Funkcja jako argument otrzymuje tablice z pozycjami pionów obu graczy oraz gracza, który ma wykonać ruch.

Dla obu graczy obliczamy za pomocą BFS minimalną liczbę ruchów potrzebnych na dojście każdym pionem na pole leżące w dwóch docelowych rzędach. Dla gracza, który aktualnie jest na ruchu zapamiętujemy pierwszy ruch tej optymalnej sekwencji dla każdego z pionów.

Teraz dla pozycji powstałych po wykonaniu każdego z tych ruchów (pojedynczo) sprawdzamy jak zmieniła się minimalna liczba ruchów dla gracza na ruchu oraz jego przeciwnika i wybieramy ten ruch, który minializuje wartość dla gracza na ruchu oraz maksymalizuje ją dla przeciwnika.

W lepszej sytuacji jest gracz, który po tym ruchu ma mniejszą minimalną liczbę ruchów do ustawienia pionów na docelowych rzędach.
:::
## Zadanie 8*

**Reversi**
Celem gry jest wypełnienie planszy większą liczbą własnych pionów niż przeciwnik.

Gra rozgrywana na planszy 8x8 pól. Każdy z dwóch graczy ma do dyspozycji pionki: jeden koloru białego, drugi -- czarnego. Początkowo na planszy znajdują się po dwa pionki każdego z graczy, ułożone jak na poniższym obrazku. Gracze układają na przemian pionki własnego koloru na wolnych polach planszy do momentu, aż plansza zostanie całkowicie zapełniona lub żaden z graczy nie będzie mógł wykonać dozwolonego ruchu. Dozwolony ruch to taki, w którym pionek jest ułożony na polu, które znajduje się w linii (poziomej, pionowej lub ukośnej) z innym pionkiem gracza wykonującego ruch, i na dokładnie wszystkich polach pomiędzy wybranym polem a tym pionkiem znajdują się pionki przeciwnika. Te pionki zostają po wykonaniu ruchu przejęte i zmieniają kolor na przeciwny (tzn. na kolor pionków gracza, który wykonuje ruch).

**Heurystyka**
Warto premiować następujące aspkety gry:
- liczba pionków
- liczba przejętych rogów (ponieważ jeśli uda się przejąć róg, to przeciwnik nie jest w stanie go odwrócić)
- liczba możliwych do wykonania ruchów (jeżeli nie jesteśmy w stanie wykonać żadnego ruchu to możemy być zdani tylko na przeciwnika co raczej nie poprawi naszej sytuacji, więc wolimy mieć dużą liczbę możliwych ruchów do wykonania).
- liczba pionków, które nie mogą zostać przejęte przez przeciwnika

Heurystyka wynikowa może być sumą powyższych heurystyk (z odpowiednimi wagami np. zależącymi od tego na którym ruchu jesteśmy - nie warto premiować zachłannego podejścia zdobywania na początku dużej liczby pionów. Lepiej skupić się na tym dopero w końcowej fazie rozgrywki, a w początkowej postarać się przejąć "strategicznie" ważne pola).

## Zadanie 9

Pierwszy gracz ma przewagę, ponieważ ma większą szansę, że gracz 2 nie zdobędzie o nim wystarczająco informacji żeby go blokować.

Agent zaczyna:
1. Zaczynamy od kółka po środku
2. Potem wybieramy dowolny narożnik:
- jeśli jest dostępny to ok
- próbujemy dokończyć
- jeśli się nie udało to stawiamy kółko w którymś z rogów które przeciwnik może próbować wykorzystać (z tym samym prawdopodobieństwem)
- jeśli nie to:
- wybieramy albo któryś z 2 rogów z wolnych przekątych (1/6, bo to ta sama opcja) albo sąsiednie do buczącego pola (1/3)
- próbujemy dokończać, jeśli się nie da to blokujemy jeśli wzieliśmy wcześniej narożnik, wpp losowo

Agent jest drugi:
1. Zaczynamy od środka, jeśli jest zajęty to bieżemy dowolny narożnik (daje on nam więcej możliwości)
2. Jeśli wzieliśmy narożnik to próbujemy wziąć któryś z kolejnych narożników
- jeśli to możliwe to w następnym ruchu probujemy dokończyć (albo się uda, jak się nie uda to mamy wystarczająco dużo informacji żeby dalsza strategia była oczywista)
- jeśli nie to blokujemy
3. Jeśli udało się wziąć na początku środek to musimy losowo próbować zablokować pierwszego gracza

## Zadanie 10