Μάθημα 4 (Μέρος Α) / Ευσταθές Ταίριασμα
Ευσταθές Ταίριασμα: Σήμερα θα κάνουμε παιχνίδι έχουμε δει στα προηγούμενα μαθήματα τη σημασία του μαθήματος Σκοπός του μαθήματος στην τεχνολογική αξία του μαθήματος έχουμε ζητήσει τις βασικές αρχές αναλύσεις αλγορίθμων έχουμε επειδή μετράμε έτσι στοιχεία αριθμός στοιχείων των πράξεων έχουμε εξηγήσει...
| Κύριος δημιουργός: | |
|---|---|
| Γλώσσα: | el |
| Φορέας: | Πανεπιστήμιο Πατρών |
| Μορφή: | Video |
| Είδος: | Ανοικτά μαθήματα |
| Συλλογή: | Τμήμα Mηχανικών Η/Υ & Πληροφορικής / Εισαγωγή στους Αλγόριθμους |
| Ημερομηνία έκδοσης: |
ΠΑΝΕΠΙΣΤΗΜΙΟ ΠΑΤΡΩΝ
2014
|
| Θέματα: | |
| Άδεια Χρήσης: | Αναφορά-Μη-Εμπορική Χρήση-Όχι Παράγωγο Έργο |
| Διαθέσιμο Online: | http://delos.upatras.gr/opendelos/videolecture/show?rid=bcf4ab25 |
| Ευσταθές Ταίριασμα: Σήμερα θα κάνουμε παιχνίδι έχουμε δει στα προηγούμενα μαθήματα τη σημασία του μαθήματος Σκοπός του μαθήματος στην τεχνολογική αξία του μαθήματος έχουμε ζητήσει τις βασικές αρχές αναλύσεις αλγορίθμων έχουμε επειδή μετράμε έτσι στοιχεία αριθμός στοιχείων των πράξεων έχουμε εξηγήσει μέσω προσωπικού συμβολισμού και δεν χρειάζεται να μετρήσουμε της πάρα πολλές λεπτομέρειες που κυρίως αφορούν σταθερές μπορούμε να τις καλύψουμε γιατί δεν επηρεάζουν το χρόνο εκτέλεσης του αλγόριθμου χώρα και έτσι στο περασμένο την περασμένη εβδομάδα είδαμε μας μερικές βασικές απλές δεδομένων όπως είναι η πίνακες μονοδιάστατη πολίτη αυτό δεν έχει σημασία λίστας και σύντομη showroom μια πάρα πολύ βασική δομή σήμερα θα δούμε το πρώτο μας αλγόριθμο μια πολύ ωραία εφαρμογή του η οποία υποθέτω θα την μα είναι θα έλεγα με κοινωνικό αντίκτυπο αυτό που έτσι πάρα πολλές εφαρμογές αλλά να δούμε ένα πάρα πολύ ωραίο παράδειγμα το πρόβλημα λέγεται σαφές ταίριασμα και αφορά την κλασική πώς το λένε περίπτωση όπου έχουμε άνδρες και γυναίκες έτσι ίσο αριθμό από άνδρες και γυναίκες και θέλουμε να τους φτιάξουμε να βρούμε το κατάλληλο ταίρι για κάθε άνδρα και κάθε γυναίκα προσέξτε γιατί είναι ένα πρόβλημα που βγαλμένα από τη ζωή λοιπόν το θέμα εδώ είναι να έχουμε ένα να επιτύχουμε ένα ευστάθειας ταίριασμα σημαίνει αυτά πες ταίριασμα σημαίνει πεδίο δηλαδή εδώ έχουμε μονογαμία η πολυγαμία δεν επιτρέπεται ένα άνδρας αντιστοιχίζονται σε μια γυναίκα και στόχος και δεν επιτρέπουμε ασταθής έβγαλε μια αυτό σημαίνει σταθερά δηλαδή ορίζουμε την ευστάθεια με το αρνητικό του ασταθούς σεμιναρίου που σημαίνει ότι ένα ζευγάρι λέγεται ασταθές και θα δούμε παραδείγματα σε λίγο διά ο άνδρας και η γυναίκα αξίζει προτιμούν ένα στον άλλον από τους τωρινούς τρόπος έτσι κάτι τέτοιο είναι μια επιθυμητό εφόσον θέλουμε να κάνουμε ένα ευστάθειας ταίριασμα είναι κατανοητό το πρόβλημα όσο λεπτομέρειες λίγο δύο αυτό το πρόβλημα τι κάνουμε έχουμε άνδρες και γυναικείας συμμετέχοντας δηλαδή ο βαθμός της έχουμε έχουμε εδώ στο παράδειγμα τρεις άνδρες και τρεις γυναίκες Λάμπρος κατατάσσουν τις γυναίκες κατά φθίνουσα σειρά προτίμησης το ίδιο κάνουν και έγινε χρήση δηλαδή ο κώστας προτιμάει προβατίνα αναμεταδίδει Μαρία μετά την Ελένη ο νίκος για αυτή τη σειρά προτίμησης πρώτη Μαρία μετά την αναμεταδίδει Ελένη πιο πέτρος έχει κύρια προτίμηση των κώστα τυχαίνει αντίστοιχα η άμα κάνω όταν τυχαία τελείως έτσι προτιμάει τον νίκο μετά λόγος μετά τον πέτρο και ούτω καθεξής και οι υπόλοιποι οι υπόλοιπες κεφα Λι πριν σας πω τους λεπτό είναι έτσι αυτό είναι η είσοδος του προβλήματος ναι ένα άλλο παράδειγμα από Αλαβάνο που επαναλαμβάνω είναι πολύ καλό για δικαστικούς σκοπούς η αρχική μορφή του προβλήματος έχει πάρα πολλές εφαρμογές η κύρια πηγή ήταν όταν μετά τον δεύτερο παγκόσμιο πόλεμο στις ηνωμένες πολιτείες η υπηρεσία που ταιριάζει ειδικευόμενους γιατρούς νοσοκομεία και το αντίστοιχο πρόβλημα και ήθελε προκειμένου να αποφύγει παράτυπες συμφωνίες μεταξύ αιτούντων και νοσοκομείων να επιβάλει ένα αυτό επιβαλλόμενη διαδικασία προσλήψεων ένα δηλαδή κατά την οποία κανείς να μην έχει κίνητρο μια να να μην δεχθεί την τελική επιλογή που θα γίνει και αυτό σημαίνει ότι δεν πρέπει να έχουμε ασταθής ασταθής έβγαλε καταρχήν πρέπει να πρέπει να αντιστοιχηθεί με ειδικές τουλάχιστον ειδικευόμενος στο νοσοκομείο ότι θα πρέπει ο να μην έχουμε σταθεί ζευγάρια που σημαίνει ότι μου όταν ο αιτών ειδικευόμενος και για το νοσοκομείο C είναι ασαφή όταν ο αιτών προτιμάει το ένα νοσοκομείο από αυτό που του έχει ανατεθεί και αντίστοιχα το νοσοκομείο προτιμάει κάποιον άλλον που είχε κάνει αίτηση αποφοίτων που τους ανατέθηκε και αυτό είναι παραπάνω ευπαθείς ανάθεση είναι μια φυσική και επιθυμητή κατάσταση επειδή ακριβώς λόγω της αυτό επιβάλλουν εμείς διαδικασίας δεν υπάρχει το ξεχωριστό ατομικό συμφέρον κανείς κανένα κίνητρο για οποιοσδήποτε παράτυπες συμφωνίες μεταξύ τούτων και νοσοκομείο το δεύτερο είναι για παράδειγμα κάθε καλοκαίρι ειδικά εσείς στο δεύτερο τους βέβαια οι περισσότεροι από σας σημείωσε το τέταρτο και πέμπτο έτος υπάρχουν φοιτητές που ψάχνουνε εταιρείες για πρακτική άσκηση μια τέτοια διαδικασία θα μπορούσε να επιβληθεί εδώ όπου θέλω πάλι να έχουνε αυτό επιβαλλόμενη διαδικασία όπου ο φοιτητής δε θέλουμε να έχουμε σταθεί ζευγάρια που σημαίνει ότι ο φοιτητής 1000 αν του ανατεθεί μια εταιρεία ψ αυτό είναι ασταθές χάρη ανοχή επιθυμεί μια άλλη καλύτερα από την ψυχή εταιρεία και η εταιρεία ψυγεια επιθυμεί κάποιον άλλον αιτούντα για πρακτική άσκηση από αυτόν που της ανατέθηκε ωραία το πρόβλημα αυτό η κωμωδία τέθηκε μετά το τέλος του δευτέρου παγκοσμίου πολεμά από την του υπουργείου υγείας των ηνωμένων πολιτειών λύθηκε αλγόριθμοι από τους gay και όσα λέει το 1962 και επαναλαμβάνω πάλι το πρόβλημα ότι θέλουμε να εκτελεί ταίριασμα που σημαίνει ότι κάθε άνδρας αντίστοιχης ακριβώς μια γυναίκα και μια γυναίκα ακριβώς έναν άνδρα έτσι και δεύτερον έχουμε το θέμα της ευστάθειας δηλαδή δεν υπάρχει κίνητρο για κάποιο ζευγάρι συμμέτοχο συμμετεχόντων άντρα και γυναίκα να υπονομεύσουν από κοινού την ανάθεση πότε συμβαίνει αυτό όταν έχουμε δυο ζευγάρια ένα ανά γραμμή και μια γυναίκα ταμείου και έναν άνδρα μύκονος και ένα γυναίκα τα πληττόμενα πείτε ότι αυτή είναι η ανάθεση και ξαφνικά ο Adam ή ανακαλύπτουν ότι προτιμούν περισσότερο από ένα τον άλλον από τους τωρινός σύντροφος και προφανώς εάν αυτό κάνω μια εγκατάλειψη βιντάλ ο Νταβούτογλου είχε ωμή δύναμη ή γίνουν ζευγάρι προφανώς καλυτερεύουν την κατάσταση τους γιατί γιατί παίρνουν κάποιον άνδρα γυναίκα καλύτερο στιλίστα προτιμήσεις τώρα ευπαθές ταίριασμα σημαίνει τελείως και χωρίς να σταθεί ως ζευγάρια και το θέμα είναι ότι εάν μας δώσουνε τις λίστες προτιμήσεων των ανδρών και των γυναικών θέλουμε να δούμε ένα ευστάθειας ταίριασμα εάν υπάρχει ώρα ρωτάω τώρα πείτε ότι κάνουμε αυτή την ανάθεση εδώ δίνουμε στον κώστα την Ελένη στον νίκο τη Μαρία στον πέτρο τινά είναι αυτό ένα ασταθές τριας γιατί γιατί πρέπει όπως σας έχει να τι θέλει ο πρόεδρος να δεν παίρνει Olympic ευστάθειας ταίριασμα σύνδεση σημαίνει όπως εξήγησα την ότι καθένας πριν την πρώτη επιλογή του με νέας παραγωγοί θέλουν αλλά το θέμα είναι πιο μπροστά ναι κάποια με κάποια προτίμηση πάμε πάλι τις ασταθές ταίριασμα σημαίνει ότι υπάρχει ένα ζευγάρι που δεν έχει γίνει ανάθεση ωραία και προτιμούν καλύτερα ένα στον άλλον από τους τωρινούς συντρόφους ώρα ένα τέτοιο πράγμα πρέπει να μου δείξεις όπως ο συνάδελφος εκεί με ορίστε να στον κώστα δεν είναι πρώτοι πρότειναν τρίτοι υπάρχει δε μας ενδιαφέρει αυτό ετσι γιατι είναι πολυ απλό διότι κοίταξε να δεις εάν δούμε ότι εδώ κοίταξε η Μαρία % άντε δύο νίκος ωραία προτιμάει τους καλύτερα τον κώστα έτσι δεν είναι στόχος έχει τεθεί Ελένη προτιμά Καλλικράτη Μαρία να λοιπόν ένα ασταθές έβγαλε δηλαδή προξένεψαν με την Ελένη στον κώστα και την στο στον κώστα την λένε Μαρία στον νίκο ωραία αλλά βλέπουμε ότι είναι και οι δύο δεν είναι ικανοποιημένοι με τις επιλογές τους γιατί αφού κοστίζει τη Μαρία τη την εξε καλύτερα προτίμησε μας περίπτωση από την Ελένη και η Μαρία με τον κώστα στην πρώτη προτίμηση σε σχέση με τον νίκο επομένως αυτοί οι δύο είναι ασταθές έβγαλε δεν είναι ικανοποιημένοι με την επιλογή με την ανάθεσή τους έχει να ακριβώς τη σημασία όχι δεν είναι το μοναδικό παράδειγμα αστάθειας εδώ απλώς είναι ένα παράδειγμα ταχείας προφανώς υπάρχει στάθης αφού αποδείξουμε σήμερα έξι άλλες 40 έμεινε ανύπαντρη έτσι οι αταίριαστοι φέτος μην μου να όχι βέβαια όχι δεν προτιμάει όπως το πρόβλημα κάτι που θα δούμε και ένα άλλο παράδειγμα εδώ γαλόνια έλενας δίνουμε στον κώστα έδιναν στον νίκο τη Μαρία και στην και στο πρόεδρό την Ελένη αυτό είναι ευπαθές ταίριασμα της καταρχήν είναι ασταθές γιατί κατά στόχων στον Νίκο Γκάτσο με την πρώτη προτίμηση εδώ να πω ότι ήδη θα ακολουθήσουμε την παραδοσιακή μέθοδο ωραίο που οι άνδρες κάνουν πρόταση στη ζωή δε συμβαίνει αυτό συμβαίνει γιατί πάνω από όλα εμείς εδώ θα είμαστε παραδοσιακοί ετσι οι άνδρες κάνουν προτάσεις και γυναίκες αποδέχονται για τους σκοπούς του συγκεκριμένου προβλήματος φορέα επομένως ο Κώστας Σπυρονίκος πήραν την πρώτη προτίμηση δεν έχουν απολύτως απαντώ στην ερώτησή σου απαντώ στην ερώτησή σου δεν έχουν απολύτως κανένα λόγο να αλλάξει το μοναδικό ζήτημα επίσης η άννα και μπορεί να έχει το κώστας 2η προτίμηση και η μαριάννα το νίκος 2η προτίμηση αλλά δεν μπορούν και να την δει Μαρία θέλει τον κώστα αλλά τι να κάνουμε όπως τελικά ανθρώπινα και Κώστας κάνει πρόταση στην επομένως μπορεί μαριάννα κίνητρο να αλλάξει αυτό θέλω να εξηγήσω μπορεί παιδιά ακούστε λιγάκι γιατί αν καταλάβετε αυτό με το παράδειγμα του συγκεκριμένου που είναι πολύ απλό να καταλάβετε δε θα μπορέσει αργότερα να καταλάβετε ότι το αγόρι μπορεί να λέω λοιπόν ότι η Μαρία έχει ένα κίνητρο να αλλάξει γιατί δεν πήρε την πρώτη επιλογή κάποιων πρώτη επιλογή κώστας για να της κάνει πρόταση Κωστα στα πρέπει κοιμάται εν πρώτοις επιλογή ο κώστας θεωρεί δεύτερη τη Μαρία για κάποιο δικό τους λόγω και θεωρεί πρώτη στην προτίμηση του την άννα εφόσον λοιπόν κάνοντας την ανάγκη αναπόδραστη και την πρόταση έχει τελειώσει το θέμα ο κώστας δεν έχει κανένα κίνητρο να αλλάξει όσο και Μαρία θέλει να αλλάξει αφού άλλος θέλει να αλλάξει έτσι τον ιωάννα αφού ήθελε τον ήχο της εικονικός όμως πρόσεξε να δεις έχει εργαστεί με την Μαρία που στην προτίμηση του νίκου Μαρία είναι πρώτη στην προτίμηση ενώ ανέφερε επόμενος χρονικός εννοεί αν αυτά χρόνια να είναι τέτοιο με τον Νίκο ο Νίκος δεν θέλει να κάνει με την άννα γιατί ταιριαστή με την Μαρία περίοδο καταλάβατε έχει σημασία να καταλάβουμε πέρα από το παιχνίδι της υπόθεσης με γιατί είναι οπαδός και Ελένη ασταθής διάκοσμο να για έναν ασταθή ισοπέδωση Ελένη καταρχήν δεν μπορεί να σε κάποιον που τις κάνει έχει εδώ υπάρχει ένα ταίρι το πέτρος Ελένη είναι ένα ταίριασμα το ασταθές είναι μεταξύ ένα άνδρα και μίας γυναίκας που 13 σημαίνει δηλαδή μου λεγες πέτρος ιωάννας μυλόπετρες και Μαρία κατάλαβες 2ο Open source έχει πάρει δεν του προτίμηση είναι ρε παιδί μου τι γίνεται με ένα για την παροχή ειδών πρώτης φορέα μια λέει θάθελα περισσότερο την άννα Ματίνα ανατίθεται ο στην πρώτη προτίμηση κα να έχει τον κώστας μεγαλύτερη προτίμηση των μέτρων άρα η Άννα δεν έχει κίνητρο να αλλάξει πήρε κάποιον καλύτερο από τον Πέτρο ο Πέτρος λέει γιατί να μην έχω τη Μαρία έτσι απαλή Μαρία το τέταρτο και τελευταίο στην προτίμηση και προτιμάει καλύτερα τον νίκο επομένως ούτε Μαρία έχει κίνητρο να αλλάξει πάνω πέτρος μένει με την Ελένη η Ελένη το ίδια συλλογιστική έχει με τον πέτρο τελετή προκειμένου να μην στραφεί πάσει περίπτωση αφορά το μέτρο φορά λέω ας ευστάθειας φωτό είναι ασταθές που πριν ωραία σταθερές όταν δεν υπάρχουν τα ζευγάρια όταν όλα τα ζευγάρια είναι όταν δεν υπάρχει σύννομη κανένας ταφές έβγαλε ώρα μεταξύ ανδρών και γυναικών ωραία είναι κατανοητό αυτό δηλαδή λέμε το ότι το ταίριασμα θέλουμε να να ναται να πιάσουμε ν άνδρες μένει γυναίκας φορέα υπάρχουν είτε τραγουδά δυνατά ζευγάρια παρά στο τέλος θα προκύψουν τετράγωνο θα προκύψουν ν έτσι για πιο δυστυχισμένα άντρα με μια γυναίκα ωραία αν από αυτή αποκτά τέτοια άσματα κανένα δεν είναι σταθερές του πόρου ταίριασμα λέγεται ευστάθειας και επαναλαμβάνω ότι επισημαίνει ασταθές όταν έχουμε κάνει αρχικό ταίριασμα τον γραμμή στη γυναίκα τάβλι και τον Ατρόμητο στη γυναίκα και εκ των υστέρων διαπιστώνουν ωμή ότι έχετε ή καλύτερα στην πρώτη στη λίστα προτίμησης από τιτάνιο και ήταν ή όχι αυτόνομη καλύτερο από τον τόνο στη λίστα προτίμηση στις έτσι στο παράδειγμα λοιπόν εδώ αν θυμάσαι καλά μια ανάθεση πολλά και παρόλο που ο πέτρος πήραν την πρώτη τους προτίμηση παρατηρούμε ότι υπάρχει ένα ασταθές έβγαλε ένα ασταθές μια ωδείο κώστας και Μαρία προτιμούν ένα στον άλλον από τους τωρινούς συντρόφους που κάποιος αλγόριθμος κάποια προξενήτρα έκανε το τρεις το κατάλαβες τώρα νέα γιατί γιατί ο κώστας θέλει καλύτερα τη Μαρία από την Ελένη και η Μαρία έχει τον νίκο μου σαν παιδί και σε δεύτερη προτεραιότητα σε σχέση με τον κώστα επομένως και οι δύο έχουν ένα ακίνητο ενώ να αλλάξουν συντρόφους γιατί καίω ο κώστας είναι καλύτερος προτίμηση από τον οίκο μόνικα δόθηκε στη Μαρία και η Μαρία είναι στη λίστα σε καλύτερη θέση προτίμησης από την Ελένη που αρχικά δόθηκε stunt στόχος κατανοητό ενώ εδώ δεν υπάρχουν ασταθής έβγαλε για το λόγο που εξήγησε δηλαδή θα πρέπει για ασταθή δεν σημαίνει ότι δεν κοιτάμε τις αναθέσεις αλλά κοιτάμε τον κώστα με τη Μαρία την Ελένη του νίκου με την άννα την Ελένη τον πέτρο με την άννα Μαρία εκεί θα ανακαλύψουμε στάθης έβγαλε σε αυτό που δεν έχουμε ταιριάξει δηλαδή και όπως εξήγησα πριν κανένας δεν έχει κίνητρο να αλλάξει καλά Κώστας Σπυρονίκος δεν έχουν κίνητρο να αλλάξουν γιατί έχουν πάρει την πρώτη προτίμηση ωραία αλλά η άννα και παρόλο που η ανακοίνωση τρεις θα θέλανε να αλλάξουν αλλά πρέπει και οι δύο να θέλουν να αλλάξουν και μοναδική περίπτωση ενώ φέτος με την άννα και τη Μαρία να δημιουργούν κάποιο ασταθές αυγά δεν συμβαίνει αυτό όμως γιατί για να δημιουργήσει πέτρος με την ανάθεση έβγαλε πρέπει να να θέλουν και οι δύο ένα στον άλλον ο πέτρος θέλει την ανά ν πρώτη προτίμηση αλλά η άννα προτιμάει τον κώστα που της ανατέθηκε καλύτερα από τον πέτρο άρα δεν έχει κίνητρο για να αλλάξει αλλά ο πέτρος δεν μπορεί να παρέμειναν αντίστοιχα ο πέτρος με τη Μαρία ο πέτρος θέλει τη Μαρία ωραία αλλά η Μαρία αποδεκτό μέτρο τελευταία προτιμήσει σχέση με τον νίκο που ήδη έχει επομένως αφού έχει τον νίκο γουλιά καλεί το θεωρεί καλύτερο από τον πέτρο δεν έχει κίνητρο μαριάννα άλλαξε άρα πέτρος δεν μπορεί να γίνει ταίρι με την Μαρία ασχέτως Ελένη οπλισμένοι με την Ελένη και έχουμε έτσι ευστάθειας ταίριασμα γιατί πουθενά έδωσε οποιοδήποτε μη ταίριασμα ένα ζευγάρι και ένα ανδρόγυνο εικόνα και να κοιτάξουμε δεν παρατηρούμε αστάθεια κατανοητό χώρα πάμε να δούμε έναν αλγόριθμο για το πώς με αυτοματοποιημένο τρόπο αυτήν αυτό επιβαλλόμενη διαδικασία έτσι ώστε κανείς να μην έχει παράπονα πάση περιπτώσει μπορούμε να το να το πετύχουμε επαναλαμβάνω ότι εδόθη είναι ακολουθούμε τον παραδοσιακό τρόπο ο παραδοσιακός κλασικός τρόπος είναι ότι οι άνδρες κάνουν προτάσεις γυναίκες και αυτό το νου έξι φετινοί παραδοσιακή ιδέα την μετέτρεψαν σε αλγόριθμο αγγελική σοφού λέει πριν 50 τόσα χρόνια και λέγεται αλγόριθμος προτάσεις και απόρριψης δηλαδή οι άνδρες κάνουν πρόταση και γυναίκες είτε αποδέχονται η πορεία του έτσι αλλά στο τέλος όλοι μένουν εργαζόμενοι έστω και με τη χειρότερη επιλογή τους να κάνουν κατανοητό θα δούμε θα δούμε ένα παράδειγμα σε λίγο που θα εξακολουθούμε λοιπόν είναι οι εξής σε ψευδό κώδικα ότι αρχικά όλοι ελεύθεροι και ξεκινάει ένα τροχός wine παίρνοντας τους ελεύθερους άνδρας επειδή οι άντρες κάνουν προτάσεις ωραία εάν λοιπόν υπάρχει κάποιος τέτοιος άντρας και δεν έχει κάνει πρόταση σε κάθε γυναίκα πιλότος κάνει πρώτα θα κάνει προτάσεις κάθε γυναίκα μέχρι να να βρει κάποιον μέχρι να βρει μια φτωχή δύο έτσι θέλουμε να ελευθερωθεί τώρα και κάνει πρόταση στην πρώτη γυναίκα πούνε διαθέσιμη στη λίστα προτίμησης κατά φθίνουσα σειρά υπάρχουν τώρα τρεις επιλογές πρώτος αν η γυναίκα αυτή είναι ελεύθεροι και αυτός είναι ο άντρας που της κάνει πρόταση δεσμεύονται είπαμε οι γυναίκες θέλουν να μείνουν στο ράφι με αυτό εάν Δεύτερον Προσέξτε η γυναίκα που ζει για το τώρα πρόταση μπορεί να δεσμεύει μεν αλλά με κάποιον που το θεωρώ χειρότερο από αυτό που κάνει τώρα πρόταση εγκαταλείπει αυτό και παίρνει τον μου τον άντρα Μ καταλύτη δηλαδή των τωρινό σύντροφό μου με τον μάνο πρώτη και φέρνει τον τον γραμμή που τις κάνει τώρα πρώτος ωραία έλεος δηλαδή αν ο άντρας γυναίκα είναι δεσμευμένη και ο άντρας που της κάνει πρόταση το θεωρεί χειρότερο από αυτό που έχει του λέει συγνώμη δε με ενδιαφέρει και τον απορρίπτει αυτό συναλλαγών πάμε να δούμε τον αλγόριθμο με ένα παράδειγμα χώρα για να καταλάβετε τον αλγόριθμο κοίταξε το εξής παράδειγμα έχουμε πέντε άνδρες και πέντε γυναίκες ο καθένας με τη λίστα προτίμησης φορά σαφές ξεκινά παραπάνω τηλέ αλγόριθμος ξεκινάμε από τους άντρες πείτε ότι παίρνουμε τους άνδρες κατά αλφαβητική σειρά στον αέρα δεν έχει σημασία σε απόσπασμα για λόγους ευκολίας και που ανδρέας λοιπόν θα κάνει προφανώς πρόταση στη βάση ώρα στην πρώτη αλγόριθμος λέει ότι οι άνδρες κοιτούν την λίστα προτίμησης στους και κάνουν προτάσεις την πρώτη γυναίκα που είναι διαθέσιμοι που δεν είναι δεσμευμένη αυτό ενώ λοιπόν κάνει πρώτα στη βάσω η βάσω λέει είναι τρίτος είναι τέταρτος στην επιλογή Ανδρέας προκειμένου να μείνουν στο ράφι ας κονέ ωραία η βάσω δεν είναι εργαζόμενοι άρα γίνεται τέλη με τον Ανδρέα ωραία μετά ο Βασίλης κάνει προτάσεις στη δήμητρα η δήμητρα δεν έχει ταίρι τελευταίος στις προτιμήσεις στην προτίμηση της λέει κάποιος πρέπει να πάρω και εγώ να μη φωνάζει μαμά μου δεκάδων διαφέρει επειδή δεν έχει ταίρι μετά κάνει πρόταση οικογένειες ο γιάννης κάνει πρόταση στη βάσω έτσι ECB τώρα γιάννης κάνει πρόταση στη βάση ώρα τι θα συμβεί τώρα ορίστε πολύ σωστά η βάση λέει ο Γιάννης που το θέλει περισσότερο απ'όλους τους κάνει πρόταση λέει ανδρέα λυπάμαι μου έκανε πρόταση γάμου καλύτερος ανάβει ο γιάννης κάνει πρόταση στη βάσω η οποία είναι δεσμευμένη είδαμε λοιπόν στη λίστα της Βάσως στη βάσω της κάνει πρόταση γάμου τους πολύ καλύτερος από τον ανδρέα κατά τη δική της σαφή προτίμηση υπάρχει περίπτωση οπότε αφήνει το ταίρι της τον ανδρέα και γίνεται με το γεν ωραία είναι κατανοητό είναι κατανοητό μετά γίνεται τώρα ο ανδρέας όμως έμεινε ελεύθερος παρά τα κάνει προτάσεις στην επόμενη στην επιλογή του στη λίστα προτίμησης η οποία είναι η άννα οι αλλά δεν έχει ταίρι έτσι δεν έχει τελειώσει με κανέναν και δέχεται τάξη λέει δεν είναι πρώτος δεν είναι ένα αλλά μας περίπτωσιν καθώς καλώς μέχρι επομένως κου ανδρέα Βασίλης και γιάννης έχουν ευρύτερη πάμε τώρα στον Δημήτρη ο Δημήτρης κάνει πρόταση συναντά χώρα τώρα τι θα συμβεί αν δεσμευμένη τι θα συμβεί η ανατολή λυπάμαι δημήτρη έχω καλύτερο ταίρι αποκαλεί έτσι έχω καλύτερο σύντροφο κατά τη δική της λίστα προτίμησης επομένως η άννα απορρίπτει το δημήτρη το Cine μετά ο δημήτρης συνεχίζει γιατί πρέπει να να εργαστεί και βρίσκει και κάνει πρόταση στη δήμητρα ο δημήτρης κάνει πρόταση στην επόμενη από τον απέρριψε για να κάνει πρόταση στην επόμενη στην δήμητρα εδώ η δήμητρα είναι εσείς δε δεσμευμένοι με το Βασίλη και της κάνει πρόταση ότι μέχρι να συμβεί της θα αφήσει τον Βασίλη και δέχεται τον δημήτρη γιατί θεωρεί τον δημήτρη καλύτερο από τον Βασίλη έτσι είναι καλύτερα στη λίστα προτίμησης της όσο εργάστηκε κλαίω δημήτρης και πάμε τώρα στο Βασίλη ο οποίος μας έλλης ήταν δεσμευμένος με τη δήμητρα Γαλάνη δήμητρα τον άφησε πρέπει κι αυτό να βρει τώρα ταίρι έκανε πρόταση στη βάση τι θα συμβεί βάσω θα τον απορρίψει γιατί έχει ήδη του γιάννη που το θεωρεί καλύτερο γρά Ουν φοβάσαι ο Βασίλης παιδιά Βασίλης επιμένει και κάνει πρόταση στην άννα μόνο αυτή είναι η επόμενη στη λίστα προτίμησης ώρα τι θα κάνει έτσι τι θα συμβεί στην περίπτωση αυτή πάντων απόρριψη γιατί πρέπει εκεί τον ανδρέα τον θεωρεί καλύτερο από τον Βασίλη ωραία συνεχίζει να κάνει πρόταση στην γεωργία Βασίλης γεωργία όχι μόνο είναι ελεύθερη αλλά κάνει πρόταση πιο πρώτο στην προτίμηση της έτσι απομένουν ως γεωργία δέχεται γιατί δεν έχει ταίρι και δεν είχε κανένα κίνητρο να αλλάξει χρόνος από δω και πέρα την ώρα και μας μένει με τον ο έκτορας κάνει πρόταση στην βάσω έτσι λίγο έκτορας παιδιά νεκρός κάνει πρόταση στην βάσω η βάσω είναι ήδη δεσμευμένοι με την πρώτη προτίμηση αλλά τώρα απορρίψει το με τον ο έκτορας επιμένει κάνει πρόταση στη δήμητρα ωραία η δήμητρα κάνει πρόταση εξαγοράς όπου τον οποίο θεωρεί καλύτερο από αυτόν που κυβερνά το δημήτρη και να συμβεί θα αφήσει το δημήτρη και θα γίνει ταίρι με τον έκτορα οπότε ο έκτορας βρήκε ταίρι αλλά τώρα ο δημήτρης έμεινε χωρίς ταίρι έκανε πρόταση στην επόμενη στη λίστα προτίμησής τους γεωργία ωραία η γεωργία όμως είναι ήδη δεσμευμένα με κάποιον όποιος είναι καλύτερος από τον δημήτρη οπότε τον Βορίδη ο δημήτρης επιμένει πρέπει να βρείτε ερε κάνει πρόταση στη βάσω η βάσω έχει καλύτερη επιλογή καλύτερο σύντροφο από τον δημήτρη τον Βορίδη κύριε όπως βλέπετε η μάχη θα απορρίψει όλους και είναι με το γιάννη ότι μήνες λοιπόν εκεί θα κάνει πρόταση στην Ελένη που η τελευταία του επιλογή πέρα και να κάνει η Ελένη ενώ θεωρεί τον δημήτρη όμως είναι είναι καταρχήν χωρίς ταίρι και είναι πρώτη της επιλογή επομένως όλοι έχουν ευρύτερη πρόσεξε λιγάκι όλοι έχουν βρει ταίρι και κανένας δεν έχει κίνητρο να αλλάξει φορέα δηλαδή που ανδρέας και να θέλει να πάει είπαμε με τη βάσω η βάσω έχει βρει βουλή το γιάννη το καλύτερο της θεωρώ καλυτερο εγώ Ανδρέας είναι τέταρτος στη λίστα της φορέα του ίδιου οποιοδήποτε άλλο ταίρι ενώ προσπαθεί να προσπαθήσετε να βρείτε δημήτρη Σταμάτη με την γεωργία το είδαμε πριν γεωργία θεωρεί τον Βασίλη Καλλίδη από τον δημήτρη δηλαδή μπορεί να ακούει κάποιος να θέλει αλλά θα πρέπει και ο άλλος επισης να θέλει αυτό μου κάνει πρόταση για να υπάρχει αστάθεια εδώ αν παρατηρήσετε δεν υπάρχουν στάθης έβγαλε μια επομένως έχουμε ένα επταθέσιο ταίριασμα και όπως βλέπετε έχουμε τους έχουμε ταιριάξει όλους δηλαδή κανένας από αυτούς δεν έχει κίνητρο να αφήσει τον τωρινό μου σύντροφο για κάποιον άλλον αυτό σημαίνει αστάθεια |