Dynamic programming·Διάλεξη 17·~42 min

L17 · Δυναμικός Προγραμματισμός IV — Ανεξάρτητο Σύνολο σε Δέντρα & Bellman-Ford

Χρειάζεσαι:L16 · DP III — LCS, edit distance L09 · Γραφήματα IV — MST (Prim, Kruskal)

Τι θα δούμε

Φτάσαμε στην τελευταία διάλεξη. Σε όλον τον δυναμικό προγραμματισμό μέχρι τώρα (L14–L16) το υποπρόβλημα είχε σχεδόν πάντα το ίδιο σχήμα: «τα πρώτα $j$ στοιχεία μιας ακολουθίας». Σήμερα το υποπρόβλημα γίνεται κάτι πιο πλούσιο — ένα κομμάτι ενός γραφήματος:

Ανεξάρτητο σύνολο σε δέντρα — DP όπου τα υποπροβλήματα είναι υποδέντρα.
Bellman-Ford — συντομότερες διαδρομές όταν κάποιες ακμές έχουν αρνητικό βάρος, εκεί ακριβώς που ο Dijkstra του L09 τα παρατάει. Έτσι κλείνει και μια υπόσχεση που έμεινε ανοιχτή από τότε.

Ανεξάρτητο σύνολο σε δέντρα — «το πάρτι»

Το πρόβλημα

Οργανώνουμε ένα πάρτι για μια εταιρεία με αυστηρή ιεραρχική δομή. Κάθε υπάλληλος $v$ έχει μια θετική «προσφορά» $χ (v)$ — πόσο κέφι φέρνει στο πάρτι. Ένας περιορισμός: δεν καλούμε ταυτόχρονα έναν υπάλληλο και τον άμεσο προϊστάμενό του.

Είσοδος: ένα δέντρο που περιγράφει την ιεραρχία, με μια προσφορά σε κάθε κορυφή.

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

Δύο τιμές ανά κορυφή

Όπως σε κάθε DP (L14), το πρώτο βήμα είναι να βρούμε το σωστό υποπρόβλημα. Εδώ η επιλογή είναι φυσική: για κάθε κορυφή $v$ , κοίτα μόνο το υποδέντρο της — την $v$ και όλους τους απογόνους της. Αν λύσουμε κάθε υποδέντρο, η απάντηση για ολόκληρο το δέντρο είναι απλώς το υποδέντρο της ρίζας.

Μένει να συνδέσουμε ένα υποδέντρο με τα υποδέντρα των παιδιών του. Κι εδώ κρύβεται μια παγίδα.

Μία τιμή ανά κορυφή δεν αρκεί. Ας υποθέσουμε ότι για κάθε κορυφή κρατάμε έναν μόνο αριθμό: «το βάρος του καλύτερου ανεξάρτητου συνόλου μέσα στο υποδέντρό της». Ακούγεται λογικό — αλλά σπάει. Όταν αποφασίζουμε για μια κορυφή $v$ , αν την βάλουμε μέσα τότε κανένα παιδί της δεν επιτρέπεται. Χρειαζόμαστε λοιπόν να ξέρουμε «το καλύτερο του υποδέντρου ενός παιδιού χωρίς το ίδιο το παιδί». Ένας μόνο αποθηκευμένος αριθμός δεν το ξεχωρίζει αυτό — μπορεί κρυφά να περιλαμβάνει το παιδί, κι έτσι η σύνθεση βγάζει παράνομο σύνολο. Δοκίμασέ το:

Γιατί χρειάζονται δύο τιμές ανά κορυφή

Νόμιμο σύνολο

Ανεξάρτητο σύνολο = κανένα ζευγάρι γειτόνων μαζί. Ο αριθμός σε κάθε κορυφή είναι η προσφορά χ.

Πόσες τιμές κρατάμε ανά κορυφή;

Βάζουμε το p στο σύνολο;

Το p μένει έξω. Δεν μπλοκάρει κανέναν — η καλύτερη απάντηση για το υποδέντρο του p είναι απλώς το καλύτερο σύνολο του υποδέντρου του c: 9, που το πετυχαίνει το σύνολο {c}.

