L11 · Άπληστοι Αλγόριθμοι I — Χρονοπρογραμματισμός Διαστημάτων

Τι θα δούμε

Ξεκινά μια νέα οικογένεια αλγορίθμων: οι άπληστοι (greedy). Τους συναντήσαμε ήδη στο L09 — Dijkstra, Prim, Kruskal — αλλά εκεί η απληστία ήταν «κρυμμένη» μέσα στο γράφημα. Εδώ τη βλέπουμε γυμνή, σε δύο προβλήματα χρονοπρογραμματισμού:

1. Χρονοπρογραμματισμός διαστημάτων — διάλεξε όσο το δυνατόν περισσότερες μη-επικαλυπτόμενες εργασίες.
2. Διαμέριση διαστημάτων — μοίρασε όλες τις εργασίες σε όσο το δυνατόν λιγότερες μηχανές.

Η ιδέα του άπληστου αλγορίθμου

Δες την παγίδα να συμβαίνει. Ο πεζοπόρος παρακάτω ακολουθεί έναν και μόνο κανόνα — «κάνε πάντα το βήμα προς τα πάνω» — και δεν βλέπει τίποτα πέρα από τα δύο σημεία δίπλα στα πόδια του. Άλλαξε την αφετηρία και δες πού καταλήγει:

Ίδιος κανόνας, διαφορετική κατάληξη: άλλοτε η κορυφή, άλλοτε ένας λοφίσκος. Κι ο πεζοπόρος δεν μαθαίνει ποτέ τη διαφορά — από εκεί που στέκεται, ο λοφίσκος μοιάζει με κορυφή. Αυτός είναι ο άπληστος αλγόριθμος σε μία εικόνα. Γι' αυτό δεν αρκεί να βρεις έναν κανόνα που «δείχνει λογικός»· πρέπει να τον αποδείξεις. Θα ξεκινήσουμε δείχνοντας ότι οι περισσότεροι λογικοφανείς κανόνες απλώς δεν δουλεύουν.

Χρονοπρογραμματισμός διαστημάτων

Διατύπωση

Είσοδος: $n$ εργασίες· η εργασία $j$ ξεκινά τη στιγμή $s_j$ και τελειώνει τη στιγμή $f_j$.

Δύο εργασίες είναι συμβατές αν δεν επικαλύπτονται χρονικά.

Στόχος: βρες το μεγαλύτερο σε πλήθος υποσύνολο εργασιών που είναι ανά δύο συμβατές.

Το άπληστο πρότυπο — και ποια σειρά

Όλοι οι υποψήφιοι άπληστοι αλγόριθμοι έχουν την ίδια σκελετική μορφή:

Θεώρησε τις εργασίες σε κάποια σειρά. Διάλεξε κάθε εργασία εφόσον είναι συμβατή με όσες έχεις ήδη επιλέξει.

Όλο το παιχνίδι είναι ποια σειρά. Τέσσερις λογικοφανείς υποψήφιες:

Τρεις από τις τέσσερις είναι λάθος. Στο εργαλείο παρακάτω, κάθε κριτήριο έρχεται με το δικό του στιγμιότυπο: για τα τρία λανθασμένα κριτήρια είναι ένα αντιπαράδειγμα — μια είσοδος όπου ο κανόνας αποδεδειγμένα αποτυγχάνει· για το σωστό, μια είσοδος που τη λύνει τέλεια. Διάλεξε κριτήριο και σάρωσε βήμα-βήμα:

Γιατί τα τρία κριτήρια αποτυγχάνουν

Κάθε ένα από τα τρία λανθασμένα κριτήρια έχει ένα μικρό, καθαρό αντιπαράδειγμα — κι αυτό ακριβώς δείχνει η αντίστοιχη καρτέλα του εργαλείου παραπάνω.

Μικρότερος χρόνος έναρξης. Στην καρτέλα «Πρώτη έναρξη», μία εργασία ξεκινά πρώτη απ' όλες και απλώνεται σχεδόν σε ολόκληρο τον άξονα. Επειδή ξεκινά πρώτη, ο κανόνας τη διαλέγει αμέσως — και τότε αυτή επικαλύπτεται με καθεμία από τις τέσσερις σύντομες εργασίες, που από μόνες τους θα χωρούσαν άνετα όλες μαζί. Λύση: 1 αντί για 4. Το πότε ξεκινά μια εργασία δεν λέει τίποτα για το πόσο χώρο αφήνει στις επόμενες.

