krzynkrzyn / aal_2019_01_15 Goto Github PK
View Code? Open in Web Editor NEWAlgorithm complexity analysis project
Algorithm complexity analysis project
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
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.