Αλγόριθμος του Μπίρκοφ

Από testwiki
Μετάβαση στην πλοήγηση Πήδηση στην αναζήτηση

Ο αλγόριθμος του Μπίρκοφ (επίσης γνωστός ως αλγόριθμος Μπίρκοφ-φον Νόιμαν) είναι ένας αλγόριθμος για τη διάσπαση ενός διστοχαστικού πίνακα σε έναν κυρτό συνδυασμό πινάκων μετατροπής. Δημοσιεύθηκε από τον Γκάρετ Μπίρκοφ το 1946[1][2]Πρότυπο:Rp Έχει πολλές εφαρμογές. Μια τέτοια εφαρμογή είναι για το πρόβλημα της δίκαιης τυχαίας κατανομής: δεδομένης μιας τυχαίας κατανομής αντικειμένων, ο αλγόριθμος του Μπίρκοφ μπορεί να την αποσυνθέσει σε μια κλήρωση σε προσδιοριστικές αναθέσεις.

Ορολογία

Ένας διστοχαστικός πίνακας (που ονομάζεται επίσης: διπλά-στοχαστικός) είναι ένας πίνακας στον οποίο όλα τα στοιχεία είναι μεγαλύτερα ή ίσα του 0 και το άθροισμα των στοιχείων σε κάθε γραμμή και στήλη ισούται με 1. Ένα παράδειγμα είναι ο ακόλουθος πίνακας 3 επί 3:

(0.20.30.50.60.20.20.20.50.3)

Ένας πίνακας μεταθέσεων είναι μια ειδική περίπτωση ενός διστοχαστικού πίνακα, στον οποίο κάθε στοιχείο είναι είτε 0 είτε 1 (έτσι υπάρχει ακριβώς ένα «1» σε κάθε γραμμή και κάθε στήλη). Ένα παράδειγμα είναι ο ακόλουθος πίνακας 3 επί 3:

(010001100)

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

0.2(010001100)+0.2(100010001)+0.1(010100001)+0.5(001100010)

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

Εργαλεία

Ένα σύνολο αντιμετάθεσης ενός n-προς-n πίνακα X είναι ένα σύνολο n καταχωρήσεων του X που περιέχει ακριβώς μία καταχώρηση από κάθε γραμμή και από κάθε στήλη. Ένα θεώρημα του Ντένες Κνούνιγκ αναφέρει ότι: [3][2]Πρότυπο:Rp

Κάθε διστοχαστικός πίνακας έχει ένα σύνολο μεταθέσεων στο οποίο όλες οι καταχωρήσεις είναι θετικές.

Το γράφημα θετικότητας ενός πίνακα n-προς-n X είναι ένα διμερές γράφημα με 2 n κορυφές, στο οποίο οι κορυφές από τη μία πλευρά είναι οι n γραμμές και οι κορυφές από την άλλη πλευρά είναι οι n στήλες, και υπάρχει ακμή μεταξύ μιας γραμμής και μιας στήλης αν η είσοδος σε αυτή τη γραμμή και τη στήλη είναι θετική. Ένα σύνολο μεταθέσεων με θετικές καταχωρήσεις είναι ισοδύναμο με ένα τέλειο ταίριασμα στο γράφημα θετικότητας. Ένα τέλειο ταίριασμα σε ένα διμερές γράφημα μπορεί να βρεθεί σε πολυωνυμικό χρόνο, π.χ. με τη χρήση οποιουδήποτε αλγορίθμου για ταίριασμα μέγιστης πληθικότητας. Το θεώρημα του Κνούνιγκ είναι ισοδύναμο με το ακόλουθο:

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

Ένας πίνακας ονομάζεται κλιμακωτός-διστοχαστικός αν όλα τα στοιχεία είναι μη αρνητικά και το άθροισμα κάθε γραμμής και στήλης ισούται με c, όπου c είναι κάποια θετική σταθερά. Με άλλα λόγια, είναι c επί ένα διστοχαστικό πίνακα. Δεδομένου ότι το γράφημα θετικότητας δεν επηρεάζεται από την κλιμάκωση:

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