Το δίδαγμα: ένα σκέτο «καλύτερο σύνολο του υποδέντρου» δεν λέει αν η ρίζα του είναι μέσα ή έξω — κι αυτό ακριβώς χρειάζεται ο γονιός για να αποφασίσει. Γι' αυτό κάθε κορυφή κρατά δύο τιμές: A[v] (η v επιτρέπεται) και B[v] (η v σίγουρα έξω).

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

Έστω $v$ με παιδιά (άμεσους υφισταμένους) $v_{1}, v_{2}, \dots, v_{k}$ .

Για το $B [v]$ : η $v$ δεν μπαίνει — άρα δεν μπλοκάρει κανέναν. Κάθε υφιστάμενος επιλέγει ελεύθερα· για κάθε υποδέντρο παίρνουμε το βέλτιστο $A [v_{i}]$ :

$B [v] = \sum_{i = 1}^{k} A [v_{i}]$

Για το $A [v]$ : δύο σενάρια, παίρνουμε το καλύτερο.

Η $v$ δεν μπαίνει: αυτό είναι ακριβώς το $B [v]$ .
Η $v$ μπαίνει: τότε κανένα από τα παιδιά δεν επιτρέπεται, οπότε κάθε υποδέντρο $v_{i}$ συνεισφέρει το $B [v_{i}]$ . Συνολικά: $χ (v) + \sum_{i} B [v_{i}]$ .

$A [v] = max {B [v], χ (v) + \sum_{i = 1}^{k} B [v_{i}]}$

Ο αλγόριθμος

ΑλγόριθμοςΑνεξάρτητο σύνολο μέγιστου βάρους σε δέντρο

O(n)

Για κάθε κορυφή κράτα δύο τιμές, A[v] και B[v]· υπολόγισέ τες από τα φύλλα προς τη ρίζα.

Είσοδος:: δέντρο με προσφορά χ(v) σε κάθε κορυφή
Έξοδος:: η μέγιστη συνολική προσφορά ενός ανεξάρτητου συνόλου

Με λόγια. Υπολογίζουμε τα $A [v], B [v]$ από τα φύλλα προς τη ρίζα — κάθε κορυφή χρειάζεται πρώτα τα παιδιά της. Για φύλλο $ℓ$ : $B [ℓ] = 0$ και $A [ℓ] = χ (ℓ)$ . Για εσωτερική κορυφή, εφαρμόζουμε τους δύο τύπους. Η τελική απάντηση είναι το $A [ρ \overset{ι}{ˊ} ζα]$ .

Πολυπλοκότητα. Κάθε κορυφή και κάθε ακμή επεξεργάζεται $O (1)$ φορές → $O (n)$ συνολικά.

Δες τον υπολογισμό να ανεβαίνει από τα φύλλα στη ρίζα. Σε κάθε κορυφή εμφανίζονται τα $A$ και $B$ της — και στο τέλος φωτίζεται η βέλτιστη λίστα καλεσμένων:

Ανεξάρτητο σύνολο σε δέντρο — από τα φύλλα στη ρίζα

Αρχή

A[v] = καλύτερο στο υποδέντρο · B[v] = καλύτερο χωρίς την v.

Δέντρο ιεραρχίας — ο αριθμός σε κάθε κορυφή είναι η προσφορά χ(v). Θα υπολογίσουμε A[v] και B[v] από τα φύλλα προς τη ρίζα.

Βήμα 0 / 7

Συντομότερες διαδρομές με αρνητικά βάρη

Γιατί ξαναπιάνουμε το πρόβλημα

Στο L09 λύσαμε το πρόβλημα της συντομότερης διαδρομής με τον αλγόριθμο Dijkstra — αλλά με μια ρητή προϋπόθεση: όλα τα βάρη των ακμών έπρεπε να είναι θετικά. Τώρα ρίχνουμε αυτόν τον περιορισμό και επιτρέπουμε και αρνητικά βάρη $ℓ_{e}$ . Φαντάσου ένα δίκτυο όπου κάποιες ακμές κοστίζουν, ενώ άλλες αποδίδουν «κέρδος» — μια πληρωμή, μια έκπτωση, ενέργεια που ανακτάς.

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

