AΛΓΟΡΙΘΜOI
ΥΠΟΧΡΕΩΤΙΚΗ ΑΤΟΜΙΚΗ ΕΡΓΑΣΙΑ
Σε μία μυρμηγκοφωλιά ζουν κόκκινα και μαύρα μυρμήγκια.
- Το σημείο που βρίσκεται το κάθε μυρμήγκι καθορίζεται από συγκεκριμένες συντεταγμένες (x, y) όπου x∈R, y∈R.
- Τα μαύρα μυρμήγκια μαζεύουν την τροφή (σπόρους) σε κά ποιες τοποθεσίες από τις οποίες τα κόκκινα την μεταφέρουν στην φωλιά.
- Τα κόκκινα μυρμήγκια είναι ίσα σε αριθμό με τα μαύρα. Τα κόκκινα μυρμήγκια έχουν Id περιττό αριθμό ενώ τα μαύρα έχουν Id ζυγό αριθμό.
- Τα κόκκινα μυρμήγκια κουβαλούν από έναν κάδο, διαφορ ετικής χωρητικότητας σπόρων.
- Τα μαύρα μυρμήγκια μαζεύουν σπόρους από πολλαπλά είδη.
- Το κάθε είδος σπόρου έχει διαφορετικό βάρος.
- Κάθε μαύρο μυρμήγκι επιλέγει όσους σπόρους θέλει, αλλά από 5 μόνο είδη. Σε κάποια χρονική στιγμή, έχουμε δεδομένα της ακόλουθης μορφής για όλα τα μυρμήγκια
Id Συντεταγμένες x y Λοιπές Πληροφορίες
1 0.123 0.876 1567 (χωρητικότητα κάδου, ακέραιος)
2 0.821 0.526 12 14 34 46 24 (βάρος κάθε είδος σπόρου, ακέραιοι)
3 0.345 0.653 1002 (χωρητικότητα κάδου, ακέραιος)
4 0.812 0.913 42 44 24 26 14 (βάρος κάθε είδος σπόρου, ακέραιοι)
...
Πρέπει να υλοποιηθεί ένα πρόγραμμα που να εκτελεί τις ακόλουθες ανεξάρτητες λειτουργίες:
ΛΕΙΤΟΥΡΓΙΑ Α: Τα μυρμήγκια αποφασίζουν να μην κουνηθούν από τη θέση τους ξανά, πριν αποφασίσουν ποιο είναι το συντομότερο δίκτυο μονοπατιών (Minimum Spanning Tree) που θα ενώνει όλα τα μυρμήγκια. Βρείτε το εφαρμόζοντας αποδοτικά τον αλγόριθμο Kruskal+ Union find οι αποστάσεις να είναι Ευκλείδειες).
ΛΕΙΤΟΥΡΓΙΑ B: Τα κόκκινα μυρμήγκια πρέπει να δημιουργήσουν ζεύγη με τα μαύρα, ώστε να βάλουν στους κάδους τους σπόρους. Τα μυρμήγκια προτιμούν να δημιουργήσουν ζεύγη με το κοντινότερο μυρμήγκι άλλου χρώματος. Να δημιουργήσετε ζεύγη μυρμηγκιών εφαρμόζοντας αποδοτικά τον αλγόριθμο ευσταθούς ταιριάσματος (Gale Shapley), με την προϋπόθεση ότι τις προτάσεις τις κάνουν τα κόκκινα μυρμήγκια οι αποστάσεις να είναι Ευκλείδειες).
ΛΕΙΤΟΥΡΓΙΑ Γ: Έστω το ζεύγος στο οποίο συμμετέχει το 1ο κόκκινο μυρμήγκι (id = 1) και το 1 ο μαύρο μυρμήγκι (id = 2). Το κόκκινο μυρμήγκι θέλει να ελέγξει αν μπορεί να γεμίσει ΠΛΗΡΩΣ τον κάδο του, με όσο το δυνατόν λιγότερους σπόρους που του δίνει το μαύρο. Ελέγξτε αν υπάρχει τέτοιος τρόπος και ποιος για όλα τα ζευγάρια (με τη σειρά που εμφανίζονται στα δεδομένα εισόδου), με χρήση αποδοτικού αλγορίθμου δυναμικού προγραμματισμού. Το πρόβλημα είναι αντίστοιχο με αυτό της ανταλλαγής ρέστων.
Παρατηρήσεις σχετικά με τον τρόπο υλοποίησης:
- Η είσοδος των δεδομένων θα γίνεται από ένα αρχείο κειμένου txt που θα έχει την παραπάνω μορφή, δηλαδή:
1 0.123 0.876 1567
2 0.821 0.526 12 14 34 46 24
3 0.345 0.653 1002
4 0.812 0.913 42 44 24 26 14
...
Τα δεδομένα μπορεί να χωρίζονται με κενά ή tabs. Το όνομα του αρχείου αυτού θα πρέπει να δίνεται ως το μοναδικό όρισμα στο εκτελέσιμο αρχείο jar του κώδικά σας κατά την εκτέλεσή του από την command lineline (προσοχή: πρέπει να διαβάζεται απευθείας από τον ίδιο φάκελο του jar και να μην χρειάζεται path, π.χ. data.txt)
- Η έξοδος των αποτελεσμάτων για την λειτουργία Α θα γίνεται σε αρχείο txt όπου στην πρώτη γραμμή θα έχει το συνολικό βάρος του MSTMST ενώ στις επόμενες γραμμές του θα έχει τα ζεύγη των Ids των μυρμηγκιών που σχηματίζουν τις ακμές (με το μικρότερο Id να αναγράφεται πρώτο) και κατόπιν ως προς το δεύτερο, π.χ.
1422.654
1 4
2 7
2 12
3 5
...
Τα Ids πρέπει να χωρίζονται με κενά ή tabs. Το αρχείο αυτό θα πρέπει να αποθηκεύεται στον ίδιο φάκελο όπως πριν (χωρίς path).
- Η έξοδος των αποτελεσμάτων για την λειτουργία Β θα γίνεται σε αρχείο txt όπου στις γραμμές του θα έχει τα τελικά ζεύγη των Ids (περιττός και άρτιοε) των μυρμηγκιών του ευσταθούς ταιριάσματος ταξινομημένα ως προς το πρώτο Id , π.χ.
1 8
3 6
5 4
...
Σα Ids πρέπει να χωρίζονται με κενά ή tabs. Το αρχείο αυτό θα πρέπει να αποθηκεύεται στον ίδιο φάκελο όπως πριν (χωρίς path).
- Η έξοδος των αποτελεσμάτων για την λειτουργία Γ θα γίνεται σε αρχείο txt όπου στις γραμμές του θα έχει μόνο τα ζεύγη των Ids (περιττός και άρτιος) των μυρμηγκιών στα οποία επιτυγχάνεται πλήρες γέμισμα, ταξινομημένα ως προς το πρώτο Id, και θα ακολουθούν 5 ακέραιοι που θα εκφράζουν πόσες φορές χρησιμοποιήθηκε ο κάθε αντίστοιχος σπόρος, π.χ.
5 6 1 4 0 31 17
11 12 0 0 11 24 3
...
Σα Ids πρέπει να χωρίζονται με κενά ή tabs. Το αρχείο αυτό θα πρέπει να αποθηκεύεται στον ίδιο φάκελο όπως πριν (χωρίς path).
-
Το πρόγραμμα από τη στιγμή που θα δεχθεί τα δεδομένα της εισόδου θα πρέπει να εκτελέσει τις λειτουργίες Α,Β,Γ και να παράγει τα αποτελέσματα.
-
Να χρησιμοποιήσετε Java 1.8
-
Ο πηγαίος κώδικας πρέπει να έχει συνοπτικά σχόλια μέσα στον κώδικα (inline) όπου είναι απαραίτητο, και εκτενή σχόλια επάνω από κάθε συνάρτηση, τα οποία να εξηγούν το σκεπτικό της υλοποίησής σας.