Αλγόριθμος

Ο αλγόριθμος του Μπίρκοφ είναι ένας άπληστος αλγόριθμος[4]: βρίσκει άπληστα τις τέλειες αντιστοιχίες και τις αφαιρεί από την κλασματική αντιστοιχία. Λειτουργεί ως εξής.[5]Πρότυπο:Rp

  1. Έστω i = 1.
  2. Σχεδιάστε το γράφημα θετικότητας GX of X.
  3. Βρείτε ένα τέλειο ταίριασμα στο GX, που αντιστοιχεί σε ένα θετικό σύνολο μεταθέσεων στο X.
  4. Έστω z[i] > 0 η μικρότερη καταχώρηση στο σύνολο μεταθέσεων.
  5. Έστω P[i] ένας πίνακας μεταθέσεων με 1 στο θετικό σύνολο μεταθέσεων.
  6. Έστω X := X − z[i] P[i].
  7. Αν το X περιέχει μη μηδενικά στοιχεία, αφήστε i = i + 1 και επιστρέψτε στο βήμα 2.
  8. Διαφορετικά, επιστρέψτε το άθροισμα: z[1] P[1] + ... + z[2] P[2] + ... + z[i] P[i].

Ο αλγόριθμος είναι σωστός διότι, μετά το βήμα 6, το άθροισμα σε κάθε γραμμή και κάθε στήλη μειώνεται κατά z[i]. Επομένως, ο πίνακας X παραμένει κλιμακωτός-πιστοχαστικός. Επομένως, στο βήμα 3, υπάρχει πάντα μια τέλεια αντιστοίχιση.

Πολυπλοκότητα χρόνου εκτέλεσης

Με την επιλογή του z[i] στο βήμα 4, σε κάθε επανάληψη τουλάχιστον ένα στοιχείο του X γίνεται 0. Επομένως, ο αλγόριθμος πρέπει να τελειώσει μετά από το πολύ n2 βήματα. Ωστόσο, το τελευταίο βήμα πρέπει ταυτόχρονα να κάνει n στοιχεία 0, οπότε ο αλγόριθμος τελειώνει μετά από το πολύ n2 − n + 1 βήματα, το οποίο συνεπάγεται O(n2)

Το 1960, οι Τζόσνσον, Ντουλμάζ και Μέντελσον έδειξαν ότι ο αλγόριθμος του Μπίρκοφ τελειώνει στην πραγματικότητα μετά από το πολύ n2 − 2n + 2 βήματα, το οποίο είναι σφιχτό σε γενικές γραμμές (δηλαδή, σε ορισμένες περιπτώσεις μπορεί να απαιτούνται n2 − 2n + 2 πίνακες μεταθέσεων)[6].

Εφαρμογή στη δίκαιη κατανομή

Στο πρόβλημα της δίκαιης τυχαίας κατανομής, υπάρχουν n αντικείμενα και n άτομα με διαφορετικές προτιμήσεις για τα αντικείμενα. Απαιτείται να δοθεί ένα αντικείμενο σε κάθε άτομο. Για να επιτευχθεί η δίκαιη κατανομή, η κατανομή είναι τυχαία: για κάθε ζεύγος (άτομο, αντικείμενο) υπολογίζεται μια πιθανότητα, έτσι ώστε το άθροισμα των πιθανοτήτων για κάθε άτομο και για κάθε αντικείμενο να είναι 1. Η πιθανολογική-σειριακή διαδικασία μπορεί να υπολογίσει τις πιθανότητες έτσι ώστε κάθε πράκτορας, κοιτάζοντας τον πίνακα των πιθανοτήτων, να προτιμά τη σειρά των πιθανοτήτων του από τις σειρές όλων των άλλων ατόμων (αυτή η ιδιότητα ονομάζεται ζηλευτή-ευγένεια). Αυτό εγείρει το ερώτημα πώς μπορεί να εφαρμοστεί αυτή η τυχαιοποιημένη κατανομή στην πράξη; Δεν είναι δυνατόν να γίνει τυχαία κατανομή κάθε αντικειμένου ξεχωριστά, καθώς αυτό θα μπορούσε να οδηγήσει σε κατανομές στις οποίες κάποιοι άνθρωποι παίρνουν πολλά αντικείμενα ενώ άλλοι κανένα.