Γιατί ο Dijkstra αποτυγχάνει

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

Με μια αρνητική ακμή, η υπόθεση καταρρέει: μια ακμή μπορεί να αφαιρέσει κόστος, οπότε ένα μονοπάτι με περισσότερες ακμές μπορεί τελικά να βγει φθηνότερο. Όμως ο Dijkstra έχει ήδη κλειδώσει την κορυφή. Δες το να συμβαίνει, στο μικρότερο δυνατό παράδειγμα:

Γιατί ο Dijkstra αποτυγχάνει με αρνητική ακμή

Αρχή

Πράσινο = οριστικοποιημένη (κλειδωμένη) · κόκκινο = εξάγεται τώρα.

Αρχικοποίηση: d(s) = 0, d(t) = d(u) = ∞. Καμία κορυφή δεν είναι οριστική. Ο Dijkstra θα εξάγει κάθε φορά την κορυφή με το μικρότερο d.

Βήμα 0 / 4

Γιατί δεν αρκεί να προσθέσεις μια σταθερά

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

Δεν δουλεύει — και αξίζει να καταλάβεις γιατί, γιατί το λάθος είναι λεπτό. Όταν προσθέτεις $k$ σε κάθε ακμή, μια διαδρομή με πολλές ακμές μαζεύει το $k$ πολλές φορές, ενώ μια διαδρομή με λίγες ακμές το μαζεύει λίγες. Οι δύο διαδρομές δεν επιβαρύνονται το ίδιο — άρα η σύγκρισή τους αλλοιώνεται, και η συντομότερη μπορεί να αλλάξει. Σύρε το $k$ και δες τη σωστή απάντηση να ανατρέπεται:

«Πρόσθεσε μια σταθερά» — γιατί δεν δουλεύει

Σωστή απάντηση

Δύο διαδρομές. Πραγματικά μήκη: A = 2, B = −1 — άρα η Διαδρομή B — 4 ακμές είναι όντως η συντομότερη.

Σταθερά k+0 / ακμή

Διαδρομή A — 2 ακμές

2 + 2·0 = 2

Διαδρομή B — 4 ακμές

-1 + 4·0 = -1

Με k = 0, ο Dijkstra επιλέγει την πραγματικά συντομότερη — σωστά. Αλλά υπάρχουν ακόμη αρνητικά βάρη — χρειάζεται k ≥ 4 για να γίνουν όλα ≥ 0. Σύρε το παραπέρα.

Γιατί: κάθε +1 στο k ακριβαίνει τη μία διαδρομή κατά +2 και την άλλη κατά +4. Μια διαδρομή με περισσότερες ακμές μετράει τη σταθερά περισσότερες φορές — έτσι η σύγκριση αλλοιώνεται.

Αρνητικοί κύκλοι

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

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

Αρνητικός κύκλος — η συντομότερη διαδρομή εξαφανίζεται

0 γύροι

Η διαδρομή s→t περνά από τον κύκλο a→b→c→a, που έχει άθροισμα βαρών −3.

Ο κύκλος a→b→c→a: 2 + 1 + (−6) = −3 ανά γύρο.

Κόστος = 4 − 3 × 0 = 4

Η απλή διαδρομή s→a→b→c→t κοστίζει 4. Πάτα «άλλος ένας γύρος» — αντί να βγει στο t, η διαδρομή ξαναγυρίζει τον κύκλο.

0 / 8 γύροι

Κράτα αυτό το «απλή»: θα μας φανεί χρήσιμο σε λίγο. Μια απλή διαδρομή σε γράφημα με $n$ κορυφές έχει το πολύ $n - 1$ ακμές — δεν γίνεται να έχει περισσότερες χωρίς να ξαναπεράσει από κάποια κορυφή.

Ο αλγόριθμος Bellman-Ford

Η αναδρομή — παραμετροποίηση με το πλήθος ακμών

