Αλγόριθμοι και Συνδυαστική Βελτιστοποίηση — Σεπτέμβριος 2019

Η μεταγραφή προέρχεται από τις φωτογραφίες 84160576_2219682761671364_6327315777170964480_n.jpg (σελίδα 1) και 84024861_2219682721671368_6378002691980787712_n.jpg (σελίδα 2).

84160576_2219682761671364_6327315777170964480_n.jpg

Αλγόριθμοι και Συνδυαστική Βελτιστοποίηση

Εξέταση Σεπτεμβρίου 2019 [28.08.2019]

1. (20%) Θεωρείστε το δίκτυο του παρακάτω σχήματος, στο οποίο οι αριθμοί που συσχετίζονται με τις ακμές του αναπαριστούν χωρητικότητα. Στο δίκτυο αυτό ζητείται να βρείτε τη μέγιστη ροή εφαρμόζοντας τον αλγόριθμο της συντομότερης διαδρομής επαύξησης (shortest augmenting path). Ο αλγόριθμος θα εφαρμόζεται με τον περιορισμό ότι κάθε φορά που ξεκινάει από την s να βρει μια διαδρομή διέλευσης (admissible path), θα θεωρεί την (s, x) σαν πρώτη ακμή για όσο διάστημα η συγκεκριμένη ακμή αποτελεί ακμή διέλευσης (admissible edge) στο υπολειπόμενο δίκτυο (residual network), αλλιώς θα θεωρεί την (s, z) σαν πρώτη ακμή. Να δείξετε, με τη

[Σχήμα: κατευθυνόμενο δίκτυο G με κόμβους s, x, y, z, w, t. Χωρητικότητες ακμών: s→x 9, s→z 9, x→y 6, z→x 5, x→w 5, y→w 5, y→t 8, z→w 6, w→t 8.]

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

1. (20%) Θεωρήστε το δίκτυο του παρακάτω σχήματος, στο οποίο οι αριθμοί που συσχετίζονται με τις ακμές του αναπαριστούν χωρητικότητα. Στο δίκτυο αυτό ζητείται να βρείτε τη μέγιστη ροή εφαρμόζοντας τον αλγόριθμο της προρροής-ώθησης (preflow-push).

[Σχήμα: κατευθυνόμενο δίκτυο με κόμβους s, a, b, t. Χωρητικότητες ακμών: s→a 14, s→b 10, a→t 9, a→b 6, b→t 11.]

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

(15%) Έστω G = (V,E) (|V| = n, |E| = m) ένα κατευθυνόμενο γράφημα με μη αρνητικά κόστη στις ακμές του και έστω διακριτές κορυφές s1, s2, t1, t2 ∈ V. Σχεδιάστε έναν αλγόριθμο υπολογισμού μιας συντομότερης διαδρομής η οποία αρχίζει είτε από την s1 είτε από την s2 και καταλήγει είτε στην t1 είτε στην t2. Η απάντησή σας πρέπει να οπωσδήποτε να περιλαμβάνει

[Λείπει από τη φωτογραφία: το υπόλοιπο της πρότασης· συνεχίζεται στη 2η σελίδα («περιγραφή του αλγορίθμου…»)]

84024861_2219682721671368_6378002691980787712_n.jpg

Αλγόριθμοι και Συνδυαστική Βελτιστοποίηση, Εξέταση Σεπ. 2019

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

1. (15%) Προσδιορίστε ποιες από τις ακόλουθες προτάσεις είναι αληθείς και ποιες ψευδείς. Δικαιολογήστε την απάντησή σας είτε δίνοντας την απόδειξη όταν η πρόταση είναι αληθής, είτε δίνοντας ένα αντιπαράδειγμα όταν η πρόταση είναι ψευδής.

