Αλγόριθμοι και Συνδυαστική Βελτιστοποίηση — Ιανουάριος 2024¶
Η μεταγραφή προέρχεται από τη φωτογραφία 2024-01-07_000230.png.
2024-01-07_000230.png¶
- (20%) Θεωρήστε το δίκτυο του παρακάτω σχήματος, στο οποίο οι αριθμοί που συσχετίζονται με τις ακμές του αναπαριστούν χωρητικότητα. Στο δίκτυο αυτό ζητείται να βρείτε τη μέγιστη ροή εφαρμόζοντας τον αλγόριθμο της προώθησης-ώθησης (preflow-push).
[Σχήμα: κατευθυνόμενο δίκτυο με κορυφές s, a, b, t. Χωρητικότητες ακμών: s→a 14, s→b 10, a→b 6, a→t 9, b→t 11.]
Να δείξετε, με τη βοήθεια σχημάτων, την εκτέλεση του αλγορίθμου στο παραπάνω δίκτυο. Πιο συγκεκριμένα, να δείξετε το υπολειπόμενο δίκτυο είτε (α) μετά από μια ώθηση ροής κατά μήκος μιας ακμής διέλευσης καταγράφοντας ρητά την ποσότητα ροής που ωθείται, καθώς και το νέο πλεόνασμα των κορυφών, είτε (β) μετά από ανανέωση ετικέτας (relabeling) απόστασης κάποιας κορυφής, καταγράφοντας ρητά την κορυφή και τη νέα της απόσταση.
Λύσεις (⚪ AI, μη επαληθευμένο)
Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (deepseek-flash), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο
Προσοχή
Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.
AI λύσεις — 2024-01¶
Οι λύσεις γράφτηκαν από μοντέλα AI και δεν έχουν ελεγχθεί από άνθρωπο. Η αρίθμηση ακολουθεί το αρχείο θεμάτων.
Θέμα 2¶
Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: υψηλή
Θέτω \(e(v)=\text{ροή εισόδου}-\text{ροή εξόδου}\) και \(h(v)\) την ετικέτα απόστασης. Χρησιμοποιώ την τυπική αρχικοποίηση \(h(s)=4\), \(h(a)=h(b)=h(t)=0\) και κορεσμό των ακμών εξόδου της \(s\): \(f_{sa}=14,\ f_{sb}=10\). Συμβολίζω με \(R\) το υπολειπόμενο δίκτυο και γράφω μόνο τις ακμές με θετική υπολειπόμενη χωρητικότητα.
Αρχική κατάσταση.
[
e(s,a,b,t)=(-24,14,10,0),\quad h(s,a,b,t)=(4,0,0,0),
]
[
R_0={a\to s:14,\ b\to s:10,\ a\to b:6,\ a\to t:9,\ b\to t:11}.
]
-
Relabel \(a\): Δεν υπάρχει αποδεκτή ακμή.
[ h(a)=1+\min{h(s),h(b),h(t)}=1+\min{4,0,0}=1. ] Το \(R_1=R_0\) παραμένει ίδιο. -
Push \(a\to t\):
[ \delta=\min(e(a),c_f(a,t))=\min(14,9)=9. ] Νέα \(e(s,a,b,t)=(-24,5,10,9)\).
[ R_2={a\to s:14,\ b\to s:10,\ a\to b:6,\ t\to a:9,\ b\to t:11}. ] -
Push \(a\to b\):
[ \delta=\min(5,6)=5. ] Νέα \(e(s,a,b,t)=(-24,0,15,9)\).
[ R_3={a\to s:14,\ b\to s:10,\ a\to b:1,\ b\to a:5,\ t\to a:9,\ b\to t:11}. ] -
Relabel \(b\):
[ h(b)=1+\min{h(s),h(a),h(t)}=1+\min{4,1,0}=1. ] \(R_4=R_3\). -
Push \(b\to t\):
[ \delta=\min(15,11)=11. ] Νέα \(e(s,a,b,t)=(-24,0,4,20)\).
[ R_5={a\to s:14,\ b\to s:10,\ a\to b:1,\ b\to a:5,\ t\to a:9,\ t\to b:11}. ] -
Relabel \(b\): Αφού \(c_f(b,t)=0\),
[ h(b)=1+\min{h(s),h(a)}=1+\min{4,1}=2. ] \(R_6=R_5\). -
Push \(b\to a\):
[ \delta=\min(4,5)=4. ] Νέα \(e(s,a,b,t)=(-24,4,0,20)\).
[ R_7={a\to s:14,\ b\to s:10,\ a\to b:5,\ b\to a:1,\ t\to a:9,\ t\to b:11}. ] -
Relabel \(a\): Αφού \(c_f(a,t)=0\),
[ h(a)=1+\min{h(s),h(b)}=1+\min{4,2}=3. ] \(R_8=R_7\). -
Push \(a\to b\):
[ \delta=\min(4,5)=4. ] Νέα \(e(s,a,b,t)=(-24,0,4,20)\).
[ R_9={a\to s:14,\ b\to s:10,\ a\to b:1,\ b\to a:5,\ t\to a:9,\ t\to b:11}. ] -
Relabel \(b\):
[ h(b)=1+\min{h(s),h(a)}=1+\min{4,3}=4. ] \(R_{10}=R_9\). -
Push \(b\to a\):
[ \delta=\min(4,5)=4. ] Νέα \(e(s,a,b,t)=(-24,4,0,20)\).
[ R_{11}={a\to s:14,\ b\to s:10,\ a\to b:5,\ b\to a:1,\ t\to a:9,\ t\to b:11}. ] -
Relabel \(a\):
[ h(a)=1+\min{h(s),h(b)}=1+\min{4,4}=5. ] \(R_{12}=R_{11}\). -
Push \(a\to b\):
[ \delta=\min(4,5)=4. ] Νέα \(e(s,a,b,t)=(-24,0,4,20)\).
[ R_{13}={a\to s:14,\ b\to s:10,\ a\to b:1,\ b\to a:5,\ t\to a:9,\ t\to b:11}. ] -
Relabel \(b\):
[ h(b)=1+\min{h(s),h(a)}=1+\min{4,5}=5. ] \(R_{14}=R_{13}\). -
Push \(b\to s\):
[ \delta=\min(e(b),c_f(b,s))=\min(4,10)=4. ] Νέα \(e(s,a,b,t)=(-20,0,0,20)\).
[ R_{15}={a\to s:14,\ b\to s:6,\ s\to b:4,\ a\to b:1,\ b\to a:5,\ t\to a:9,\ t\to b:11}. ]
Τώρα \(e(a)=e(b)=0\), άρα δεν υπάρχουν ενεργές κορυφές εκτός από \(s,t\) και ο αλγόριθμος τερματίζει. Η τελική ροή είναι [ f_{sa}=14,\quad f_{sb}=6,\quad f_{ab}=5,\quad f_{at}=9,\quad f_{bt}=11, ] με τιμή [ |f|=f_{sa}+f_{sb}=14+6=20. ] Επιβεβαίωση με min-cut: η τομή \(\{s,a,b\}\) ως προς \(\{t\}\) έχει χωρητικότητα \(9+11=20\), άρα η μέγιστη ροή είναι \(20\).