ΚΑΛΑΜΠΟΚΗΣ ΕΥΑΓΓΕΛΟΣ 1115202100045 ΕΡΙΚ ΚΑΓΙΑΤΣΚΑ 1115202100043

----------------------------------ΕΚΤΕΛΕΣΗ ΠΡΟΓΡΑΜΜΑΤΟΣ----------------------------------

1. Δημιουργία φακέλου build --> mkdir build
2. Είσοδος στον φάκελο build --> cd build
3. cmake ..
4. make
5. Εκτέλεση προγράμματος: ./main -i input_file -o output_file

Ενδεικτική εκτέλεση: ./main -i ../tests/instance_test_4.json -o ../output/output.json

----------------------------------ΛΕΠΤΟΜΕΡΕΙΕΣ ΥΛΟΠΟΙΗΣΗΣ----------------------------------

Στο αρχείο main.cpp βρίσκεται όλη η διαχείριση των Input/ output και επιλογή των μεθόδων

Στο αρχείο triangulation.hpp βρίσκονται οι 3 βασικοί αλγόριθμοι:

1. local search: ο αλγόριθμος αυτός ο οποίος είναι ίδιος με αυτόν που είχε παραδοθεί στην πρώτη εργασία στην ουσία επιλέγει όλες τις μεθόδους και στο τέλος διαλέγει να εφαρμόσει αυτή που είχε τη μεγαλύτερη βελτίωση στο cdt.
2. simulated annealing: Ο αλγόριθμος αυτός τρέχει όσο η θερμοκρασία είναι > 0 επιλέγοντας μια τυχαία μέθοδο με γνώμονα αν μειώνει την ενέργεια του ή εαν μέσω του υπολογισμού μιας πιθανότητας παραμένει μεγαλύτερη από ένα κατώφλι R.
3. ant colony optimization: Ο αλγόριθμος αυτός επιλέγει n/4 μυργμήγκια να τρέξουν στο ίδιο αντίγραφο του cdt για κάθε κύκλο καθένα πειράζοντας ένα ξεχωριστό αμβλυγώνιο τρίγωνο στο τέλος οι αλλαγές αυτές αποθηκεύονται εφόσον μειώνουν την ενέργεια και τα αμβλυγώνια τρίγωνα.

Οι επιλογές των παραμέτρων επιλέχθηκαν έπειτα από αρκετές πειραματικές προσπάθειες ώστε να ευννοούν όσο περισσότερο γίνεται τη μείωση των αμβλυγώνιων τριγώνων.

Τέλος, στο αρχείο test_results βρίσκονται φωτογραφίες της εκτέλεσης των μεθόδων καθώς και ένα excel σύγκρισης της απόδοσης τους. :)