Κ23γ: Ανάπτυξη Λογισμικού για Αλγοριθμικά Προβλήματα Χειμερινό εξάμηνο 2022-23
1η Προγραμματιστική Εργασία Πολυγωνοποίηση σημειοσυνόλου με τη χρήση της βιβλιοθήκης CGAL (C++)
Παναγιώτης Κοντοειδής 1115201900266 Στέλιος Δημητριάδης 1115201900050
Σκοπός της εργασίας είναι η πολυγωνοποίηση σημειων στον χώρο με δυο διαφορετικους αλγορίθμους τον Αυξητικό και τον αλγοριθμο που βασιζεται στο ΚΠ.
Αρχεία που περιλαμβάνονται είναι τα:
Polygon_functions.cpp Polygon_functions.hpp PROJECT.cpp CMakeLists.txt .git
Οδηγίες μεταγλώττισης του προγράμματος:
-
cmake -DCGAL_DIR=$CMAKE_INSTALLED_PREFIX/lib/CGAL -DCMAKE_BUILD_TYPE=Release .
-
make
-
./PROJECT -i input.txt -o output.txt -algorithm (choose incremental or convex_hull) -edge selection (choose 1 2 3 1=random 2=min 3=max) (this option exists if you choose incremental algorithm)-initialization (choose 1a 1b 2a 2b 1a=sort by x in increasing order,1b=sort by x in decreasing order,2a sort by y in increasing order,2b sort by y in decreasing order)
Στους παρακάτω πίνακες αναφέρονται οι μέσοι χρόνοι εκτέλεσης των δοθείσων παραδειγμάτων. Οι μέσοι χρόνοι προέκυψαν από την επαναλαμβανόμενη εκτέλεση των αλγορίθμων.
Τα συμπεράσματα που προκύπτουν από αυτούς είναι ότι, στον αυξητικό αλγόριθμο ο μέσος χρόνος της τυχαίας επιλογής ορατής ακμής μπορεί να είναι ο βέλτιστος σε μερικές περιπτώσεις. Κατά κύριο λόγο κυμαίνεται ανάμεσα από τις τιμές της επιλογής ορατής ακμής για ελάχιστο εμβαδόν(min) και τις τιμές της επιλογής ορατής ακμής για το μέγιστο εμβαδόν(max), το οποίο οφείλεται στο μεγάλο εύρος χρόνων εκτέλεσης του αλγορίθμου με την τυχαία επιλογή, κατά την δειγματοληψία. Οι τιμές των χρόνων εκτέλεσης για min/max επιλογή ορατών ακμών διακυμένονται ανάλογα το αρχείο που εξετάζεται κάθε φορά και μπορεί σε μερικές περιπτώσεις να διαφέρουν κατά πολύ.
Όσον αφορά την αρχικοποίηση του αυξητικού αλγορίθμου βλέπουμε ότι η ταξινόμηση των στοιχείων κατά αύξουσα σειρά τεμνημένων (1b) έχει τους βέλτιστους χρόνους εκτέλεσης σε πολλά παραδείγματα. Τον χείριστο χρόνο εκτέλεσης φαίνεται ότι έχει ταξινόμηση των στοιχείων κατά φθίνουσα σειρά τεταγμένων (2a).
Τα συμπεράσματα που προκύπτουν για τον αλγόριθμο με βαση το ΚΠ είναι ότι για τυχαία επιλογή ορατής ακμης ο χρονος εκτελεσης του σε όλα τα αρχεία είναι μικρότερος από αυτόν της επιλογής ακμης min/max. Παράλληλα, κατά την επιλογη min και max οι χρόνοι είναι παρόμοιοι δεν διαφέρουν κατα πολύ και όσο ο αριθμός των δοθέντων σημείων αυξάνεται τόσο και ο χρόνος εκτέλεσης του αλγορίθμου αυξάνεται ραγδαία. Για παράδειγμα, με τυχαία επιλογή ορατής ακμής σε αρχείο με 600 σημεία ο χρόνος εκτέλεσης είναι 9.54 sec ενω για 1000 ειναι 58.31, 6 φορες περισσότερος, ενω για min/max ειναι 8 φορες περισσότερος. Για 2000 σημεία ο ενδεικτικός χρόνος εκτέλεσης είναι περίπου 10 λεπτά και επομένως ο χρόνος εκτέλεσης αυξάνεται κατα πολυ για μεγάλο αριθμό σημείων. Επιπρόσθετα, οι χρόνοι εκτέλεσης στα αρχεία με ομοιόμορφη κατανομή σημείων(uniform) είναι σχετικά μεγαλύτεροι από τα αρχεία με δειγματοληψία εικόνων (images), σε αντίστοιχο αριθμό σημείων.
Τέλος, συγκρίνοντας τους δύο αλγορίθμους παρατηρείται ότι ο αυξητικός αλγόριθμος παρόλο που έχει μεγαλύτερο μέσο χρόνο εκτέλεσης σε αρχεία με μικρό αριθμό σημείων, έχει σημαντικά μικρότερο χρόνο εκτέλεσης σε αρχεία με μεγάλο αριθμό σημείων από ότι ο αλγόριθμος με βάση το ΚΠ.
Αλγόριθμος: Αυξητικός
File: uniform-0000090-1.instance
Random
Min
Max
1a
0.28
0.29
0.31
1b
0.308
0.28
0.45
2a
0.28
0.28
0.33
2b
0.28
0.28
0.46
File: uniform-0000300-1.instance
Random
Min
Max
1a
4.33
3.56
5.07
1b
3.38
2.62
3.18
2a
3.91
3.3
4.2
2b
3.76
3.82
3.5
File: uniform-0001000-1.instance
Random
Min
Max
1a
91.2
80.11
97.3
1b
90.5
87.5
94.5
2a
95.2
84.1
93.2
2b
89.4
72.3
103.6
File: euro-night-0000090.instance
Random
Min
Max
1a
0.28
0.20
0.32
1b
0.18
0.24
0.31
2a
0.31
0.37
0.39
2b
0.28
0.34
0.28
File: euro-night-0000300.instance
Random
Min
Max
1a
3.5
3.51
3.89
1b
3.67
5.05
3.95
2a
4.31
3.69
4.05
2b
3.81
5.69
4.51
File: euro-night-0001000.instance
Random
Min
Max
1a
104.67
115.68
125.6
1b
89.37
120.59
115.65
2a
133.59
110.12
123.65
2b
110.15
76.16
100.64
Αλγόριθμος : Με βάση το ΚΠ
FILE: uniform-0000090-1.instance uniform-0000300-1.instance uniform-0000600-1.instance uniform-0001000-1.instance RANDOM 0.021 0.80 9.54 58.31 MIN 0.041 2.01 24.46 198.90 MAX 0.035 2.10 24.973 195.76
FILE: euro-night-0000090.instance euro-night-0000300.instance euro-night-0000600.instance euro-night-0001000.instance RANDOM 0.022 0.76 9.48 53.50 MIN 0.042 2.193 25.97 167.13 MAX 0.042 2.015 25.86
Κ23γ: Ανάπτυξη Λογισμικού για Αλγοριθμικά Προβλήματα Χειμερινό εξάμηνο 2022-23
1η Προγραμματιστική Εργασία Πολυγωνοποίηση σημειοσυνόλου με τη χρήση της βιβλιοθήκης CGAL (C++)
Παναγιώτης Κοντοειδής 1115201900266 Στέλιος Δημητριάδης 1115201900050
Σκοπός της εργασίας είναι η πολυγωνοποίηση σημειων στον χώρο με δυο διαφορετικους αλγορίθμους τον Αυξητικό και τον αλγοριθμο που βασιζεται στο ΚΠ.
Αρχεία που περιλαμβάνονται είναι τα:
Polygon_functions.cpp Polygon_functions.hpp PROJECT.cpp CMakeLists.txt .git
Οδηγίες μεταγλώττισης του προγράμματος:
-
cmake -DCGAL_DIR=$CMAKE_INSTALLED_PREFIX/lib/CGAL -DCMAKE_BUILD_TYPE=Release .
-
make
-
./PROJECT -i input.txt -o output.txt -algorithm (choose incremental or convex_hull) -edge selection (choose 1 2 3 1=random 2=min 3=max) (this option exists if you choose incremental algorithm)-initialization (choose 1a 1b 2a 2b 1a=sort by x in increasing order,1b=sort by x in decreasing order,2a sort by y in increasing order,2b sort by y in decreasing order)
Στους παρακάτω πίνακες αναφέρονται οι μέσοι χρόνοι εκτέλεσης των δοθείσων παραδειγμάτων. Οι μέσοι χρόνοι προέκυψαν από την επαναλαμβανόμενη εκτέλεση των αλγορίθμων.
Τα συμπεράσματα που προκύπτουν από αυτούς είναι ότι, στον αυξητικό αλγόριθμο ο μέσος χρόνος της τυχαίας επιλογής ορατής ακμής μπορεί να είναι ο βέλτιστος σε μερικές περιπτώσεις. Κατά κύριο λόγο κυμαίνεται ανάμεσα από τις τιμές της επιλογής ορατής ακμής για ελάχιστο εμβαδόν(min) και τις τιμές της επιλογής ορατής ακμής για το μέγιστο εμβαδόν(max), το οποίο οφείλεται στο μεγάλο εύρος χρόνων εκτέλεσης του αλγορίθμου με την τυχαία επιλογή, κατά την δειγματοληψία. Οι τιμές των χρόνων εκτέλεσης για min/max επιλογή ορατών ακμών διακυμένονται ανάλογα το αρχείο που εξετάζεται κάθε φορά και μπορεί σε μερικές περιπτώσεις να διαφέρουν κατά πολύ.
Όσον αφορά την αρχικοποίηση του αυξητικού αλγορίθμου βλέπουμε ότι η ταξινόμηση των στοιχείων κατά αύξουσα σειρά τεμνημένων (1b) έχει τους βέλτιστους χρόνους εκτέλεσης σε πολλά παραδείγματα. Τον χείριστο χρόνο εκτέλεσης φαίνεται ότι έχει ταξινόμηση των στοιχείων κατά φθίνουσα σειρά τεταγμένων (2a).
Τα συμπεράσματα που προκύπτουν για τον αλγόριθμο με βαση το ΚΠ είναι ότι για τυχαία επιλογή ορατής ακμης ο χρονος εκτελεσης του σε όλα τα αρχεία είναι μικρότερος από αυτόν της επιλογής ακμης min/max. Παράλληλα, κατά την επιλογη min και max οι χρόνοι είναι παρόμοιοι δεν διαφέρουν κατα πολύ και όσο ο αριθμός των δοθέντων σημείων αυξάνεται τόσο και ο χρόνος εκτέλεσης του αλγορίθμου αυξάνεται ραγδαία. Για παράδειγμα, με τυχαία επιλογή ορατής ακμής σε αρχείο με 600 σημεία ο χρόνος εκτέλεσης είναι 9.54 sec ενω για 1000 ειναι 58.31, 6 φορες περισσότερος, ενω για min/max ειναι 8 φορες περισσότερος. Για 2000 σημεία ο ενδεικτικός χρόνος εκτέλεσης είναι περίπου 10 λεπτά και επομένως ο χρόνος εκτέλεσης αυξάνεται κατα πολυ για μεγάλο αριθμό σημείων. Επιπρόσθετα, οι χρόνοι εκτέλεσης στα αρχεία με ομοιόμορφη κατανομή σημείων(uniform) είναι σχετικά μεγαλύτεροι από τα αρχεία με δειγματοληψία εικόνων (images), σε αντίστοιχο αριθμό σημείων.
Τέλος, συγκρίνοντας τους δύο αλγορίθμους παρατηρείται ότι ο αυξητικός αλγόριθμος παρόλο που έχει μεγαλύτερο μέσο χρόνο εκτέλεσης σε αρχεία με μικρό αριθμό σημείων, έχει σημαντικά μικρότερο χρόνο εκτέλεσης σε αρχεία με μεγάλο αριθμό σημείων από ότι ο αλγόριθμος με βάση το ΚΠ.
Αλγόριθμος: Αυξητικός
File: uniform-0000090-1.instance
Random
Min
Max
1a
0.28
0.29
0.31
1b
0.308
0.28
0.45
2a
0.28
0.28
0.33
2b
0.28
0.28
0.46
File: uniform-0000300-1.instance
Random
Min
Max
1a
4.33
3.56
5.07
1b
3.38
2.62
3.18
2a
3.91
3.3
4.2
2b
3.76
3.82
3.5
File: uniform-0001000-1.instance
Random
Min
Max
1a
91.2
80.11
97.3
1b
90.5
87.5
94.5
2a
95.2
84.1
93.2
2b
89.4
72.3
103.6
File: euro-night-0000090.instance
Random
Min
Max
1a
0.28
0.20
0.32
1b
0.18
0.24
0.31
2a
0.31
0.37
0.39
2b
0.28
0.34
0.28
File: euro-night-0000300.instance
Random
Min
Max
1a
3.5
3.51
3.89
1b
3.67
5.05
3.95
2a
4.31
3.69
4.05
2b
3.81
5.69
4.51
File: euro-night-0001000.instance
Random
Min
Max
1a
104.67
115.68
125.6
1b
89.37
120.59
115.65
2a
133.59
110.12
123.65
2b
110.15
76.16
100.64
Αλγόριθμος : Με βάση το ΚΠ
FILE: uniform-0000090-1.instance uniform-0000300-1.instance uniform-0000600-1.instance uniform-0001000-1.instance RANDOM 0.021 0.80 9.54 58.31 MIN 0.041 2.01 24.46 198.90 MAX 0.035 2.10 24.973 195.76
FILE: euro-night-0000090.instance euro-night-0000300.instance euro-night-0000600.instance euro-night-0001000.instance RANDOM 0.022 0.76 9.48 53.50 MIN 0.042 2.193 25.97 167.13 MAX 0.042 2.015 25.86 181.59