L12 · Άπληστοι Αλγόριθμοι II — Ελάχιστη Καθυστέρηση & Τοπολογική Διάταξη

Τι θα δούμε

Δύο θέματα — και μία τεχνική απόδειξης που θα ξαναδείς σε κάθε εξεταστική:

1. Χρονοπρογραμματισμός με ελάχιστη καθυστέρηση, και μαζί το επιχείρημα ανταλλαγής (exchange argument) — η δεύτερη μεγάλη τεχνική για άπληστους αλγορίθμους, μετά το «ο άπληστος προηγείται» του L11.
2. Τοπολογική διάταξη — πώς βάζεις σε σειρά εργασίες με προαπαιτούμενα, και γιατί αυτό γίνεται αν και μόνο αν δεν υπάρχουν κύκλοι.

Χρονοπρογραμματισμός με ελάχιστη καθυστέρηση

Διατύπωση

Μία μηχανή, που επεξεργάζεται μία εργασία τη φορά.

• Η εργασία $j$ απαιτεί $t_j$ μονάδες χρόνου και έχει προθεσμία $d_j$.
• Αν ξεκινήσει τη στιγμή $s_j$, τελειώνει τη στιγμή $f_j=s_j+t_j$.
• Καθυστέρηση της $j$: ${\ell }_j=\max \{0,f_j-d_j\}$ — πόσο μετά την προθεσμία της τελείωσε (ή $0$ αν πρόλαβε).

Στόχος: προγραμμάτισε όλες τις εργασίες ελαχιστοποιώντας τη μέγιστη καθυστέρηση $L={\max }_j{\ell }_j$.

Υποψήφια κριτήρια

Πάλι το ίδιο άπληστο πρότυπο: βάλε τις εργασίες σε κάποια σειρά και τρέξε τες. Όλο το ζήτημα είναι ποια σειρά. Τρεις λογικοφανείς υποψήφιες:

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

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

Ο αλγόριθμος: Earliest Deadline First

Τον είδες ήδη να τρέχει στην καρτέλα «Earliest Deadline First» του εργαλείου παραπάνω — και να πετυχαίνει την ελάχιστη δυνατή μέγιστη καθυστέρηση. Μένει το δύσκολο: γιατί αυτό συμβαίνει πάντα.

Δύο παρατηρήσεις-κλειδιά

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

Το επιχείρημα ανταλλαγής

Όλη η απόδειξη στηρίζεται σε μία κίνηση: παίρνεις δύο διαδοχικές εργασίες που είναι αντεστραμμένες και τις αντιμεταθέτεις.

Αυτός ο ισχυρισμός είναι, ουσιαστικά, ολόκληρη η απόδειξη — και γίνεται απτός μόνο όταν τον χειριστείς ο ίδιος. Παρακάτω ένα χρονοδιάγραμμα ξεκινά ανακατεμένο, με αρκετές αντιστροφές. Κάθε ⇄ σημαδεύει ένα διαδοχικό αντεστραμμένο ζεύγος· κάνε κλικ και αντιμετάθεσέ το. Παρακολούθησε δύο αριθμούς: τις αντιστροφές (πέφτουν κατά $1$ κάθε φορά) και τη μέγιστη καθυστέρηση $L$ — που δεν ανεβαίνει ποτέ:

Απόδειξη του ισχυρισμού. Έστω $i,j$ διαδοχικές με αντιστροφή ($d_i<d_j$, αλλά η $j$ πριν την $i$). Αντιμεταθέτουμέ τες. Συμβολίζουμε με ${\ell }_k$ τις παλιές καθυστερήσεις και ${\ell }_k^{\prime }$ τις νέες.

• Για κάθε $k\ne i,j$: η εργασία $k$ δεν μετακινήθηκε καθόλου, άρα ${\ell }_k^{\prime }={\ell }_k$.
• Η $i$ μετακινήθηκε νωρίτερα, άρα τελειώνει νωρίτερα: ${\ell }_i^{\prime }\le {\ell }_i$.
• Η $j$ μετακινήθηκε αργότερα. Τελειώνει τώρα ακριβώς εκεί όπου τελείωνε πριν η $i$ — δηλαδή $f_j^{\prime }=f_i$. Άρα:

όπου η ανισότητα ισχύει επειδή $d_j>d_i$.

Άρα και οι δύο νέες καθυστερήσεις, ${\ell }_i^{\prime }$ και ${\ell }_j^{\prime }$, είναι $\le {\ell }_i$ — δηλαδή $\le$ από κάτι που ήδη μετριόταν στην παλιά μέγιστη. Η μέγιστη καθυστέρηση δεν αυξήθηκε. $■$