Ξέρουμε ήδη τη συνταγή του DP (L14): σπάσε το πρόβλημα σε υποπροβλήματα, βάλ' τα σε μια σειρά ώστε καθένα να εξαρτάται μόνο από προηγούμενα, και λύσε τα με αυτή τη σειρά.

Εδώ σκοντάφτουμε. Σε ένα γράφημα με κύκλους, η «συντομότερη διαδρομή ως την $v$ » μπορεί να εξαρτάται από τη «συντομότερη διαδρομή ως την $w$ », που με τη σειρά της εξαρτάται πάλι από την $v$ . Τα υποπροβλήματα είναι μπλεγμένα κυκλικά — δεν υπάρχει φυσική σειρά να τα λύσεις.

Το κόλπο του Bellman-Ford: πρόσθεσε μια δεύτερη παράμετρο που αυξάνει πάντα μονότονα — το πλήθος των ακμών που επιτρέπεται να χρησιμοποιεί η διαδρομή. Αυτό δεν μπλέκεται ποτέ σε κύκλο: μια διαδρομή με $i$ ακμές χτίζεται πάντα πάνω σε μία με $i - 1$ ακμές. Να η σειρά που έλειπε.

Σταθεροποιούμε έναν προορισμό $t$ και ορίζουμε:

Έστω $P$ το βέλτιστο τέτοιο μονοπάτι. Δύο περιπτώσεις:

Το $P$ χρησιμοποιεί το πολύ $i - 1$ ακμές — τότε $OPT (i, v) = OPT (i - 1, v)$ .
Το $P$ χρησιμοποιεί ακριβώς $i$ ακμές. Έστω $(v, w)$ η πρώτη του ακμή· το υπόλοιπο είναι το συντομότερο $w \to t$ μονοπάτι με $i - 1$ ακμές. Κόστος: $ℓ_{v w} + OPT (i - 1, w)$ .

Ο αλγόριθμος

ΑλγόριθμοςBellman-Ford

Θ(mn)

n−1 γύροι· σε κάθε γύρο, χαλάρωσε κάθε ακμή — επεκτείνοντας τις διαδρομές κατά μία ακμή τη φορά.

Είσοδος:: κατευθυνόμενο γράφημα με βάρη (ίσως αρνητικά), και προορισμός t
Έξοδος:: η συντομότερη απόσταση από κάθε κορυφή v προς το t

Με λόγια. Ξεκινάμε με $M [0, t] = 0$ και $\infty$ για κάθε άλλη κορυφή. Σε κάθε από τους $n - 1$ γύρους, για κάθε κορυφή $v$ δοκιμάζουμε να βελτιώσουμε την απόστασή της μέσω κάθε εξερχόμενης ακμής $(v, w)$ . Μετά τον γύρο $i$ , ο πίνακας περιέχει τις συντομότερες διαδρομές με το πολύ $i$ ακμές — οπότε μετά από $n - 1$ γύρους έχουμε τις τελικές αποστάσεις.

Πολυπλοκότητα. $n - 1$ γύροι, και κάθε γύρος εξετάζει κάθε ακμή μία φορά → $Θ (mn)$ χρόνος, $Θ (n^{2})$ χώρος.

Δες τους γύρους να γεμίζουν τον πίνακα. Πρόσεξε ιδιαίτερα το $M [i, s]$ : μετά τον γύρο $i$ είναι ακριβώς το καλύτερο μονοπάτι $s \to t$ με το πολύ $i$ ακμές — γι' αυτό πέφτει σταδιακά, $\infty \to 20 \to 10 \to 6$ , ανακαλύπτοντας κάθε γύρο ένα μονοπάτι με μία ακμή παραπάνω:

Bellman-Ford βήμα-βήμα — οι γύροι γεμίζουν τον πίνακα

Γύρος 0

Ζητάμε τις συντομότερες αποστάσεις προς το t. M[i, v] = καλύτερο v→t μονοπάτι με ≤ i ακμές.

M[i,v]

i=0

∞

i=1

i=2

