krzynkrzyn / aal_2019_01_15 Goto Github PK

Imię i nazwisko: Krzysztof Najda

======================================================================================================================================================
Specyfikacja problemu:
======================================================================================================================================================
Mamy na płaszczyźnie XY dokładnie N punktów. W jednym ruchu możemy zaznaczyć zbiór punktów, z których wszystkie są współliniowe, i usunąć je. 
Celem gry jest usunięcie wszystkich punktów w jak najmniejszej liczbie ruchów. 
Zaproponuj algorytm, który wyliczy minimalną liczbę ruchów potrzebną do usunięcia wszystkich punktów oraz liczbę możliwych kombinacji ruchów służących usunięciu tych punktów (przy czym jeden ruch różni się od innego jeśli przynajmniej jeden punkt jest usunięty w innym ruchu).

======================================================================================================================================================
Polecenia aktywacji programu:
======================================================================================================================================================
-m	Wybór trybu uruchomienia programu
	1 - Zbiór punktów podawany przez standardowe wejście
	2 - Zbiór punktów generowany jednym z generatorów
	3 - Uruchomienie eksperymentu złożoności czasowej algorytmów

-g	Wybór generatora punktów [tylko dla trybu -m 2]
	grid -	generowanie punktów w siatce, tj. wszystkie punkty mają współrzędne takie że są kolejnymi liczbami całkowitymi
	sgrid -	jak grid z tym że licza punktów do generacji jest zadana przez użytkownika
	sparse - generowanie punktów w liniach o losowych parametrach
	comb - generowanie punktów w formie grzebienia 
	diamond - generowanie siatki o ściętych krawędziach

-col	Wybór ilości kolumn w siatce [tylko dla -g grid, sgrid, comb, diamond]
-row	Wybór ilości rzędów w siatce [tylko dla -g grid, sgrid, comb, diamond]
-il	Wybór wielkości wcięcia w lewym górnym rogu siatki [tylko dla -g diamond]
-ir	Wybór wielkości wcięcia w prawym dolnym rogu siatki [tylko dla -g diamond]
-nmin	Wybór max ilości punktów w jednej linii [tylko dla -g sparse]
-nmax	Wybór min ilości punktów w jednej linii [tylko dla -g sparse]
-n	Wybór ilości punktów [tylko dla -g sgrid], lub ilości linii [tylko dla -g sparse]
-d	Wybór gęstośći punktów [tylko dla -g sgrid oraz -m 3]

-r	Wybór ilości powtórzeń, czyli ile razy będzie powtarzany eksperyment [tylko dla -m 3]
-i	Wybór ilości iteracji, czyli ile razy liczba punktów będzie powiększana [tylko dla -m 3]
-step	Wybór wielkości kroku między kolejnymi iteracjami, czyli ile zostanie dodane punktów [tylko dla -m 3]

-lines	Opcjonalna flaga, dołączenie jej spowoduje wyświetlenie podsumowania wygenerowanych linii - ile jest linii o danych rozmiarze [tylko dla -m 1, 2]
-points	Opcjonalna flaga, dołączenie jej spowoduje wyświetlenie podsumowania zbioru punktów, oraz w pliku points.txt pojawi się zbiór wszystkich wprowadzonych punktów [tylko dla -m 1, 2]
-time	Opcjonalna flaga, dołączenie jej spowoduje wyświetlenie ile czasu zajęło wykonanie każdego etapu algorytmu [tylko dla -m 1, 2]

======================================================================================================================================================
Konwencja danych wejściowych i prezentacji wyników
======================================================================================================================================================
Dane dotyczące punktów mogą zostać wprowadzone ze standardowego wejścia (dla trybu -m 1).
Powinny one mieć taką formę, że kolejne współrzędne są oddzielone za pomocą whitespace, a kolejne pary liczb to współrzędne kolejnych punktów.

Przykład:
1 	0
3.1 	8
0 	2.5
1 	1