Οι τρεις τεχνικές απόδειξης άπληστων αλγορίθμων

Τοπολογική διάταξη

Το πρόβλημα

Πολλές εργασίες με προαπαιτούμενα: η εργασία $u$ πρέπει να γίνει πριν την $v$. Τα μοντελοποιούμε με ένα κατευθυνόμενο γράφημα $G=(V,A)$ — η ακμή $(u,v)$ σημαίνει «η $u$ προηγείται της $v$».

Ο ορισμός γίνεται κατανοητός μόνο όταν τον παλέψεις. Παρακάτω οι κορυφές κάθονται σε μια σειρά από θέσεις· κάνε κλικ σε δύο για να ανταλλάξουν θέσεις. Κάθε ακμή χρωματίζεται πράσινη αν δείχνει δεξιά, κόκκινη αν δείχνει αριστερά. Στόχος: όλες πράσινες. Δοκίμασε και τις δύο καρτέλες — το άκυκλο γράφημα και εκείνο με τον κύκλο:

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

Πότε υπάρχει;

Δεν έχουν όλα τα κατευθυνόμενα γραφήματα τοπολογική διάταξη. Αν $a\to b\to c\to a$, ποια μπαίνει πρώτη; Καμία — υπάρχει κύκλος, κι ένας κύκλος δεν χωράει ποτέ σε μία ευθεία γραμμή. Το είδες μόλις στο εργαλείο.

Μέρος 1 — αν έχει τοπολογική διάταξη, τότε είναι DAG. Έστω ότι το $G$ έχει τοπολογική διάταξη $v_1,\dots ,v_n$ και έναν κύκλο $C$. Έστω $v_i$ η κορυφή του $C$ με τον μικρότερο δείκτη, και $v_j$ η κορυφή ακριβώς πριν την $v_i$ μέσα στον $C$. Τότε η $(v_j,v_i)$ είναι ακμή. Από την επιλογή της $v_i$ ως μικρότερης, $i<j$· αλλά μια ακμή σε τοπολογική διάταξη πάει εμπρός, άρα $j<i$. Άτοπο. $■$

Μέρος 2 — κάθε DAG έχει μια «πηγή»: κορυφή χωρίς εισερχόμενες ακμές. Έστω, για άτοπο, ότι κάθε κορυφή έχει εισερχόμενη ακμή. Τότε ξεκίνα από μια οποιαδήποτε κορυφή και ακολούθα ακμές προς τα πίσω — κάθε φορά μπορείς, γιατί καμία κορυφή δεν είναι πηγή. Με $n$ κορυφές, μετά από το πολύ $n$ βήματα θα συναντήσεις κάποια κορυφή δύο φορές — και το κομμάτι της διαδρομής ανάμεσα στις δύο επισκέψεις είναι κύκλος. Άτοπο, αφού το $G$ είναι DAG. $■$

Αυτό το επιχείρημα είναι καθαρό «εις άτοπον» και αξίζει να το δεις να εκτελείται. Διάλεξε μια αφετηρία και ακολούθα ακμές προς τα πίσω. Στην καρτέλα DAG η διαδρομή κολλάει αναγκαστικά σε μια πηγή· στην καρτέλα «Χωρίς πηγή» — όπου κάθε κορυφή έχει εισερχόμενη ακμή — δεν κολλάει ποτέ, και γι' αυτό κλείνει κύκλο:

Μέρος 3 — κάθε DAG έχει τοπολογική διάταξη. Επαγωγή στο πλήθος κορυφών. Βάση $n=1$: προφανές. Βήμα: σε ένα DAG με $k+1$ κορυφές, από το Μέρος 2 υπάρχει πηγή $v$ (χωρίς εισερχόμενες ακμές). Το $G\setminus \{v\}$ είναι DAG με $k$ κορυφές, άρα (επαγωγική υπόθεση) έχει τοπολογική διάταξη. Τοποθετούμε την $v$ πρώτη — αφού δεν έχει εισερχόμενες ακμές, κάθε ακμή της δείχνει εμπρός. $■$

Ο αλγόριθμος

Η απόδειξη του Μέρους 3 είναι ο αλγόριθμος: βγάζε επανειλημμένα μια κορυφή χωρίς εισερχόμενες ακμές.

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

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

Βάλε στη σειρά τα βήματα της τοπολογικής διάταξης:

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

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