Εδώ είναι χρήσιμος ο αλγόριθμος του Μπίρκοφ. Ο πίνακας πιθανοτήτων, που υπολογίζεται από τον αλγόριθμο πιθανοτήτων-σειρών, είναι διστοχαστικός. Ο αλγόριθμος του Μπίρκοφ μπορεί να τον αποσυνθέσει σε έναν κυρτό συνδυασμό πινάκων μεταθέσεων. Κάθε πίνακας μεταθέσεων αντιπροσωπεύει μια προσδιοριστική κατανομή, στην οποία κάθε πράκτορας λαμβάνει ακριβώς ένα αντικείμενο. Ο συντελεστής κάθε τέτοιου πίνακα ερμηνεύεται ως πιθανότητα- με βάση τις υπολογισμένες πιθανότητες, είναι δυνατόν να επιλεγεί μια τυχαία ανάθεση και να υλοποιηθεί.

Επεκτάσεις

Το πρόβλημα του υπολογισμού της παραγοντοποιήσης Μπίρκοφ με τον ελάχιστο αριθμό όρων έχει αποδειχθεί ότι είναι NP-δύσκολο, αλλά είναι γνωστές κάποιες ευρετικές τεχνικές για τον υπολογισμό του[7][8] Το θεώρημα αυτό μπορεί να επεκταθεί για τον γενικό στοχαστικό πίνακα με προσδιοριστικούς πίνακες μετάβασης[9].

Οι Μπουντίς, Τσε, Κοτζίμα και Μίλγκρομ[10] γενικεύουν τον αλγόριθμο του Μπίρκοφ σε μη τετραγωνικούς πίνακες, με ορισμένους περιορισμούς στις εφικτές αναθέσεις. Παρουσιάζουν επίσης έναν αλγόριθμο αποσύνθεσης που ελαχιστοποιεί τη διακύμανση των αναμενόμενων τιμών.

Ο Βαζιράνι[11] γενικεύει τον αλγόριθμο του Μπίρκοφ σε μη διμερή γραφήματα.

Οι Βάλς κ.ά.[12] έδειξαν ότι είναι δυνατόν να ληφθεί ένα ϵ-προσεγγιστική παραγοντοποιήση με O(log⁡(1/ϵ2)) μεταθέσεις.

Δημοσιεύσεις

Δείτε επίσης

Εξωτερικοί σύνδεσμοι

Παραπομπές

Πρότυπο:Reflist

Πρότυπο:Authority control Πρότυπο:Portal bar

  1. ↑ Πρότυπο:Citation.
  2. ↑ 2,0 2,1 Lovász, László; Plummer, M. D. (1986), Matching Theory, Annals of Discrete Mathematics, vol. 29, North-Holland, ISBN 0-444-87916-1, MR 0859549
  3. ↑ Πρότυπο:Citation.
  4. ↑ Πρότυπο:Cite web
  5. ↑ Πρότυπο:Cite arXiv
  6. ↑ Πρότυπο:Cite journal
  7. ↑ Πρότυπο:Cite journal
  8. ↑ Πρότυπο:Cite journal
  9. ↑ Πρότυπο:Cite journal
  10. ↑ Πρότυπο:Cite journal
  11. ↑ Πρότυπο:Cite arXiv
  12. ↑ Πρότυπο:Cite journal
Ανακτήθηκε από «https://el.wiki.beta.math.wmflabs.org/w/index.php?title=Αλγόριθμος_του_Μπίρκοφ&oldid=2882»