Takie dane wygenerują następujące punkty: (1, 0), (3.1, 8), (0, 2.5), (1, 1)
Takie same punkty zostałyby wygenerowane dla następującego wejścia: 1 0 3.1 8 0 2.5 1 1
= = = = = =
Prezentacja wyników dla trybu -m 1, 2 jest taka sama i zależy w dużym stopni od tego czy program został wywołany z flagami: -lines, -points, -time.
Bez względu na obecność tych flag, zawsze są wyświetlane: ile min ruchów(linii) potrzeba aby pokryć dany zbiór punktów, oraz ile jest kombinacji, aby to wykonać takie minimalne pokrycie.

Przykład:

MinCover: 15
UniqueSolutions: 2 (2615348736000) //przed nawiasem ile jest unikalnych rozwiązań (nie biorąc pod uwagę kolejności usuwania kolejnych linii z rozwiązania)
= = = = = =
Gdyby zostałe włączone opcjonalne flagi -lines, -points, -time, mogło by to wyglądać tak:

Lines size: //-lines
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	
0	0	0	1706	432	236	20	48	36	4	4	4	4	4	4	32	
Execution time: 101 //-time (czas wykonania generacji linii)

MinCover: 15
Execution time: 16 //-time (czas znalezienia minimalnego rozwiązania)

UniqueSolutions: 2 (2615348736000)
Execution time: 743 //-time (czas znalezienia ilości rozwiązań)
= = = = = =
Wyjście dla trybu -m 3 wygląda inaczej:
Kolejno, w tej samej linii, odzielone za pomocą '\t', dla każdej iteracji wypisywane są: 
	czas wykonania generacji linii,
	czas znalezienia minimalnego pokrycia,
	ile linii pokrywa daną iteracje problemu, 
	czas znalezienia ilości unikalnych rozwiązań, 
	ile unikalnych rozwiązań znaleziono.
Newline oddziela kolejne powtórzenia problemu.

Po wykonaniu wszystkich powtórzeń wypisywane jest podsumowanie uśrednionych czasów wykonania każdego z algorytmów dla każdej z iteracji, oraz uśrednioną liczbę linii znalezionych w danej iteracji.

Przykład dla ustawień -d 0.5 -r 2 -i 8 -step 25:

0	0	7	0	5	
0	0	9	0	1	
15	0	12	0	1	
16	0	14	15	1	
32	0	16	46	2	
32	15	17	63	1	
62	47	19	415	2	
94	90	20	597	2	

0	0	7	0	43	
15	0	11	0	6	
0	16	13	0	2	
15	16	15	47	5	
31	16	16	47	1	
31	391	18	506	1	
63	522	20	2190	2	
78	641	21	2868	2	


LinesNumber: 	35	120	257	458	744	1070	1451	1895	
LineGen: 	0	7	7	15	31	31	62	86	
MinCover: 	0	0	8	8	8	203	284	365	
Unique: 	0	0	0	31	46	284	1302	1732	
======================================================================================================================================================
Opis metody rozwiązania i struktur danych
======================================================================================================================================================
Problem został podzielony na 3 zasadnicze podproblemy:
1. Odnalezienie wszystkich linii które zawierają 3 lub więcej punktów (nie ma sensu zapamiętywać tych które mają 2 lub mniej punktów, ponieważ takie linie można ułożyć między każdym z dowolnych punktów)
2. Odnalezienie minimalnej liczby linii pokrywającej wszystkie punkty
3. Odnalezienie wszystkich rozwiązań, składających się z liczby linii, która została określona przez algorytm numer 2
= = = = = =
Zostały zastosowane następujące struktury danych:
Line oraz Point
	Reprezentują linie i punkty. Każda linia trzyma listę punktów, które ta linia zawiera. Podobnie każdy punkt trzyma listę linii, kóte przecinają ten punkt.
	Dokładniej ujmując to obie te struktury trzymają iteratory na tą drugą, co jest możliwe ponieważ punkty oraz linie są trzymane w liście, której iteratory są stałe.
	Dzięki temu nie trzeba korzystać z pointerów, ani kopiować obiektów.

