Αλγόριθμοι και Συνδυαστική Βελτιστοποίηση — Ιούνιος 2022¶

Η μεταγραφή προέρχεται από το αρχείο 22.pdf (2 σελίδες).

22.pdf (σελ. 1-2)¶

Θέμα 1 (1,5Μ)

Έστω $G=(V,E)$ κατευθυνόμενο γράφημα, $n=|V|$ και $m=|E|$, με μη-αρνητικά κόστη στις ακμές του, στο οποίο έχουν υπολογιστεί συντομότερες διαδρομές από μία κορυφή $s$ προς όλες τις υπόλοιπες. Υποθέστε ότι προστίθεται μια νέα κορυφή $t$ στο γράφημα με κάποιες προσκείμενες (που έχουν το ένα άκρο τους στην $t$ και το άλλο σε κάποια άλλη κορυφή του $V$) με μη-αρνητικά κόστη. Περιγράψτε αλγόριθμο ενημέρωσης των αποστάσεων από την $s$ προς όλες τις υπόλοιπες κορυφές, δίνοντας και αιτιολογώντας την πολυπλοκότητά τους στις περιπτώσεις: α) Η κορυφή $t$ έχει μόνο εισερχόμενες προσκείμενες ακμές. β) Η κορυφή $t$ έχει εισερχόμενες και εξερχόμενες προσκείμενες ακμές.

Θέμα 2 (1,5Μ)

[Σχήμα: Κατευθυνόμενο γράφημα με κόμβους s, t και ενδιάμεσους κόμβους με κόστη/χωρητικότητες ακμών]

α) Ποια/ες είναι η/οι συντομότερη διαδρομές (Αρχικές διαδρομές $s-t$) β) Max-flow $s-t$ γ) Min-cut $s-t$

Θέμα 3 (1,5Μ)

αλγόριθμος πρόωσης-προώθησης (preflow-push)

[Σχήμα: Κατευθυνόμενο γράφημα με κόμβους s, t και ενδιάμεσους κόμβους με χωρητικότητες ακμών]

α) τελικό σχήμα β) Min-cut γ) τελική ετικέτα του b

Θέμα 4 (1,5Μ)

[Σχήμα: Κατευθυνόμενο γράφημα με κόμβους s, t και ενδιάμεσους κόμβους με χωρητικότητες ακμών]

α) Max-flow $s-t$ β) Min-cut $s-t$ γ) προώθηση 2 μονάδων στην διαδρομή $(s, x, a, b, y, t)$

Θέμα 5 (2,0Μ)

α) Δίνεται γραμμικό πρόγραμμα $\min (x_1 + x_2 + x_3)$ υπό τους περιορισμούς: $3x_1 + 4x_2 + 9x_3 - 36 = 0$, $x_1 \ge 0$, $x_2 \ge 0$, $x_3 \ge 0$

Αντιστοιχεί κάποιο από τα σημεία του συνόλου $\{(1,1,1), (12,0,0), (0,9,0), (0,0,4), (0,0,2)\}$ στην βέλτιστη λύση; Αιτιολογήστε την απάντηση σας.

β) Ένα γραμμικό πρόγραμμα έχει τους παρακάτω περιορισμούς $x_1 + x_2 + x_3 \le 13$ $2x_1 + 4x_2 + 5x_3 = 24$ $3x_1 + 3x_2 + 2x_3 \ge 30$

Αντιστοιχεί κάποιο από τα στοιχεία του συνόλου $\{2, 3, 5, \text{άπειρες}, \text{καμία}\}$ στο πλήθος των αποδεκτών/εφικτών λύσεων (feasible solutions) του παραπάνω γραμμικού προγράμματος;

Επιπλέον πηγές χωρίς μεταγραφή εδώ (λύσεις → 2022-06.solutions.md, ή διπλότυπες φωτογραφίες της ίδιας σελίδας): rn_image_picker_lib_temp_9e2e97da-f94d-4059-aa88-5e42684cb35e.jpg

Λύσεις (⚪ AI, μη επαληθευμένο)

Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (antigravity-gemini, deepseek-flash), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο

Προσοχή

Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.

AI λύσεις — 2022-06¶

Οι λύσεις γράφτηκαν από μοντέλα AI και δεν έχουν ελεγχθεί από άνθρωπο. Η αρίθμηση ακολουθεί το αρχείο θεμάτων.

Θέμα 1¶

Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: υψηλή