i=3

i=4

Πορτοκαλί = βελτιώθηκε σε αυτόν τον γύρο · πράσινο = η τελική απόσταση s→t.

Αρχικοποίηση (γύρος 0). M[0, t] = 0 — η t απέχει 0 από τον εαυτό της. Κάθε άλλη κορυφή ∞: δεν υπάρχει ακόμη μονοπάτι με 0 ακμές.

Βήμα 0 / 5

Βελτιώσεις

Κλειδί

Γραμμικός χώρος. Κράτα έναν μονοδιάστατο πίνακα $M [v]$ = το μήκος του καλύτερου $v \to t$ μονοπατιού που βρέθηκε ως τώρα. Μετά από $i$ γύρους, το $M [v]$ δεν είναι μεγαλύτερο από το συντομότερο μονοπάτι με $\leq i$ ακμές. Χώρος: $O (m + n)$ .
Παράλειψη. Μην εξετάζεις ακμή $(v, w)$ εκτός αν το $M [w]$ άλλαξε στον προηγούμενο γύρο — αλλιώς δεν θα δώσει τίποτα νέο.
Πρόωρος τερματισμός. Αν σε έναν ολόκληρο γύρο καμία τιμή δεν άλλαξε, σταμάτα — έχεις συγκλίνει. (Αν ύστερα από $n - 1$ γύρους κάτι ακόμα αλλάζει, υπάρχει αρνητικός κύκλος.)

Με αυτές: $O (m + n)$ χώρος, $O (mn)$ χρόνος στη χειρότερη περίπτωση — αλλά συχνά πολύ ταχύτερα.

Κάρτα μνήμης — Ανεξάρτητο σύνολο σε δέντρο

Λέξεις-κλειδιά

υποπροβλήματα = υποδέντραδύο τιμές: A[v], B[v]υπολογισμός φύλλα → ρίζαA[v] = max{B[v], χ(v)+ΣB}O(n)

Τα βήματα στο μυαλό σου

1Για κάθε κορυφή v κράτα δύο τιμές: A[v] (η v ελεύθερη) και B[v] (η v έξω).

2Φύλλο: B = 0, A = χ.

3B[v] = Σ A[παιδιών]· A[v] = max{ B[v], χ(v) + Σ B[παιδιών] }.

4Υπολόγισέ τα από τα φύλλα προς τη ρίζα· η απάντηση είναι το A[ρίζα].

Πολυπλοκότητα

O(n)

Κλασική παγίδα

Μία τιμή ανά κορυφή δεν αρκεί — η απάντηση εξαρτάται από το ΑΝ η v είναι μέσα. Γι' αυτό δύο τιμές. Στα γενικά γραφήματα το πρόβλημα είναι NP-δύσκολο· μόνο η δομή του δέντρου το κάνει εύκολο.

Κάρτα μνήμης — Bellman-Ford

Λέξεις-κλειδιά

αρνητικά βάρη επιτρεπτάOPT(i, v) = ≤ i ακμέςn−1 γύροιαρνητικός κύκλος → καμία λύσηΘ(mn)

Τα βήματα στο μυαλό σου

1OPT(i, v) = μήκος συντομότερου v→t μονοπατιού με το πολύ i ακμές.

2Αναδρομή: min{ OPT(i−1,v), min στις ακμές (v,w) του ℓ(v,w) + OPT(i−1,w) }.

3Χωρίς αρνητικό κύκλο η συντομότερη διαδρομή είναι απλή → n−1 ακμές αρκούν.

4Η απάντηση για κάθε v είναι το M[n−1, v].

Πολυπλοκότητα

Θ(mn)

Κλασική παγίδα

Ο Dijkstra ΔΕΝ δουλεύει με αρνητικά βάρη — και η προσθήκη σταθεράς δεν βοηθάει (μια πολυάκμη διαδρομή κερδίζει τη σταθερά πολλές φορές). Αν υπάρχει αρνητικός κύκλος στη διαδρομή, ΔΕΝ υπάρχει συντομότερο μονοπάτι.

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

