משתמש:אלגוריתמיקאי/ארגז חול

כתיבת הערך שידוך יציב

בעיית השידוך היציב, הוא כינוי לאוסף של בעיות העוסקות במציאת התאמה בין איברים של שתי קבוצות בהינתן סדרי עדיפויות כשהדגש הוא על יציבות הפתרון. ניסוח טיפוסי מספר על n גברים וn נשים הרוצים להשתדך, כשלכל גבר ולכל אישה דירוג מלא של כל בני המין השני. המטרה למצוא התאמה כך שלא יהיו גבר ואישה שמשודכים לבני זוג אחרים ומעדיפים זה את זה על פני בני זוגם. שידוך שאין בו גבר ואישה כאלה נקרא יציב

הסטוריה של הבעיה

הבעייה נוסחה באופן פורמלי לראשונה במאמר של דייוויד גייל (David Gale) ולויד שפלי (Lloyd Shapley) שהוכיחו כי בתנאים הנ"ל תמיד יש שידוך יציב וכי יש אלגוריתם פשוט למציאתו.