Εισαγωγή στους Αλγόριθμους — Φεβρουάριος 2023 — Θέμα 6 (απόσπασμα)¶
Μεταγραφή από το image.png.
image.png¶
ΘΕΜΑ 6
Ο Δήμος μιας πόλης θέλει να εγκαταστήσει κολώνες φωτισμού κατά μήκος ενός νέου δρόμου που έχει πρόσφατα κατασκευάσει, σε συγκεκριμένες θέσεις επί των πεζοδρομίων που έχουν υποδειχθεί από τους κατοίκους. Για λόγους εξοικονόμησης κόστους, ο Δήμος έχει αποφασίσει ότι δεν θα τοποθετήσει κολώνες σε δύο διαδοχικές τέτοιες θέσεις, αλλά σε ένα υποσύνολο μη διαδοχικών θέσεων οι οποίες θα εξασφαλίζουν τη συνολικά μέγιστη δυνατή φωτεινότητα. Μοντελοποιώντας γραφο-θεωρητικά το πρόβλημα, προκύπτει ένα μη κατευθυνόμενο γράφημα \(\Gamma = (K, A)\), όπου \(K = \{x_1, \dots, x_n\}\) είναι ένα σύνολο \(n\) κορυφών (μία για κάθε δυνητική θέση τοποθέτησης κολώνας), \(A = \{(x_i, x_{i+1}) : 1 \le i < n\}\) ένα σύνολο ακμών, και κάθε κορυφή \(x_i\) συσχετίζεται με την φωτεινότητα \(\varphi_i\) που εξασφαλίζεται από τη συγκεκριμένη θέση. Ένα υποσύνολο κορυφών ονομάζεται ανεξάρτητο αν οποιεσδήποτε δύο κορυφές του \(\Pi\) δεν συνδέονται με ακμή, και ονομάζεται μέγιστο ανεξάρτητο υποσύνολο αν αποφέρει τη μέγιστη συνολικά φωτεινότητα μεταξύ όλων των υποσυνόλων του \(K\). Στόχος λοιπόν είναι να βρεθεί το μέγιστο ανεξάρτητο υποσύνολο, αφού η εξοικονόμηση κόστους δεν επιτρέπει την τοποθέτηση κολώνων φωτισμού σε δύο διαδοχικές θέσεις, δηλαδή σε δύο γειτονικές κορυφές του \(\Gamma\). Θεωρήστε, για παράδειγμα, το παρακάτω στιγμιότυπο 7 κορυφών
[Σχήμα: 7 κορυφές σε ευθεία \(x_1\) έως \(x_7\): \(x_1\): 8, \(x_2\): 40, \(x_3\): 20, \(x_4\): 16, \(x_5\): 32, \(x_6\): 36, \(x_7\): 24]
στο οποίο οι αριθμοί εντός των κορυφών συμβολίζουν τη φωτεινότητα. Τα υποσύνολα \(\Pi_1 = \{x_1, x_3, x_5, x_7\}\), και \(\Pi_4 = \{x_1, x_4, x_7\}\) είναι ανεξάρτητα με συνολική φωτεινότητα 84 και 48, αντίστοιχα.
Θεωρήστε τον εξής άπληστο αλγόριθμο επίλυσης του παραπάνω προβλήματος: επιλέγει το υποσύνολο κορυφών με περιττούς δείκτες και το υποσύνολο κορυφών με άρτιους δείκτες, και επιστρέφει ως λύση εκείνο το υποσύνολο με τη συνολικά μέγιστη φωτεινότητα.
(α) Ποια είναι η τιμή της συνολικής φωτεινότητας που επιστρέφει ο άπληστος αλγόριθμος στο παραπάνω παράδειγμα;
[Λείπει από τη φωτογραφία: τα υπόλοιπα ερωτήματα του Θέματος 6 μετά το (α) και τα υπόλοιπα θέματα της εξέτασης]
Λύσεις (⚪ AI, μη επαληθευμένο)
Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (sonnet), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο
Προσοχή
Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.
AI λύσεις — 2023-02¶
Οι λύσεις γράφτηκαν από μοντέλα AI και δεν έχουν ελεγχθεί από άνθρωπο. Η αρίθμηση ακολουθεί το αρχείο θεμάτων.
Θέμα 6 (α)¶
Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: υψηλή
Φωτεινότητες \(x_1..x_7\): 8, 40, 20, 16, 32, 36, 24.
- Περιττοί δείκτες \(\{x_1,x_3,x_5,x_7\}\): \(8+20+32+24=84\).
- Άρτιοι δείκτες \(\{x_2,x_4,x_6\}\): \(40+16+36=92\).
Ο άπληστος επιστρέφει το μέγιστο: 92.
(Σημείωση: το βέλτιστο είναι \(\{x_2,x_5,x_7\}=96\), άρα ο άπληστος δεν είναι βέλτιστος.)
Τα υπόλοιπα ερωτήματα του Θέματος 6 δεν φαίνονται στη μεταγραφή.