Βάλε στη σειρά τα βήματα του Bellman-Ford:

Βάλε τα βήματα στη σειρά

Ο αλγόριθμος Bellman-Ford, από την πρώτη ενέργεια στην τελευταία.

Σύρε τις γραμμές για αναδιάταξη — ή χρησιμοποίησε τα βελάκια.

1.Σε κάθε γύρο, για κάθε κορυφή v, ξεκίνα από την προηγούμενη τιμή M[i−1, v].

2.Επανάλαβε για i = 1 έως n−1 γύρους.

3.Μετά από n−1 γύρους, το M[n−1, v] είναι η συντομότερη v→t απόσταση.

4.Για κάθε εξερχόμενη ακμή (v, w), δοκίμασε τη βελτίωση ℓ(v,w) + M[i−1, w].

5.Θέσε M[0, t] = 0 και M[0, v] = ∞ για κάθε άλλη κορυφή v.

6.Κράτα το ελάχιστο ως νέα τιμή M[i, v].

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

Συμπλήρωσε τα κενά

Οι δύο αλγόριθμοι της τελευταίας διάλεξης σε τέσσερις λέξεις-κλειδιά.

Στο ανεξάρτητο σύνολο σε δέντρο, τα υποπροβλήματα είναι και κρατάμε τιμές ανά κορυφή. Ο Bellman-Ford λύνει συντομότερες διαδρομές ακόμα και με βάρη, παραμετροποιώντας το υποπρόβλημα με το πλήθος των της διαδρομής.

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

DP πέρα από τον πίνακα — δέντρα και γραφήματα

Σινιάλα στην εκφώνηση«πρόβλημα βελτιστοποίησης σε δέντρο»«συντομότερες διαδρομές με αρνητικά βάρη»«το «προφανές» υποπρόβλημα δεν έχει σειρά»

Ο δυναμικός προγραμματισμός δεν περιορίζεται σε πίνακες 1D/2D:

Σε δέντρο, το φυσικό υποπρόβλημα είναι ένα υποδέντρο. Υπολόγισε από τα φύλλα προς τη ρίζα.
Αν η απάντηση εξαρτάται από μια διακριτή «κατάσταση» της ρίζας του υποπροβλήματος (μέσα / έξω), κράτα μία τιμή ανά κατάσταση — εδώ $A [v]$ , $B [v]$ .
Σε γράφημα με κύκλους δεν υπάρχει φυσική σειρά υποπροβλημάτων. Λύση: παραμετροποίησε με κάτι που αυξάνει μονότονα — π.χ. το πλήθος ακμών (Bellman-Ford).
Πάντα οι ίδιες 4 ερωτήσεις (L14): τι είναι υποπρόβλημα, ποια η αναδρομή, με ποια σειρά υπολογίζω, πώς ανακτώ τη λύση.

Ραντάρ εξετάσεων

DP σε δέντρο — όρισε τα υποπροβλήματα στα υποδέντρα, με τιμές ανά κατάστασησυχνό

Bellman-Ford — τρέξε τον και υπολόγισε τις συντομότερες αποστάσειςσυχνό

Δες το στις ασκήσειςpt4-th1-q3

Γιατί ο Dijkstra αποτυγχάνει με αρνητικά βάρη — αντιπαράδειγμαπιθανό

Αρνητικοί κύκλοι: γιατί καταργούν τη συντομότερη διαδρομή, και πώς εντοπίζονταιπιθανό

Δες το στις ασκήσειςpt1-th2-a

Ανεξάρτητο σύνολο μέγιστου βάρους σε δέντρο σε O(n)πιθανό

Ταξινόμηση αλγορίθμων: άπληστος vs DP — διαγνωστικό «κλείδωμα ή πίνακας;»συχνό

Σ/Λ ερωτήσεις τύπου «είναι ο X άπληστος;» θέλουν το διαγνωστικό «μία αμετάκλητη απόφαση το βήμα, ή νέα γραμμή που διαβάζει την προηγούμενη;»

Δες το στις ασκήσειςpt4-th1-q3

