5james/tower-of-cubes

University project for Analisys of Algorithms subject.

//ENG Brief README

This project is about creating the highest possible tower of cubes. Here are some rules about cubes and how the tower should look like:

• Each Cube's faces are varicoloured (This means that number of colours avaible are minimum 6)
• Each Cube has specified weight
• If you want to put cube A on top of cube B -> cube B must be heavier or the same weight as cube A AND colour of top of cube B must be the same as colout of bottom of cube A

The idea to solve this problem will be in documentation.

//PL Dokładny README

1. Dane studenta: Jakub Guzek Semestr: 15Z

2. Specyfikacja problemu: Danych jest N kolorowych sześcianów, z których każdy ma inną wagę. Sześciany są niejednokolorowe (każda ściana ma inny kolor). Zadanie polega na zbudowaniu za pomocą sześcianów możliwie najwyższą wieżę spełniającą warunki:

Nie można położyć cięższego sześcianu na lżejszym Dolna ściana sześcianu musi mieć taki sam kolor jak górna innego, który jest poniżej

Dane wejściowe – zestawy kolekcji sześcianów (każdy sześcian ma podane na wejściu kolory ścianek)

Wynik – liczba sześcianów najwyższej wieży, oraz ich konfiguracja ścianek.

3. Aktywacja programu: Program nie ma argumentów / parametrów wejściowych (argc, argv)

Po włączeniu programu zgodnie z poleceniem: wczytuje plik i wykonuje algorytmy generacja losowych grafow oraz wykonanie wszysystkich algorytmow Dane wejściowe: N sześcianów(int), M kolorów(int), W maxymalna waga(int) generacja wielu grafow oraz ich wykonanie + porownanie w tabelce Dane wejściowe: wybór algorytmu 1 lub 2 lub 3

4. Struktory danych: a) Node Cały program ma rozwiązywać problem wieży sześcianów. Każdy sześcian rozszepia się na 6 NODE. Node więc reprezentuje ścianę. Każdy ma swój kolor, przeciwną ścianę oraz id (numer sześcianu). Z sześcianem jest przypisywana również waga. Każdy Node (już niezależnie od sześcianów) ma swoich sąsiadów po kolorach oraz najbliższych po rozpięciu sześcianu. b) SimpleNodesTree Użyty w GraphBFSTree. Jest to węzeł w drzewie. Posiada informacje o id sześcianu; kolorze, który jest na dnie. Posiada też informacje bezpośrednio związane z drzewem - rodzic oraz vector dzieci. c)std::pair wielokrotnie wykorzystywana struktura po to, aby m.in. przechowywać jednocześnie kolor i id, Node* i coś jeszcze

5. Algorytmy:

a. BFS Tree Jest to moja inwencja. BFS Miałaby ona działać na takiej zasadzie, że buduję drzewo (w atrybucie ma ID sześcianu): 0. Tworzę roota, który jest najcięższym ze wszystkich danych sześcianów