PlaneXY
	Trzyma lisę punktów oraz wektor list które trzymającą linie. Każdy indeks wektora odpowiada rozmiarowi danej linii (czyli ilości trzymanych przez niego punktów).
	Dzięki temu linie są zawsze posortowane według rozmiaru, co okazuje się przydatne w trakcie działania algorytmu 2 i 3.
	Dostępne są metody które "niby wyłączają" daną linie - tzn. symulują układ struktury danych tak jakby linia i wszystkie punkty które ona zawiera została usunięta.
	Możliwy jest także "splice" danych linii, co jest używane, aby przesunąć przetestowane już linie do innej struktury danych. Dzięki temu dana kombinacja linii jest sprawdzana max raz.
= = = = = =
Algorytm numer 1
	Aby móc rozważać, które linie należy wybrać, aby spełnić warunki polecenia, trzeba je najpierw znaleźć. 
	W tym celu wybieram ze zbioru punktów dwa punkty, określam na jakiej linii te dwa punkty leżą i sprawdzam czy linia o takich parametrach nie została już rozważona. (to ostanie realizowane za pomocą unordered_set)
	Jeśli taka linia rzeczywiście została już rozważona to wracam do początku algorytmu wybierając dwa kolejne punkty.
	Następnie dla wszystkich punktów za wyjątkiem tych już rozważonych, sprawdzam czy należą do rozważanej linii. Jeśli tak to dodaje punkt do linii. 
	Po sprawdzeniu wszystkich punktów dla danej linii sprawdzam, czy leżą na niej więcej niż 2 punkty. Jeśli tak to linię zapisuję i wracam do początku algorytmu. 
	Postępuję tak dopóki nie rozważę wszystkich par punktów.

Algorytm numer 2
	Przed właściwym algorytmem znajdowania minimalnego pokrycia, następuje preprocesing.
	Znajduje on punkty które nie leża na żadnej z linii znalezionych za pomocą algorytmu 1, i odejmuje znalezioną liczbę od liczby punktów dla których szukane będzie rozwiązanie.
	Znajduje on także linie, które mają co najmniej 2 punkty które są przecinane tylko przez tą linie. Taka linia może zostać usunięta z danych wejściownych do właściwego algorytmu.
	Po tych zabiegach następuje przejście do właściwej części algorytmu.
	Algorytm przyjmuje liczbę punktów (n), przypuszczalną liczbę linii (k), oraz zbiór linii wygenerowany algorytmem z pkt. 1 i poddany preprocesingowi. 
	Liczba punktów jest dana, natomiast jako parametr początkowy k podawana jest liczba ceil(n/2) - czyli tak jakbyśmy nie przewidywali żadnych linii które zawierają więcej niż 2 punkty.
	Dla każdej linii która przecina więcej niż ceil(c/k) punktów, po zasymulowaniu usunięcia tejże linii i przerzucania jej do listy przetestowanych już linii wywoływany jest rekurencyjnie ten algorytm.
	Gdy rekurencja wraca, przetestowana linia jest "włączana" (ale cały czas pozostaje w liście przetestownych) i wybierana jest kolejna linia.
	Kiedy znalezione zostaje rozwiązanie dla k linii, parametr k zostaje dekrementowany, a nowe stany są rozwijane z ostrzejszym ograniczeniem.
	Gdy nie ma już stanów które możnaby rozwinąć zwracane jest najlepsze znalezione dotychczas rozwiązanie, a jeśli takiego nie ma -1.

Algorytm numer 3
	Pomysł na algorytm do problemu numer 3 jest modyfikacją algorytmu z punktu 2. 
	Podobnie przeszukujemy w głąb bez linii które nie zawierają więcej niż n/k punktów. 
	Zmianą jest to, że parametr k jest stały (wyliczony za pomocą algorytmu numer 2), a zwracane jest nie nowe rozwiązanie, a liczba która reprezentuje ile unikalnych rozwiązań zostało znalezionych.

======================================================================================================================================================
Pliki programu
======================================================================================================================================================
//TODO

======================================================================================================================================================
Dodatkowe zalecenia
======================================================================================================================================================
//TODO