Αλγόριθμοι και Συνδυαστική Βελτιστοποίηση — Ιούνιος 2020 (Σετ 2)¶
Η μεταγραφή προέρχεται από τη φωτογραφία aco-june20-set2.png.
aco-june20-set2.png¶
Ερώτηση 1 (Πολλαπλής Επιλογής (Μοναδική Απάντηση) — 0.60 βαθμοί)
(12%) Θεωρήστε ότι ο αλγόριθμος Dijkstra με χρήση μιας ουράς προτεραιότητας MySuperPQ εφαρμόζεται σε ένα κατευθυνόμενο γράφημα G = (V,E) με μη αρνητικά κόστη στις ακμές του, και έστω n = |V| και |m| = |E|. Οι χρόνοι των βασικών λειτουργιών της MySuperPQ σε ένα σύνολο N δεδομένων έχουν ως εξής: οι λειτουργίες create, insert, find-min εκτελούνται σε επιμερισμένο χρόνο O(1), η λειτουργία delete-min εκτελείται σε χρόνο χειρότερης περίπτωσης O(log² N), και η λειτουργία decrease-key εκτελείται σε επιμερισμένο χρόνο O(log N).
Ποια από τις παρακάτω είναι η ασυμπτωτική πολυπλοκότητα χειρότερης περίπτωσης του αλγορίθμου Dijkstra με χρήση της MySuperPQ ;
- [ ] A: O((m+n)log² n)
- [ ] B: O(mlogn + nlog² n)
- [ ] Γ: O(mlogn + nlogn)
- [ ] Δ: O(m + nlog² n)
- [ ] E: O(mlog² n + nlogn)
- [ ] ΣΤ: καμία από τις προηγούμενες.
Ερώτηση 2 (Ελεύθερου Κειμένου — 0.60 βαθμοί)
Δικαιολογήστε συνοπτικά την απάντησή σας στην παραπάνω ερώτηση 1:
[κενό πεδίο απάντησης]
Ερώτηση 3 (Ελεύθερου Κειμένου — 1.30 βαθμοί)
(13%) Θεωρήστε τον αλγόριθμο του Dial για την επίλυση του προβλήματος συντομότερων διαδρομών από μια αρχική κορυφή s σε ένα κατευθυνόμενο γράφημα G = (V,E) (|V| = n, |E| = m) με μη αρνητικά κόστη ακμών, που παίρνουν ακέραιες τιμές στο διάστημα [0, Δ]. Έστω S το σύνολο των κορυφών με οριστικοποιημένες (μόνιμες) ετικέτες και S' = V − S το σύνολο των κορυφών με προσωρινές (αλλά πεπερασμένες) ετικέτες. Δείξτε ότι αν d(u) είναι η ετικέτα που δηλώνεται μόνιμη στην αρχή μιας επανάληψης (δηλαδή u είναι η κορυφή με την ελάχιστη ετικέτα), τότε στο τέλος αυτής της επανάληψης θα ισχύει d(v) ≤ d(u) + Δ, για κάθε v ∈ S'.
Απάντηση:
[κενό πεδίο απάντησης]
Επιπλέον πηγές χωρίς μεταγραφή εδώ (λύσεις →
2020-06-b.solutions.md, ή διπλότυπες φωτογραφίες της ίδιας σελίδας):104175265_751736782032945_7473132285045078598_n.jpg
Λύσεις (⚪ AI, μη επαληθευμένο)
Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (deepseek-flash), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο
Προσοχή
Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.
AI λύσεις — 2020-06-b¶
Οι λύσεις γράφτηκαν από μοντέλα AI και δεν έχουν ελεγχθεί από άνθρωπο. Η αρίθμηση ακολουθεί το αρχείο θεμάτων.
Θέμα 1¶
Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: υψηλή
Σωστή επιλογή: Β: \(O(m\log n+n\log^2 n)\).
Στον Dijkstra εκτελούνται το πολύ \(n\) delete-min, καθένα χειρότερης περίπτωσης \(O(\log^2 n)\), άρα συνολικά \(O(n\log^2 n)\), και το πολύ \(m\) decrease-key, καθένα με επιμερισμένο κόστος \(O(\log n)\), άρα συνολικά \(O(m\log n)\). Οι υπόλοιπες πράξεις είναι γραμμικές/σταθερές και δεν αλλάζουν το ασυμπτωτικό αποτέλεσμα.
Θέμα 2¶
Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: υψηλή
Το συνολικό κόστος της εκτέλεσης είναι:
[
O(n)\cdot O(1)+O(n)\cdot O(\log^2 n)+O(m)\cdot O(\log n)+O(n)+O(m).
]
Εδώ χρησιμοποιούμε ότι οι insert και find-min γίνονται συνολικά \(O(n)\) φορές και κοστίζουν \(O(1)\) επιμερισμένα, οι delete-min γίνονται το πολύ \(n\) φορές με κόστος \(O(\log^2 n)\) η καθεμία, και οι decrease-key γίνονται το πολύ \(m\) φορές με επιμερισμένο κόστος \(O(\log n)\) η καθεμία. Άρα:
[
O(n\log^2 n+m\log n).
]
Επομένως η σωστή επιλογή είναι η Β: \(O(m\log n+n\log^2 n)\).
Θέμα 3¶
Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: υψηλή
Έστω ότι στην αρχή μιας επανάληψης η \(u\in S'\) έχει την ελάχιστη ετικέτα, δηλαδή \(d(u)\le d(x)\) για κάθε \(x\in S'\). Επειδή οι ακμές έχουν βάρη στο \([0,\Delta]\), όταν μια μόνιμη κορυφή \(p\) χαλαρώσει μια ακμή \((p,v)\), η νέα ετικέτα ικανοποιεί [ d(v)\le d(p)+w(p,v)\le d(p)+\Delta. ] Για κάθε \(v\in S'\) με πεπερασμένη ετικέτα, η τιμή \(d(v)\) προέκυψε από χαλάρωση κάποιας ακμής \((p,v)\) από μόνιμη κορυφή \(p\). Αν \(p=u\), τότε άμεσα [ d(v)\le d(u)+w(u,v)\le d(u)+\Delta. ] Αν \(p\neq u\), τότε η \(p\) είχε οριστικοποιηθεί σε προηγούμενη επανάληψη. Επειδή ο Dial οριστικοποιεί τις κορυφές με μη φθίνουσα σειρά ετικετών και η \(u\) είναι η ελάχιστη μη μόνιμη κορυφή στην αρχή της τρέχουσας επανάληψης, ισχύει \(d(p)\le d(u)\). Άρα [ d(v)\le d(p)+w(p,v)\le d(u)+\Delta. ] Αν κάποια ετικέτα δεν βελτιωθεί στην τρέχουσα επανάληψη, ικανοποιεί ήδη το ίδιο φράγμα από την προηγούμενη χαλάρωσή της. Επομένως, στο τέλος της επανάληψης, για κάθε \(v\in S'\) ισχύει [ d(v)\le d(u)+\Delta. ]