Ημερολόγιο Τετάρτης 2/11/2022

Πιθανοθεωρητικός αλγόριθμος για εύρεση ενός min-cut ενός γραφήματος

Έχουμε ένα γράφημα $G$ και θέλουμε να διαμερίσουμε το σύνολο κορυφών του $V$ σε δύο μέρη $$ V = V_1 \cup V_2 $$ έτσι ώστε να ελαχιστοποιήσουμε το πλήθος των ακμών που ενώνουν μια ακμή του $V_1$ με μια ακμή του $V_2$. Αυτό είναι το πρόβλημα εύρεσης του min-cut.

Δεν είναι εύκολο πρόβλημα μια και το πλήθος των διαμερίσεων για $n$ κορυφές είναι της τάξης του $2^n$ οπότε ο προφανής αλγόριθμος (ελέγχουμε όλες τις διαμερίσεις) είναι εκθετικός και μη πρακτικός.

Είδαμε σήμερα ένα randomized αλγόριθμο που σε χρόνο της τάξης του $n^2$ μας βρίσκει ένα min-cut με πιθανότητα τουλάχιστον $\frac{1}{2n(n-1)}$. Είδαμε ότι αν επαναλάβουμε τον αλγόριθμο αυτό περίπου $n^2 \log n$ φορές (και κρατήσουμε το μικρότερο cut που βρούμε στις επαναλήψεις) τότε μπορούμε να μειώσουμε την πιθανότητα αποτυχίας σε κάτι πολύ μικρό (π.χ. $1/n$).

Ο αλγόριθμος σε λεπτομέρειες είναι εδώ.

Μετά από την ανάλυση του αλγορίθμου ασχοληθήκαμε με την υλοποίησή του και το ημιτελές πρόγραμμα που γράψαμε φαίνεται παρακάτω.

In [22]:
import numpy as np

n = 5 # πλήθος κορυφών

V = {} # λεξικό που θα έχει τα ονόματα των κορυφών ως κλειδιά και για κάθε κορυφή
       # θα έχει σε μια λίστα τους γείτονές της

# Αυτό θα είναι το γράφημα με το οποίο θα δουλέψουμε αρχικά
V = { '0': ['1', '3', '4'],
      '1': ['0', '2', '3'],
      '2': ['1', '3'],
      '3': ['0', '1', '2'],
      '4': ['0'] 
    }

W = V.copy() # φτιάχνουμε ένα αντίγραφο του γραφήματος το οποίο θα αλλάζει κατά τη διάρκεια του αλγορίθμου

# Θα κάνουμε συνολικά n-2 συμπτύξεις (contractions) ακμών, αφού θέλουμε να μείνουν 2 κορυφές στο
# τέλος και σε κάθε σύμπτυξη φεύγει μια κορυφή.
for i in range(n-2):
    EE = [] # λίστα με όλες τις ακμές μέσα, μια φορά την κάθε μια
    for j in W.keys(): 
        for v in W[j]:
            if [v, j] not in EE: # δεν προσθέτουμε την ακμή στην ΕΕ αν έχει ήδη μπει με την ανάποδη
                                 # σειρά κορυφών
                EE.append([j, v])
    E = len(EE) # E είναι ο αριθμός των ακμών
    e = np.random.randint(0, E) # τυχαία ακμή
    u = EE[e][0] # αρχική κορυφή της e
    v = EE[e][1] # τελική κορυφή της e