Αλγόριθμος Gale-Shapley
Ο αλγόριθμος Gale-Shapley επιλύει το πρόβλημα του σταθερού γάμου: πώς να αντιστοιχιστούν δύο ομάδες (π.χ., ειδικευόμενοι ιατροί σε νοσοκομεία, φοιτητές σε σχολεία) έτσι ώστε κανένα ζεύγος να μην προτιμά ο ένας τον άλλον από τους ανατεθειμένους συντρόφους του. Ο αλγόριθμος, που εισήχθη από τους David Gale και Lloyd Shapley το 1962, εγγυάται μια σταθερή αντιστοίχιση σε πολυωνυμικό χρόνο μέσω μιας διαδικασίας αναβολής αποδοχής, όπου η μία πλευρά προτείνει διαδοχικά και η άλλη πλευρά απαντά, αναθεωρώντας τις επιλογές καθώς φτάνουν καλύτερες επιλογές.
Διαβάστε ολόκληρη τη μέθοδο
Συνδεθείτε με δωρεάν λογαριασμό για να διαβάσετε αυτή την ενότητα.
Χάρτης μεθόδων
Η γειτονιά των σχετιζόμενων μεθόδων — επιλέξτε έναν κόμβο για εξερεύνηση.
Πηγές
- Gale, D., & Shapley, L. S. (1962). College admissions and the stability of marriage. The American Mathematical Monthly, 69(1), 9-15. DOI: 10.1080/00029890.1962.11989827 ↗
- Roth, A. E. (1984). The economics of matching: Stability and incentives. Mathematics of Operations Research, 7(4), 617-628. DOI: 10.1287/moor.7.4.617 ↗
Πώς να παραπέμψετε σε αυτή τη σελίδα
ScholarGate. (2026, June 3). Gale-Shapley Stable Marriage Algorithm. ScholarGate. https://scholargate.app/el/game-theory/gale-shapley-algorithm
Ποια μέθοδος;
Τοποθετήστε αυτή τη μέθοδο δίπλα στις πιο συγγενείς της και διαβάστε τις παράλληλα — η βιβλιοθήκη απλώνει τα βιβλία στο τραπέζι· η επιλογή είναι δική σας.
- Ισορροπία Nash Bayes (BNE)Θεωρία Παιγνίων↔ σύγκριση
- Μοντέλο Κύριου-ΕντολοδόχουΘεωρία Παιγνίων↔ σύγκριση
- Κύκλοι Κορυφαίων ΣυναλλαγώνΘεωρία Παιγνίων↔ σύγκριση
- Μηχανισμός VCG (Vickrey-Clarke-Groves)Θεωρία Παιγνίων↔ σύγκριση
Αναφέρεται από
Εντοπίσατε πρόβλημα σε αυτή τη σελίδα; Αναφέρετέ το ή προτείνετε διόρθωση →