Κ23γ: Ανάπτυξη Λογισμικού για Αλγοριθμικά Προβλήματα

Χειμερινό εξάμηνο 2022-23

• Σακαρέλλος Ιωάννης (sdi1800167)
• Μασούρας Νικόλαος (sdi1800112)

3^η Προγραμματιστική Εργασία

Περιγραφή εργασίας

Βελτιστοποίηση πολυγωνοποίησης σημειοσυνόλου βέλτιστης επιφάνειας, ανάπτυξη εφαρμογής για τη συγκριτική αξιολόγηση των αλγορίθμων πολυγωνοποίησης και διαγωνισμός

Η εφαρμογή παίρνει ως είσοδο έναν φάκελο με αρχεία σημειοσυνόλων. Για κάθε αρχείο δοκιμάζει συνδυασμόυς αλγορίθμων που υλοποιήσαμε για τις δύο πρώτες εργασίες του μαθήματος. Για κάθε δυνατό συνδυασμό υπολογίζει τα scores και bounds, όπως αυτά ζητούνται στην εκφώνηση. Στο τέλος, επιστρέφεται (σε αρχείο εξόδου, το όνομα του οποίου δίνεται επίσης ως όρισμα στην εφαρμογή) ένας πίνακας με τα αποτελέσματα των δοκιμών. Συγκεκριμένα, αποτελέσματα δοκιμών για αρχεία ίδιου μεγέθους (σε σημεία) συνυπολογίζονται σε μία γραμμή του τελικού πίνακα. Για τις δοκιμές της εφαρμογής, χρησιμοποιούνται απο προεπιλογή οι εξής τιμές:

• L = 10
• THRESHOLD = 0.1

Οι τιμές αυτές μπορούν να αλλάξουν από το αρχείο main/main.cpp, στις γραμμές 12 και 13 αντίστοιχα.

Οδηγίες μεταγλώττισης

Όπως και στις πρώτες δύο Εργασίες, για την παραγωγή του εκτελέσιμου αρχείου evaluate, ακολουθούμε τα εξής βήματα:

• Μεταβαίνουμε στον φάκελο build
• Δίνουμε την εντολή cmake .. -DCMAKE_BUILD_TYPE=Release
• Δίνουμε την εντολή make
• Μεταβαίνουμε στον φάκελο main που δημιουργήθηκε
• Εκτελούμε το τελικό εκτελέσιμο αρχείο με την εντολή ./evaluate ακολουθούμενη από τα κατάλληλα ορίσματα

Οδηγίες χρήσης

Η εκτέλεση του προγράμματος γίνεται μέσω της εντολής $./evaluate -i <input_files_directory> -o <output_file>, όπου:

• Το <input_file_directory> είναι το όνομα του φακέλου που περιέχει τα αρχεία εισόδου
• Το <output_file> είναι το όνομα του αρχείου στο ποίο θα γραφούν τα δεδομένα εξόδου. Προσοχή: Το αρχείο <output_file> δεν πρέπει να υπάρχει ήδη

Περιγραφή αρχείων κώδικα

Βιβλιοθήκη arguments (Παρόμοια με προηγούμενες Εργασίες)

Η βιβλιοθήκη arguments αποτελείται από τα αρχεία arguments.cpp και arguments.hpp. Υλοποιεί την κλάση arguments, που διαβάζει, επαληθεύει και αποθηκεύει τα σημεία που δίνονται από κάθε αρχείο εισόδου σε κατάλληλες δομές, όπως και στις πρώτες δύο Εργασίες του μαθήματος.

Βιβλιοθήκη polyline (Παρόμοια με προηγούμενες Εργασίες)

Η βιβλιοθήκη polyline αποτελείται από τα αρχεία polyline.cpp και polyline.hpp. Υλοποιεί την κλάση polyline, μέσω της οποίας γίνεται η κατασκευή της αρχικής πολυγωνικής γραμμής, όπως και στις πρώτες δύο Εργασίες του μαθήματος.

Βιβλιοθήκη optimization (Παρόμοια με 2^η Εργασία)

Η βιβλιοθήκη optimization αποτελείται από τα αρχεία optimization.hpp και optimization.cpp. Υλοποιεί την κλάση optimization, μέσω της οποίας μεγιστοποιείται ή ελαχιστοποιείται το εμβαδόν του πολυγώνου, όπως και στην 2^η Εργασία του μαθήματος.

Σχολιασμός αποτελεσμάτων

Δίνοντας στην εφαρμογή μας ως είσοδο τα εξής αρχεία:

euro-night-0000010.instance
euro-night-0000020.instance
euro-night-0000060.instance
euro-night-0000300.instance
stars-0000090.instance
uniform-0000010-1.instance
uniform-0000040-1.instance
uniform-0000050-1.instance
uniform-0000100-1.instance
us-night-0000030.instance
us-night-0000070.instance
us-night-0000080.instance

Παίρνουμε τα εξής αποτελέσματα:

      ||                  local_search                 ||              simulated_annealing              ||
======||===============================================||===============================================||
 size || min score | max score | min bound | max bound || min score | max score | min bound | max bound ||
======||===============================================||===============================================||
10    ||0.481469   |1.63996    |0.847317   |0.092998   ||0.671886   |1.71246    |0.865146   |0.283415   ||
20    ||0.288586   |0.648327   |0.648327   |0.288586   ||0.288586   |0.673579   |0.673579   |0.288586   ||
30    ||0.270626   |0.819203   |0.819203   |0.270626   ||0.270626   |0.819203   |0.819203   |0.270626   ||
40    ||0.32684    |0.766232   |0.766232   |0.32684    ||0.32684    |0.766232   |0.766232   |0.32684    ||
50    ||0.21569    |0.781251   |0.781251   |0.21569    ||0.21569    |0.781251   |0.781251   |0.21569    ||
60    ||0.238279   |0.824618   |0.824618   |0.238279   ||0.238279   |0.824618   |0.824618   |0.238279   ||
70    ||0.211207   |0.721921   |0.721921   |0.211207   ||0.211207   |0.721921   |0.721921   |0.211207   ||
80    ||0.175371   |0.887823   |0.887823   |0.175371   ||0.175371   |0.887823   |0.887823   |0.175371   ||
90    ||0.309915   |0.727112   |0.727112   |0.309915   ||0.309915   |0.727112   |0.727112   |0.309915   ||
100   ||0.308851   |0.713752   |0.713752   |0.308851   ||0.308851   |0.713752   |0.713752   |0.308851   ||
300   ||0.221185   |0.744483   |0.744483   |0.221185   ||0.221185   |0.744483   |0.744483   |0.221185   ||

Καθώς οι στήλες min score και max score είναι αθροίσματα αποτελεσμάτων και όχι μέσοι όροι, οι τιμές τους κάποιες φορές υπερβαίνουν τη μονάδα.