Διπλή αναδρομή σε DAG — count + sum για μέσο όρο πάνω σε όλα τα μονοπάτιαπιθανό

Όταν θες μέσο όρο πάνω σε ολόκληρη οικογένεια (μονοπάτια, βέλτιστες λύσεις, αναμενόμενη τιμή), τρέξε ΔΥΟ παράλληλες αναδρομές σε λοκ-στεπ.

Δες το στις ασκήσειςfront-set-8-ask1

Τι μάθαμε

Τι κρατάμε από αυτή τη διάλεξη

Ανεξάρτητο σύνολο σε δέντρα — DP με υποπροβλήματα τα υποδέντρα. Δύο τιμές ανά κορυφή: $A [v]$ (η $v$ ελεύθερη) και $B [v]$ (η $v$ έξω). $B [v] = \sum A [v_{i}]$ , $A [v] = max {B [v], χ (v) + \sum B [v_{i}]}$ . $O (n)$ .
Ο Dijkstra αποτυγχάνει με αρνητικά βάρη· η προσθήκη σταθεράς δεν βοηθάει.
Αρνητικός κύκλος → δεν υπάρχει συντομότερη διαδρομή· αλλιώς υπάρχει και είναι απλή ( $\leq n - 1$ ακμές).
Bellman-Ford — $OPT (i, v)$ = συντομότερο $v \to t$ μονοπάτι με $\leq i$ ακμές. Αναδρομή: $min {OPT (i - 1, v), min_{(v, w)} (ℓ_{v w} + OPT (i - 1, w))}$ . Απάντηση στο $M [n - 1, v]$ .
$Θ (mn)$ χρόνος· με μονοδιάστατο πίνακα, παράλειψη αμετάβλητων κορυφών και πρόωρο τερματισμό → $O (m + n)$ χώρος.

Επόμενο

🔥 Σώσε το εξάμηνο

Ασκήσεις από εξετάσεις

Από τη θεωρία στην εξεταστική

19 άσκησεις που χρησιμοποιούν ως τελευταίο εργαλείο αυτή τη διάλεξη. Οι πρόσφατες εξεταστικές (2024/2025) φέρουν badge προτεραιότητας.

Παλαιό θέμαΙούνιος 2025Θέμα Εξετάσεων 2025Θέμα 2.13%Δυναμικός προγραμματισμόςΕύκολο

Ιούνιος 2025 · Θέμα 2.1 — Ανίχνευση αρνητικού κύκλου

Ποιον αλγόριθμο χρησιμοποιούμε για να αποφασίσουμε αν ένα κατευθυνόμενο γράφημα έχει αρνητικό κύκλο; (Αρκεί να τον αναφέρεις ονομαστικά.)

Απαιτεί:L17 · DP IV (DP on graphs)

Παλαιό θέμαΣεπτέμβριος 2024Θέμα Εξετάσεων 2024Θέμα 1 — Πρόταση 34%Δυναμικός προγραμματισμόςΕύκολο

Σεπτέμβριος 2024 · Θέμα 1.3 — Σ/Λ: ο Bellman-Ford είναι άπληστος;

Χαρακτήρισε (Σ)ωστό ή (Λ)άθος: «Ο αλγόριθμος Bellman-Ford ανήκει στην κατηγορία των άπληστων αλγορίθμων.»

Απαιτεί:L17 · DP IV (DP on graphs)

Από φροντιστήριοΦροντιστήριο 2023–24Άσκηση 1Δυναμικός προγραμματισμόςΜέτριο

Φροντιστηριακό Σετ #8 · Άσκηση 1 — Μέσο κόστος όλων των μονοπατιών σε DAG

Εύρεση του μέσου κόστους όλων των μονοπατιών, σε έναν κατευθυνόμενο ακυκλικό γράφο με βάρη $G = (V, E)$ , από μία κορυφή έναρξης $s$ προς μία κορυφή $t$ .

Απαιτεί:L17 · DP IV (DP on graphs)

Από φροντιστήριοΦροντιστήριο 2023–24Δυναμικός προγραμματισμόςΔύσκολο