Μικρότερο διάστημα. Στην καρτέλα «Μικρότερο διάστημα», η συντομότερη εργασία «κάθεται» ακριβώς πάνω στο σημείο όπου δύο μεγαλύτερες εργασίες σχεδόν αγγίζονται. Οι δύο μεγάλες είναι μεταξύ τους συμβατές — αλλά η σύντομη επικαλύπτεται και με τις δύο, οπότε διαλέγοντάς τη τις χάνεις αμφότερες. Λύση: 1 αντί για 2. Μικρή διάρκεια δεν σημαίνει «μικρό εμπόδιο».

Λιγότερες διενέξεις. Το πιο ύπουλο από τα τρία. Στην καρτέλα «Λιγότερες διενέξεις», η βέλτιστη λύση είναι οι τέσσερις εργασίες της πάνω σειράς. Όμως οι δύο μεσαίες της σειράς συγκρούονται με πολλές γειτονικές, άρα ο κανόνας τις αφήνει για το τέλος. Διαλέγει πρώτα τις εργασίες με τις «λίγες» συγκρούσεις — κι ανάμεσά τους μία εργασία που, ενώ μετράει λίγες διενέξεις, στέκεται σ' ένα σταυροδρόμι και μπλοκάρει ταυτόχρονα δύο εργασίες της βέλτιστης λύσης. Λύση: 3 αντί για 4. Το να συγκρούεσαι με λίγες εργασίες δεν σημαίνει ότι δεν είσαι εσύ το κρίσιμο εμπόδιο.

Το κριτήριο που δουλεύει: μικρότερος χρόνος λήξης

Ορθότητα — «ο άπληστος προηγείται»

Απόδειξη (εις άτοπον). Έστω $i_1,i_2,\dots ,i_k$ οι εργασίες που επιλέγει ο άπληστος, σε σειρά. Έστω $j_1,j_2,\dots ,j_m$ μια βέλτιστη λύση — και μάλιστα διαλεγμένη έτσι ώστε να συμφωνεί με τον άπληστο για όσο το δυνατόν περισσότερες αρχικές εργασίες: $i_1=j_1,\dots ,i_r=j_r$ για τη μέγιστη δυνατή τιμή του $r$.

Αν ο άπληστος δεν είναι βέλτιστος, τότε $k<m$. Θα φτάσουμε σε άτοπο.

Βήμα 1 — ο άπληστος «προηγείται». Ισχυρισμός: $f(i_{r+1})\le f(j_{r+1})$. Γιατί; Αφού $i_r=j_r$, η εργασία $j_{r+1}$ είναι συμβατή με την $i_r$ — άρα ήταν υποψήφια τη στιγμή που ο άπληστος διάλεγε την $i_{r+1}$. Και ο άπληστος επιλέγει πάντα την υποψήφια με τον μικρότερο χρόνο λήξης. Άρα η $i_{r+1}$ δεν τελειώνει αργότερα από την $j_{r+1}$.

Βήμα 2 — η ανταλλαγή. Φτιάχνουμε νέα λύση αντικαθιστώντας στη βέλτιστη την $j_{r+1}$ με την $i_{r+1}$:

$S^{\prime }=j_1,\dots ,j_r,i_{r+1},j_{r+2},\dots ,j_m.$

Είναι έγκυρη: η $i_{r+1}$ είναι συμβατή με τις $j_1,\dots ,j_r$ (αυτές είναι οι $i_1,\dots ,i_r$, και ο άπληστος την επέλεξε δίπλα τους)· και επειδή $f(i_{r+1})\le f(j_{r+1})$, η $i_{r+1}$ τελειώνει όχι αργότερα από την $j_{r+1}$, οπότε δεν συγκρούεται ούτε με την $j_{r+2}$. Το $S^{\prime }$ έχει $m$ εργασίες — άρα είναι κι αυτό βέλτιστο — αλλά συμφωνεί με τον άπληστο για $r+1$ εργασίες. Αντίφαση με τη μεγιστότητα του $r$.

Μένει η περίπτωση $k=r<m$: τότε υπάρχει η $j_{r+1}$, συμβατή με την $i_r$ — και ο άπληστος δεν θα είχε σταματήσει, θα την είχε εξετάσει. Άτοπο. Άρα $k=m$. $■$