Έστω $d(v)$ οι γνωστές συντομότερες αποστάσεις από την $s$ στο αρχικό γράφημα $G$, και $c(u,v)\ge 0$ το κόστος της ακμής.

α) Η $t$ έχει μόνο εισερχόμενες ακμές $(u,t)$. Τότε καμία διαδρομή προς κορυφή του $V$ δεν μπορεί να περάσει από την $t$, αφού από την $t$ δεν εξέρχεται ακμή. Άρα [ d'(v)=d(v)\quad \forall v\in V, ] και [ d'(t)=\min_{(u,t)\in E'}{d(u)+c(u,t)}, ] με $d'(t)=\infty$ αν δεν υπάρχει τέτοια διαδρομή. Η ορθότητα προκύπτει επειδή μια διαδρομή $s\to t$ πρέπει τελευταία να χρησιμοποιήσει κάποια ακμή $(u,t)$.

Πολυπλοκότητα: $O(k)$ για τον υπολογισμό της $d'(t)$, όπου $k$ το πλήθος των εισερχόμενων ακμών της $t$, και $O(n+k)$ συνολικά αν γράψουμε και τις $n+1$ αποστάσεις.

β) Η $t$ έχει και εισερχόμενες και εξερχόμενες ακμές. Επειδή όλα τα κόστη είναι μη αρνητικά, μια ελάχιστη διαδρομή δεν χρειάζεται να περάσει από την $t$ περισσότερο από μία φορά. Αρχικά υπολογίζουμε [ D_t=\min_{(u,t)\in E'}{d(u)+c(u,t)}, ] δηλαδή τη συντομότερη απόσταση της $t$ μέσω των παλιών αποστάσεων. Στη συνέχεια εκτελούμε Dijkstra με αφετηρία την $t$, επιτρέποντας πρώτα τις εξερχόμενες ακμές $(t,u)$ και μετά τις ακμές του αρχικού $G$· δεν χρειάζεται να χαλαρώσουμε ξανά ακμές που εισέρχονται στην $t$, αφού τυχόν επιστροφή στην $t$ σχηματίζει μη αρνητικό κύκλο. Αν $\delta_t(v)$ είναι η απόσταση από την $t$ σε αυτό το γράφημα, τότε [ d'(v)=\min{d(v),\,D_t+\delta_t(v)}\quad \forall v\in V, \qquad d'(t)=D_t. ] Αν $D_t=\infty$, τότε $d'(v)=d(v)$ για κάθε $v\in V$ και $d'(t)=\infty$.

Πολυπλοκότητα: $O(k_{\mathrm{in}})$ για τον υπολογισμό της $D_t$ και $O((n+m+k_{\mathrm{out}})\log n)$ για τον Dijkstra, άρα συνολικά [ O\bigl(k_{\mathrm{in}}+(n+m+k_{\mathrm{out}})\log n\bigr), ] ή απλούστερα $O((n+m+k)\log n)$, όπου $k=k_{\mathrm{in}}+k_{\mathrm{out}}$ το πλήθος των νέων προσκείμενων ακμών.

Θέμα 2¶

Αξιοπιστία: λύθηκε με βάση τις φωτογραφίες του θέματος· μία λύση AI

Από το χειρόγραφο σχήμα στη σελίδα 1 του 22.pdf διαβάζονται οι κορυφές και οι χωρητικότητες: - Κορυφές: $s$ (πηγή), $a, x, b, v, y, u, t$ (απόληξη). - Χωρητικότητες: $(s, a) = 70$, $(s, x) = 30$, $(a, b) = 30$, $(a, v) = 20$, $(a, x) = 10$, $(x, a) = 10$, $(b, u) = 60$, $(u, t) = 40$, $(y, t) = 50$. - Για τις ακμές μεταξύ $v, t$ και $x, y$: - Τυπική ερμηνεία ροής (αριστερά προς δεξιά): $(v, t) = 60$, $(x, y) = 70$. - Κατά γράμμα σχεδίαση βελών (literal): $(t, v) = 60$, $(y, x) = 70$, και κάθετη ακμή $(v, y)$ με χωρητικότητα $\ge 20$.

α) Συντομότερες (αύξουσες) διαδρομές $s-t$: - Με κριτήριο το ελάχιστο πλήθος ακμών (hops): - Στην τυπική κατεύθυνση υπάρχουν δύο συντομότερες διαδρομές μήκους 3 ακμών: 1. $s \to a \to v \to t$ (μήκος 3 ακμές, χωρητικότητα στενωπού: $\min(70, 20, 60) = 20$) 2. $s \to x \to y \to t$ (μήκος 3 ακμές, χωρητικότητα στενωπού: $\min(30, 70, 50) = 30$) (Η διαδρομή $s \to a \to b \to u \to t$ έχει 4 ακμές). - Στην κατά γράμμα σχεδίαση (όπου οι ακμές προς $t$ είναι μόνο από $u$ και $y$): υπάρχουν διαδρομές 4 ακμών, π.χ. $s \to a \to b \to u \to t$ (χωρητικότητα 30) και $s \to a \to v \to y \to t$ (χωρητικότητα 20).

β) Max-flow $s-t$: - Τυπική ερμηνεία: Η μέγιστη ροή είναι 90. - Ροή 30 μέσω $s \to a \to b \to u \to t$ (κορεσμός $(a, b)$ στο 30). - Ροή 20 μέσω $s \to a \to v \to t$ (κορεσμός $(a, v)$ στο 20). - Ροή 30 μέσω $s \to x \to y \to t$ (κορεσμός $(s, x)$ στο 30). - Ροή 10 μέσω $s \to a \to x \to y \to t$ (χρήση της ακμής $(a, x) = 10$). - Συνολική ροή που φτάνει στο $t$: $30 + 20 + 40 = 90$. - Κατά γράμμα σχεδίαση: Η μέγιστη ροή είναι 50 (30 μέσω $s \to a \to b \to u \to t$ και 20 μέσω $s \to a \to v \to y \to t$).

γ) Min-cut $s-t$: - Τυπική ερμηνεία: $S = \{s, a\}$, $T = \{x, b, v, y, u, t\}$. - Χωρητικότητα αποκοπής: $c(s, x) + c(a, x) + c(a, b) + c(a, v) = 30 + 10 + 30 + 20 = 90$. - Επαλήθευση: $\text{Min-cut} = \text{Max-flow} = 90$. - Κατά γράμμα σχεδίαση: $S = \{s, a, x, v\}$, $T = \{b, u, y, t\}$ με χωρητικότητα $c(a, b) + c(v, y) = 30 + 20 = 50$.

