Άπληστοι αλγόριθμοι — βέλτιστη επιλογή χρονικών διαστημάτων

Σαφές συμβόλαιο

Έχουμε εργασίες με ακέραιο χρόνο έναρξης και λήξης. Ζητάμε το μέγιστο πλήθος μη επικαλυπτόμενων εργασιών σε έναν μόνο πόρο. Κάθε εργασία έχει ίδια αξία, η έναρξη προηγείται αυστηρά της λήξης και μία εργασία μπορεί να ξεκινήσει ακριβώς όταν τελειώνει η προηγούμενη. Με αυτές τις προϋποθέσεις, η άπληστη επιλογή της εργασίας που τελειώνει νωρίτερα δίνει βέλτιστο πλήθος. Η επιλογή με βάση την πιο πρώιμη έναρξη μπορεί να αποτύχει: μία μεγάλη εργασία αποκλείει πολλές μικρές.

Εκτελέσιμο εργαστήριο Python 3

Αποθήκευσε ως intervals_lab.py και εκτέλεσε python3 intervals_lab.py. Το πρώτο μεγάλο διάστημα ξεκινά νωρίτερα, όμως επιλέγονται τρεις μικρότερες εργασίες.

def select(intervals):
    if any(type(s) is not int or type(e) is not int or s >= e
           for s,e in intervals):
        raise ValueError("invalid interval")
    chosen, end = [], None
    for start, finish in sorted(intervals, key=lambda pair:(pair[1],pair[0])):
        if end is None or start >= end:
            chosen.append((start,finish))
            end = finish
    return chosen

jobs = [(0,5),(1,2),(2,3),(3,4)]
assert select(jobs) == [(1,2),(2,3),(3,4)]
assert select([]) == []
try:
    select([(2,2)])
except ValueError:
    pass
else:
    raise AssertionError("empty interval accepted")
print("PASS: earliest finish and interval boundaries")

Γιατί η στρατηγική είναι σωστή

Έστω G η συμβατή εργασία που τελειώνει πρώτη και O η πρώτη εργασία μίας βέλτιστης λύσης. Αν αντικαταστήσουμε την O με την G, ο διαθέσιμος χρόνος για τις υπόλοιπες εργασίες δεν μικραίνει, επειδή η G τελειώνει το αργότερο όσο η O. Επαναλαμβάνοντας το επιχείρημα κατασκευάζουμε μία βέλτιστη λύση που ακολουθεί τις άπληστες επιλογές. Η ταξινόμηση κοστίζει O(n log n), η διάσχιση O(n) και η αποθήκευση των επιλογών έως O(n). Το επιχείρημα δεν ισχύει αυτούσιο όταν οι εργασίες έχουν διαφορετικές αμοιβές ή μοιράζονται πολλούς πόρους.

Ελεγχόμενες ασκήσεις

1. Πρόσθεσε εργασία που ξεκινά ακριβώς όταν λήγει προηγούμενη και εξήγησε γιατί δεν υπάρχει επικάλυψη.
2. Δοκίμασε διπλά χρονικά διαστήματα, μηδενική διάρκεια και αρνητική διάρκεια. Όρισε ρητό κανόνα.
3. Για έως οκτώ εργασίες εξέτασε όλα τα υποσύνολα και σύγκρινε το καλύτερο πλήθος με την άπληστη λύση.
4. Πρόσθεσε διαφορετικές αξίες και κατασκεύασε αντιπαράδειγμα όπου η επιλογή πρώτης λήξης δεν μεγιστοποιεί το συνολικό όφελος.

Παραδοτέα: PASS, περιγραφή επιχειρήματος ανταλλαγής, μία άκυρη εργασία και αντιπαράδειγμα βαρών.