(α) Αν όλα τα κόστη ενός κατευθυνόμενου γραφήματος είναι διαφορετικά, τότε το δένδρο συντομότερων διαδρομών (με ρίζα μια οποιαδήποτε αρχική κορυφή \(s\)) είναι μοναδικό.
(β) Έστω \(G\) ένα κατευθυνόμενο γράφημα με θετικά κόστη ακμών, και έστω \(G'\) η μη κατευθυνόμενη εκδοχή του \(G\), δηλ. το \(G'\) προκύπτει αν απαλείψουμε (ή αγνοήσουμε) την κατεύθυνση κάθε ακμής του \(G\). Τότε, για οποιεσδήποτε δύο κορυφές \(u\) και \(v\), ισχύει ότι \(\delta_{G'}(u, v) = \delta_G(u, v)\) (δηλ. η απόσταση των \(u\) και \(v\) παραμένει ίδια και στα δύο γραφήματα).
(γ) Αν το κόστος κάθε ακμής σε ένα κατευθυνόμενο γράφημα αυξηθεί κατά \(k\) μονάδες, τότε οι αποστάσεις (συντομότερων διαδρομών) αυξάνονται κατά ένα πολλαπλάσιο του \(k\).

1. (20%) Δίνεται το γραμμικό πρόγραμμα \(\Pi\)

\[\min 3x_1 + 5x_2\]

υπό τις συνθήκες \(\Sigma\)

\[x_1 + x_2 \ge 8$$ $$3x_1 - x_2 \ge 0$$ $$2x_2 - x_1 \ge 0\]

(α) (5%) Έστω \(A\) το σύνολο των \((x_1, x_2)\) που ικανοποιούν τις συνθήκες \(\Sigma\). Είναι το \(A\) φραγμένο; Δηλαδή, υπάρχει δίσκος κέντρου \((x_1 = 0, x_2 = 0)\) και ακτίνας \(R\) για κάποιο \(R\) που περιέχει το \(A\); Αιτιολογήστε την απάντησή σας.
(β) (15%) Βρείτε τη βέλτιστη λύση του \(\Pi\), δηλαδή το \(z = \min\{3x_1 + 5x_2\}\) υπό τις συνθήκες \(\Sigma\), καθώς και ένα ζεύγος \((x_1, x_2)\) που αντιστοιχεί στη βέλτιστη λύση. Αιτιολογήστε την απάντησή σας.

Σημείωση: η φωτογραφία περιέχει χειρόγραφες απαντήσεις φοιτητή.

1. (10%) Δίνεται ένα διμερές συνεκτικό γράφημα \(G = (A \cup B, E)\) όπου \(A, B\) είναι τα σύνολα κορυφών των δύο μερών και \(E\) το σύνολο των ακμών. Δίνεται και ένα ταίριασμα \(M\) (matching) του \(G\) μεγέθους 37, καθώς και ένα σύνολο κορυφών \(\Sigma\) που αποτελεί κάλυψη κορυφών (vertex cover) του \(G\) μεγέθους 37. Πόσο μεγάλο είναι ένα ταίριασμα μεγίστου μεγέθους στο \(G\); Αιτιολογήστε την απάντησή σας.

Επιπλέον πηγές χωρίς μεταγραφή εδώ (λύσεις → 2019-09.solutions.md, ή διπλότυπες φωτογραφίες της ίδιας σελίδας): 84024861_2219682721671368_6378002691980787712_n.png

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

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

Προσοχή

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

AI λύσεις — 2019-09

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

Θέμα 1

Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή

Χρησιμοποιώ Edmonds–Karp (συντομότερη επαυξητική διαδρομή ως προς πλήθος ακμών) και την προτίμηση \(s\to x\) όσο αυτή έχει θετική υπολειπόμενη χωρητικότητα. Οι ακμές με μηδενική υπολειπόμενη χωρητικότητα παραλείπονται.

Αρχικό υπολειπόμενο δίκτυο: \(s\to x:9,\ s\to z:9,\ x\to y:6,\ x\to w:5,\ z\to x:5,\ z\to w:6,\ y\to w:5,\ y\to t:8,\ w\to t:8\).

1. Διαδρομή \(P_1=s\to x\to y\to t\), ποσότητα \(\Delta_1=\min(9,6,8)=6\). Μεταβολή: \(f_{sx}=f_{xy}=f_{yt}=6\). Υπολειπόμενο δίκτυο: \(s\to x:3,\ s\to z:9,\ x\to w:5,\ z\to x:5,\ z\to w:6,\ y\to w:5,\ y\to t:2,\ w\to t:8\), και αντίστροφες \(x\to s:6,\ y\to x:6,\ t\to y:6\).

2. Επειδή το \(s\to x\) είναι ακόμη ενεργό, επιλέγεται \(P_2=s\to x\to w\to t\), με \(\Delta_2=\min(3,5,8)=3\). Μεταβολή: \(f_{sx}=9,\ f_{xw}=3,\ f_{wt}=3\). Υπολειπόμενο δίκτυο: \(s\to z:9,\ x\to w:2,\ z\to x:5,\ z\to w:6,\ y\to w:5,\ y\to t:2,\ w\to t:5\), και αντίστροφες \(x\to s:9,\ y\to x:6,\ w\to x:3,\ t\to y:6,\ t\to w:3\).

3. Τώρα \(s\to x\) έχει υπολειπόμενη χωρητικότητα \(0\), άρα χρησιμοποιείται πρώτη ακμή \(s\to z\). Επιλέγεται \(P_3=s\to z\to w\to t\), με \(\Delta_3=\min(9,6,5)=5\). Μεταβολή: \(f_{sz}=5,\ f_{zw}=5,\ f_{wt}=8\). Τελικό υπολειπόμενο δίκτυο: \(s\to z:4,\ x\to w:2,\ z\to x:5,\ z\to w:1,\ y\to w:5,\ y\to t:2\), και αντίστροφες \(x\to s:9,\ z\to s:5,\ y\to x:6,\ w\to x:3,\ w\to z:5,\ t\to y:6,\ t\to w:8\).

Στο τελικό δίκτυο δεν υπάρχει διαδρομή \(s\to t\). Η μέγιστη ροή είναι [ 6+3+5=14. ] (Ελάχιστη τομή: \(\{s,x,z,w\}\) προς \(\{y,t\}\) με χωρητικότητα \(6+8=14\).)

Θέμα 2

Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή

Αρχικοποίηση preflow-push: \(h(s)=4,\ h(a)=h(b)=h(t)=0\), και κορεσμός των \(s\to a\), \(s\to b\). Άρα \(f_{sa}=14,\ f_{sb}=10\), πλεονάσματα \(e_a=14,e_b=10,e_t=0\). Αρχικά θετικές υπολειπόμενες ακμές: \(a\to s:14,\ a\to t:9,\ a\to b:6,\ b\to s:10,\ b\to t:11\).

Εκτελώ με σειρά ενεργών κορυφών \(a,b,a,b,\dots\) και καταγράφω τις αλλαγές στο υπολειπόμενο δίκτυο (οι υπόλοιπες χωρητικότητες μένουν ως έχουν):

Βήμα	Πράξη	\(h(a),h(b)\)	\(e_a,e_b,e_t\)	Αλλαγή στο υπολειπόμενο δίκτυο
1	relabel \(a\)	\(1,0\)	\(14,10,0\)	—
2	push \(a\to t\), \(\Delta=9\)	\(1,0\)	\(5,10,9\)	\(a\to t:0,\ t\to a:9\)
3	push \(a\to b\), \(\Delta=5\)	\(1,0\)	\(0,15,9\)	\(a\to b:1,\ b\to a:5\)
4	relabel \(b\)	\(1,1\)	\(0,15,9\)	—
5	push \(b\to t\), \(\Delta=11\)	\(1,1\)	\(0,4,20\)	\(b\to t:0,\ t\to b:11\)
6	relabel \(b\)	\(1,2\)	\(0,4,20\)	—
7	push \(b\to a\), \(\Delta=4\)	\(1,2\)	\(4,0,20\)	\(b\to a:1,\ a\to b:5\)
8	relabel \(a\)	\(3,2\)	\(4,0,20\)	—
9	push \(a\to b\), \(\Delta=4\)	\(3,2\)	\(0,4,20\)	\(a\to b:1,\ b\to a:5\)
10	relabel \(b\)	\(3,4\)	\(0,4,20\)	—
11	push \(b\to a\), \(\Delta=4\)	\(3,4\)	\(4,0,20\)	\(b\to a:1,\ a\to b:5\)
12	relabel \(a\)	\(5,4\)	\(4,0,20\)	—
13	push \(a\to s\), \(\Delta=4\)	\(5,4\)	\(0,0,20\)	\(a\to s:10,\ s\to a:4\)

Στο τέλος \(e_a=e_b=0\), άρα τερματισμός. Οι τελικές ροές είναι [ f_{sa}=10,\quad f_{sb}=10,\quad f_{at}=9,\quad f_{bt}=11,\quad f_{ab}=1. ] Η μέγιστη ροή είναι [ 9+11=20, ] (όση και η συνολική χωρητικότητα προς τον \(t\)).

Θέμα 3

Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή

Προσθέτουμε υπερπηγή \(S\) και υπερκαταβόθρα \(T\). Βάζουμε ακμές [ S\to s_1,\quad S\to s_2 ] με κόστος \(0\), και ακμές [ t_1\to T,\quad t_2\to T ] με κόστος \(0\). Τρέχουμε Dijkstra από το \(S\) στο νέο γράφημα, αφού όλα τα κόστη είναι μη αρνητικά. Η απόσταση \(d(T)\) ισούται με [ \min_{i,j\in{1,2}} \delta(s_i,t_j). ] Με δείκτες γονέα (parent pointers) ανακτούμε τη συντομότερη διαδρομή \(S\to T\), η οποία αντιστοιχεί σε διαδρομή \(s_i\rightsquigarrow t_j\) του αρχικού γραφήματος.

Ορθότητα: κάθε διαδρομή από κάποιο \(s_i\) σε κάποιο \(t_j\) επεκτείνεται σε διαδρομή \(S\to T\) ίδιου κόστους και αντίστροφα. Άρα η ελάχιστη \(S\)–\(T\) διαδρομή δίνει ακριβώς τη ζητούμενη ελάχιστη διαδρομή.

Πολυπλοκότητα: το νέο γράφημα έχει \(n+2\) κορυφές και \(m+4\) ακμές. Με Dijkstra και δυαδικό σωρό απαιτείται [ O((n+m)\log n) ] χρόνος και \(O(n+m)\) μνήμη.

Θέμα 4

Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή

(α) Ψευδής. Αντιπαράδειγμα: κορυφές \(s,a,b,t\) και ακμές [ s\to a:1,\quad a\to t:4,\quad s\to b:2,\quad b\to t:3. ] Όλα τα κόστη είναι διαφορετικά. Υπάρχουν δύο συντομότερες διαδρομές \(s\to t\) ίδιου κόστους \(5\): [ s\to a\to t,\qquad s\to b\to t. ] Άρα μπορούν να προκύψουν δύο διαφορετικά δένδρα συντομότερων διαδρομών, ανάλογα με τον γονέα του \(t\).

(β) Ψευδής. Αντιπαράδειγμα: κορυφές \(u,x,v\) και ακμές [ u\to x:1,\quad x\to v:10,\quad v\to u:1. ] Στο \(G\) είναι \(\delta_G(u,v)=1+10=11\). Στο μη κατευθυνόμενο \(G'\) υπάρχει ακμή \(u-v\) κόστους \(1\) (από την \(v\to u\)), άρα \(\delta_{G'}(u,v)=1\). Δεν είναι ίσες.

(γ) Ψευδής. Αντιπαράδειγμα με \(k=10\): έστω διαδρομή [ u\to a\to b\to c\to v ] με κόστη \(1,1,1,2\) (σύνολο \(5\), μήκος \(4\) ακμές) και άμεση ακμή [ u\to v:6. ] Αρχικά \(\delta(u,v)=5\). Αν αυξήσουμε κάθε κόστος κατά \(10\), η πρώτη διαδρομή γίνεται \(5+4\cdot 10=45\), ενώ η άμεση γίνεται \(6+10=16\). Άρα νέα απόσταση \(16\), αύξηση \(16-5=11\), που δεν είναι πολλαπλάσιο του \(10\).

Θέμα 5

Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή

(α) Το σύνολο \(A\) δεν είναι φραγμένο. Για παράδειγμα, για κάθε \(t\ge 4\), το σημείο \((x_1,x_2)=(t,t)\) ικανοποιεί όλες τις συνθήκες: [ x_1+x_2=2t\ge 8,\qquad 3x_1-x_2=2t\ge 0,\qquad 2x_2-x_1=t\ge 0. ] Καθώς \(t\to\infty\), το \((t,t)\) απομακρύνεται απεριόριστα από το \((0,0)\). Άρα δεν υπάρχει δίσκος πεπερασμένης ακτίνας που να περιέχει το \(A\).

(β) Θέτω [ s=x_1+x_2\ge 8,\qquad d=2x_2-x_1\ge 0. ] Τότε [ x_1=\frac{2s-d}{3},\qquad x_2=\frac{s+d}{3}. ] Άρα [ 3x_1+5x_2 =3\cdot\frac{2s-d}{3}+5\cdot\frac{s+d}{3} =\frac{11s+2d}{3} \ge \frac{11\cdot 8}{3} =\frac{88}{3}, ] αφού \(s\ge 8\) και \(d\ge 0\). Η ισότητα απαιτεί \(s=8\) και \(d=0\). Η \(d=0\) δίνει \(x_1=2x_2\), και μαζί με \(x_1+x_2=8\): [ 3x_2=8\Rightarrow x_2=\frac83,\qquad x_1=\frac{16}{3}. ] Το σημείο αυτό ικανοποιεί και τη δεύτερη συνθήκη: [ 3x_1-x_2=16-\frac83=\frac{40}{3}\ge 0. ] Άρα η βέλτιστη λύση είναι [ (x_1,x_2)=\left(\frac{16}{3},\frac83\right), ] με ελάχιστη τιμή [ z_{\min}=3\cdot\frac{16}{3}+5\cdot\frac83 =16+\frac{40}{3} =\frac{88}{3}. ]

Θέμα 6

Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή

Έχουμε ένα ταίριασμα \(M\) μεγέθους \(37\), άρα το μέγιστο ταίριασμα έχει μέγεθος τουλάχιστον \(37\). Έχουμε και κάλυψη κορυφών \(\Sigma\) μεγέθους \(37\), άρα η ελάχιστη κάλυψη κορυφών έχει μέγεθος το πολύ \(37\). Από το θεώρημα König για διμερή γραφήματα, [ \text{μέγιστο ταίριασμα}=\text{ελάχιστη κάλυψη κορυφών}. ] Επομένως το μέγιστο ταίριασμα έχει μέγεθος το πολύ \(37\). Συνδυάζοντας τις δύο ανισότητες, το μέγιστο ταίριασμα έχει ακριβώς μέγεθος [ 37. ] Μάλιστα το δοσμένο \(M\) είναι μέγιστο και η \(\Sigma\) ελάχιστη κάλυψη κορυφών.

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

---

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