Θέμα 3¶

Αξιοπιστία: λύθηκε με βάση τις φωτογραφίες του θέματος· μία λύση AI

Στο σχήμα του Θέματος 3 (σελ. 1 του 22.pdf) το δίκτυο έχει $n=4$ κορυφές: $s$ (πηγή), $b$ (άνω), $a$ (κάτω), $t$ (απόληξη). Χωρητικότητες ακμών: $c(s, b) = 8$, $c(s, a) = 12$, $c(a, b) = 4$, $c(b, t) = 10$, $c(a, t) = 8$.

Εκτέλεση αλγορίθμου Preflow-Push: 1. Αρχικοποίηση: - $d(s) = n = 4$, $d(a) = 0$, $d(b) = 0$, $d(t) = 0$. - Κορεσμός εξερχόμενων ακμών της πηγής $s$: - $f(s, b) = 8$, πλεόνασμα $e(b) = 8$. - $f(s, a) = 12$, πλεόνασμα $e(a) = 12$. 2. Προώθηση προς την απόληξη $t$: - Για να προωθηθεί ροή προς το $t$ ($d(t)=0$), οι κορυφές $a$ και $b$ πρέπει να επανασηματοδοτηθούν (relabel) σε ετικέτα $d = 1$: - Επανασηματοδότηση $d(b) = 1$, προώθηση 8 μονάδων στην $(b, t) \implies f(b, t) = 8, e(b) = 0$. - Επανασηματοδότηση $d(a) = 1$, προώθηση 8 μονάδων στην $(a, t) \implies f(a, t) = 8$ (κορεσμός), $e(a) = 4$. 3. Διαχείριση πλεονάσματος του $a$ ($e(a) = 4$): - Η $(a, t)$ είναι κορεσμένη. Επανασηματοδότηση $d(a) = d(b) + 1 = 2$. - Προώθηση 4 μονάδων στην $(a, b) \implies f(a, b) = 4, e(a) = 0, e(b) = 4$. 4. Διαχείριση πλεονάσματος του $b$ ($e(b) = 4$): - Υπολειπόμενη χωρητικότητα $(b, t)$ είναι $10 - 8 = 2$. Επειδή $d(b)=1 = d(t)+1$, προωθούνται 2 μονάδες στην $(b, t) \implies f(b, t) = 10$ (κορεσμός), $e(b) = 2, e(t) = 18$. - Οι ακμές προς το $t$ είναι πλέον πλήρως κορεσμένες (συνολική ροή 18). 5. Επιστροφή του εναπομείναντος πλεονάσματος (2 μονάδες) προς την πηγή $s$: - Αν το πλεόνασμα επιστραφεί μέσω της διαδρομής $b \to a \to s$: - Επανασηματοδότηση $d(b) = d(a) + 1 = 3$, ώθηση 2 μονάδων πίσω στο $a \implies f(a, b) = 2, e(b) = 0, e(a) = 2$. - Επανασηματοδότηση $d(a) = d(s) + 1 = 5$, ώθηση 2 μονάδων πίσω στο $s \implies f(s, a) = 10, e(a) = 0$. - Τελικές ετικέτες: $d(b) = 4$ (ή 3), $d(a) = 5$. - Αν το πλεόνασμα επιστραφεί απευθείας από το $b$ προς το $s$ ($b \to s$): - Επανασηματοδότηση $d(b) = d(s) + 1 = 5$, ώθηση 2 μονάδων πίσω στο $s \implies f(s, b) = 6, e(b) = 0$. - Τελική ετικέτα $d(b) = 5$.