Η ανταλλαγή είναι η καρδιά της απόδειξης — και γίνεται πολύ πιο καθαρή όταν τη δεις να εκτελείται. Πάνω η λύση του άπληστου, κάτω μια βέλτιστη· σε κάθε θέση πρόσεξε την ανισότητα $f(i_r)\le f(j_r)$ — «ο άπληστος δεν τελειώνει ποτέ αργότερα» — και μετά την ανταλλαγή που ξαναγράφει τη βέλτιστη μία εργασία πιο κοντά στον άπληστο, ώσπου οι δύο λύσεις να ταυτιστούν:

Διαμέριση διαστημάτων

Διατύπωση

Αλλάζουμε ριζικά το ερώτημα. Τώρα πρέπει να προγραμματίσουμε όλες τις εργασίες — αλλά έχουμε πολλές μηχανές.

Στόχος: βρες το ελάχιστο πλήθος μηχανών ώστε κάθε εργασία να ανατεθεί σε μία μηχανή, με δύο εργασίες που τρέχουν ταυτόχρονα ποτέ στην ίδια μηχανή.

Το κάτω φράγμα — το βάθος

Αν σε κάποια στιγμή τρέχουν ταυτόχρονα $d$ εργασίες, αυτές χρειάζονται $d$ διαφορετικές μηχανές — αναγκαστικά. Άρα κάθε λύση, όσο έξυπνη κι αν είναι, χρειάζεται:

$\text{πληˊθος μηχανωˊν}\ge \text{βαˊθος}.$

Το βάθος είναι πιο εύκολο να το δεις παρά να το ορίσεις: πέρνα μια κατακόρυφη γραμμή σάρωσης πάνω από τον χρόνο και μέτρα πόσες εργασίες κόβει σε κάθε στιγμή — η μεγαλύτερη τιμή που θα συναντήσει είναι το βάθος. Ξεκίνα με τη λειτουργία «Βάθος» του εργαλείου· κράτησέ το ανοιχτό, θα το χρειαστούμε ξανά αμέσως μετά:

Το ερώτημα τώρα: μπορούμε πάντα να πετύχουμε ακριβώς το βάθος — ή μήπως υπάρχουν στιγμιότυπα που απαιτούν περισσότερες μηχανές απ' όσο το βάθος τους;

Ο άπληστος αλγόριθμος

Γύρνα τώρα τον διακόπτη του εργαλείου παραπάνω στη λειτουργία «Άπληστος» και δες τον αλγόριθμο να τρέχει σ' αυτό ακριβώς το στιγμιότυπο — εργασία την εργασία, μηχανή τη μηχανή. Πρόσεξε ιδιαίτερα τη στιγμή που ανοίγει η τρίτη μηχανή.

Ορθότητα — το επιχείρημα του βάθους

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

Απόδειξη. Έστω $d$ το πλήθος μηχανών που άνοιξε ο αλγόριθμος. Η τελευταία μηχανή, η $d$-οστή, άνοιξε επειδή κάποια εργασία — έστω η $j$ — δεν ήταν συμβατή με καμία από τις $d-1$ μηχανές που ήδη υπήρχαν.

Άρα, τη στιγμή που εξετάστηκε η $j$, καθεμία από τις $d-1$ μηχανές είχε τουλάχιστον μία εργασία σε σύγκρουση με την $j$. Επειδή ο αλγόριθμος εξετάζει τις εργασίες κατά αύξοντα χρόνο έναρξης, όλες αυτές οι εργασίες ξεκίνησαν πριν την $s_j$ — και αφού συγκρούονται με την $j$, καμία τους δεν έχει τελειώσει μέχρι την $s_j$.

Συνεπώς, τη χρονική στιγμή λίγο μετά την $s_j$ τρέχουν ταυτόχρονα $d$ εργασίες — οι $d-1$ συν την $j$. Άρα το βάθος είναι $\ge d$.

Αλλά κάθε λύση χρειάζεται $\ge \text{βαˊθος}\ge d$ μηχανές, και ο άπληστος χρησιμοποιεί ακριβώς $d$. Άρα είναι βέλτιστος. $■$

Αυτό ακριβώς ανάβει κόκκινο στο εργαλείο τη στιγμή που ανοίγει η τρίτη μηχανή: η κατακόρυφη γραμμή δείχνει τρεις εργασίες να τρέχουν μαζί. Το βάθος «αποκαλύφθηκε» μέσα από την ίδια την εκτέλεση του αλγορίθμου — δεν χρειάστηκε καν ξεχωριστή σάρωση για να το βρούμε.

Κλείδωσε τη γνώση

Βάλε στη σειρά τα βήματα του χρονοπρογραμματισμού διαστημάτων:

Και συμπλήρωσε τα κενά:

Μοτίβο σκέψης