1. Dodaję do liści wszystkie możliwe sąsiedztwa (sześciany), możliwe - z listy sąsiadów wierzchołków należących do sześcianu wybieram tylko tych, które się nie powtórzyły w drodze do roota - np. jeśli id roota to 2 oraz mam liść sześcianu o id 3 i w jego sąsiadach jest 2 to nie mogę go już dodać. Nie trzeba dodawać, że musi się zgadzać pod względem koloru oraz, że musi być lżejszy.
2. Powtarzamy pkt 1 aż do wyczerpania. Najdłuższa droga od sześcianu końcowego (liścia) do roota to nasza wieża. Niestety z moich kalkulacji algorytm ten ma dużo za dużą złożoność obliczeniową przy małej ilości kolorów. Na przykład jeśli mamy 100 takich samych sześcianów, to root będzie miał 100 dzieci -> 100 dzieci będzie miało 99 itd. Co nie wróży nic dobrego. Za to przy dużej ilości kolorów w porównaniu do sześcianów daję dokładny wynik w miarę szybko. Algorytm jest rozpoczynany z nodów, które są najcięższe. Wadą takiego rozwiązania jest to, że przy małej ich liczbie oraz przy ogromnej liczbie kolorów może się okazać, że zwróci nienajlepszy wynik. Korzyść takiego rozwiązania to oczywiście cenny czas. Myślę, że ruszanie z najcięższych nodów jest optymalne dla tego rozwiązania. b. DFS (Depth First Search) Nie wystarczy tutaj zwykły Depth First Search. Będzie trzeba wprowadzić trochę zmian. Jak w zwykłym Depth First Search tworzymy STOS. Stos ten jednak nie będzie dotyczył wierzchołków, jakie przeszliśmy, lecz id sześcianów, przez które przeszliśmy. Chodzimy po wierzchołkach i nie możemy wejść w wierzchołek, który należy do sześcianu, który jest na stosie-1. Napisałem na stosie-1, gdyż możemy chodzić po wierzchołkach sześcianu, który jest na szczycie stosu. Jest to logiczne, gdyż możemy wtedy wyjść ze wszystkich wierzchołków (kolorów-ścian) tego sześcianu. Na bieżąco zapisujemy sobie maksymalny rozmiar stosu, jaki był oraz do tej liczby listę wskaźników do wierzchołków, której dotyczy ten maksymalny rozmiar. W ten sposób po skończeniu działania algorytmu mamy gotowe rozwiązanie – najwyższą wieżę sześcianów. Oprócz wskaźników zapamiętuje się, która ściana jest zwrócona ku dołowi. Algorytm jest rozpoczynany z nodów, które są najcięższe. Wadą takiego rozwiązania jest to, że przy małej ich liczbie oraz przy ogromnej liczbie kolorów może się okazać, że zwróci nienajlepszy wynik. Korzyść takiego rozwiązania to oczywiście cenny czas. Myślę, że ruszanie z najcięższych nodów jest optymalne dla tego rozwiązania.

c. Random walking Jest to przykład błądzenia losowego. Chodzimy po wierzchołkach i zapisujemy sobie id wszystkich przejrzanych sześcianów, tak aby nie móc przejść do przejrzanego już sześcianu. Dodatkowo zapamiętujemy kolory. Pierwszy node, do którego wchodzimy z danego id sześcianu zawiera pożądany kolor. Wybór wierzchołka-sąsiada, do którego przechodzimy jest kompletnie losowy. Lista sąsiadów jest na nowo aktualizowana i zapisywana, czyli usuwane są wierzchołki, które należą do sześcianów, które zostały przejrzane. Zapisywana jest do tymczasowej listy lub vectora. Robi się to, aby się upewnić, że jest jakiś sąsiad, do którego można przejść. Jeśli takowego nie ma to kończy się algorytm. Działanie tego algorytmu przeważnie nie da się przewidzieć. Tak więc wynik tego algorytmu może wypaść od bardzo słabego do bardzo dobrego, a nawet najlepszego rozwiązania.

6. Pliki źródłowe + wygenerowane dane: data.txt - wygenerowane dane potrzebne do 1szej opcji wywolania programu declarations.h - ogólne deklaracje dla całej aplikacji Generator.h, Generator.cpp - nagłówek i implementacja generatora danych. Zapisuje to na data.txt Graph.h, Graph.cpp - Podstawowy graf, generacja, wypis wierzchołków bez implementacji solve() GraphBFSTree.h, GraphBFSTree.cpp - Implementacja algorytmu BFS GraphDFS.h, GraphDFS.cpp - Implementacja algorytmu DFS GraphRandomWalking.h, GraphRandomWalking.cpp - Implementacja algorytmu random walking main.cpp - główny plik Node.h, Node.cpp - Struktura danych - NODE Table.h, Table,cpp - klasa do porównywania wyników Singleton