α) Τελικό σχήμα (Ροές / Υπολειπόμενο Δίκτυο): - Τελικές ροές: - $f(s, b) = 8$, $f(s, a) = 10$, $f(a, b) = 2$, $f(b, t) = 10$, $f(a, t) = 8$ (Μέγιστη ροή = 18). (ή ισοδύναμα με επιστροφή από το $b$: $f(s, b) = 6$, $f(s, a) = 12$, $f(a, b) = 4$, $f(b, t) = 10$, $f(a, t) = 8$). - Υπολειπόμενες χωρητικότητες $u_f$: - $u_f(b, t) = 0$, $u_f(a, t) = 0$ (κορεσμένες ακμές προς την απόληξη).

β) Min-cut: - $S = \{s, a, b\}$ και $T = \{t\}$. - Χωρητικότητα ελάχιστης αποκοπής: $c(b, t) + c(a, t) = 10 + 8 = \mathbf{18}$.

γ) Τελική ετικέτα του $b$: - $d(b) = \mathbf{4}$ (αν το πλεόνασμα επιστρέψει μέσω $a$) ή $d(b) = \mathbf{5}$ (αν επανασηματοδοτηθεί για να ωθήσει απευθείας στο $s$).

Θέμα 4¶

Αξιοπιστία: λύθηκε με βάση τις φωτογραφίες του θέματος· μία λύση AI

Στο σχήμα του Θέματος 4 (σελ. 2 του 22.pdf) το δίκτυο έχει κορυφές $s, x, a, b, y, t$ και χωρητικότητες: - $(s, a) = 10$ - $(s, x) = 12$ - $(x, a) = 6$ - $(x, y) = 3$ - $(a, b) = 8$ - $(a, y) = 2$ - $(b, y) = 2$ - $(b, t) = 5$ - $(y, t) = 10$

α) Max-flow $s-t$: - Η τιμή της μέγιστης ροής είναι $|f_{\max}| = 12$. - Μια εφικτή μέγιστη ροή είναι: - $f(s, a) = 3, f(s, x) = 9$ (συνολική έξοδος από $s = 12$) - $f(x, a) = 6, f(x, y) = 3$ (διατήρηση στο $x$: $9 = 6 + 3$) - $f(a, b) = 7, f(a, y) = 2$ (διατήρηση στο $a$: $3 + 6 = 7 + 2 = 9$) - $f(b, t) = 5, f(b, y) = 2$ (διατήρηση στο $b$: $7 = 5 + 2$) - $f(y, t) = 7$ (διατήρηση στο $y$: $3 + 2 + 2 = 7$) - Συνολική είσοδος στο $t$: $f(b, t) + f(y, t) = 5 + 7 = 12$.

β) Min-cut $s-t$: - Η ελάχιστη αποκοπή είναι η $(S, T)$ με: $$S = \{s, x, a, b\}, \quad T = \{y, t\}$$ - Οι ακμές που διασχίζουν την αποκοπή από το $S$ στο $T$ είναι: - $(x, y)$ με χωρητικότητα 3 - $(a, y)$ με χωρητικότητα 2 - $(b, y)$ με χωρητικότητα 2 - $(b, t)$ με χωρητικότητα 5 - Χωρητικότητα αποκοπής: $$c(S, T) = 3 + 2 + 2 + 5 = \mathbf{12}$$ Επαλήθευση: $\text{Min-cut} = \text{Max-flow} = 12$.

γ) Προώθηση 2 μονάδων στη διαδρομή $(s, x, a, b, y, t)$: Η διαδρομή αποτελείται από τις ακμές $(s, x) \to (x, a) \to (a, b) \to (b, y) \to (y, t)$. Οι αρχικές χωρητικότητες είναι $(12, 6, 8, 2, 10)$, με στενωπό (bottleneck) την ακμή $(b, y)$ με χωρητικότητα 2. Προωθώντας 2 μονάδες ροής κατά μήκος της διαδρομής, οι νέες ροές και οι υπολειπόμενες χωρητικότητες $u_f$ διαμορφώνονται ως εξής: 1. Ακμή $(s, x)$: ροή $f(s, x) = 2 \implies u_f(s, x) = 12 - 2 = \mathbf{10}$, και αντίστροφη $u_f(x, s) = \mathbf{2}$. 2. Ακμή $(x, a)$: ροή $f(x, a) = 2 \implies u_f(x, a) = 6 - 2 = \mathbf{4}$, και αντίστροφη $u_f(a, x) = \mathbf{2}$. 3. Ακμή $(a, b)$: ροή $f(a, b) = 2 \implies u_f(a, b) = 8 - 2 = \mathbf{6}$, και αντίστροφη $u_f(b, a) = \mathbf{2}$. 4. Ακμή $(b, y)$: ροή $f(b, y) = 2 \implies u_f(b, y) = 2 - 2 = \mathbf{0}$ (πλήρως κορεσμένη), και αντίστροφη $u_f(y, b) = \mathbf{2}$. 5. Ακμή $(y, t)$: ροή $f(y, t) = 2 \implies u_f(y, t) = 10 - 2 = \mathbf{8}$, και αντίστροφη $u_f(t, y) = \mathbf{2}$.

Όλες οι υπόλοιπες ακμές διατηρούν μηδενική ροή και τις αρχικές τους υπολειπόμενες χωρητικότητες: $u_f(s, a) = 10$, $u_f(x, y) = 3$, $u_f(a, y) = 2$, $u_f(b, t) = 5$.

Θέμα 5¶

Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: υψηλή

α) Ο περιορισμός γράφεται $3x_1+4x_2+9x_3=36$ με $x_i\ge 0$. Ελέγχουμε τα σημεία: - $(1,1,1)$: $3+4+9=16\ne 36$, μη εφικτό. - $(12,0,0)$: $36$, εφικτό, τιμή $12$. - $(0,9,0)$: $36$, εφικτό, τιμή $9$. - $(0,0,4)$: $36$, εφικτό, τιμή $4$. - $(0,0,2)$: $18\ne 36$, μη εφικτό.

Για κάθε εφικτό σημείο, [ 36=3x_1+4x_2+9x_3\le 9x_1+9x_2+9x_3=9(x_1+x_2+x_3), ] άρα $x_1+x_2+x_3\ge 4$. Ισότητα έχουμε μόνο όταν $x_1=x_2=0$, οπότε $x_3=4$. Άρα η μοναδική βέλτιστη λύση είναι η $(0,0,4)$. Επομένως από το δοσμένο σύνολο, το σημείο $(0,0,4)$ αντιστοιχεί στη βέλτιστη λύση.

β) Το πλήθος των εφικτών λύσεων είναι άπειρες. Πράγματι, για $\lambda\in[0,12/17]$ θεωρούμε [ (x_1,x_2,x_3)=\left(12-\frac{9}{2}\lambda,\ \lambda,\ \lambda\right). ] Τότε [ 2x_1+4x_2+5x_3 =2\left(12-\frac{9}{2}\lambda\right)+4\lambda+5\lambda =24, ] [ x_1+x_2+x_3=12-\frac{9}{2}\lambda+2\lambda =12-\frac{5}{2}\lambda\le 13, ] και [ 3x_1+3x_2+2x_3 =3\left(12-\frac{9}{2}\lambda\right)+3\lambda+2\lambda =36-\frac{17}{2}\lambda\ge 30 ] για $\lambda\le 12/17$. Επίσης $x_i\ge 0$ στο διάστημα αυτό. Άρα υπάρχουν άπειρες εφικτές λύσεις, οπότε η σωστή επιλογή είναι άπειρες.

✔ Επιβεβαίωσε · ✖ Βρήκα λάθος

✖ Βρήκα λάθος στη μεταγραφή