موضوع مقاله: مسئله ازدواج پایدار | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # مسئله ازدواج پایدار | مقدمه: تعریف به‌طور کلی این قضیه بیانگر این است که اگر مجموعه‌ای از مردها و مجوعه‌ای از زن‌ها داشته باشیم که هر یک دارای اولویت‌هایی برای ازدواج باشند، در این راستا حتماً راهی وجود داردکه در نهایت امکان ندارد دو نفر که یکدیگر را می‌خواهند (در واقع در اولویت یکدیگر هستند) با یکدیگر نباشند. | ## بخش 1: مسئله ازدواج پایدار | برای مثال مرد A زن‌ها را با ترتیب C , A، D , B امتیاز دهی کرده‌است و به همان صورت زن B مردها را با ترتیب A , B، D , C ترجیح می‌دهد. الگوریتم در سال ۱۹۶۲ دیوید گیل و لوید شاپلی اثبات کردند که برای هر تعداد مساوی زن و مرد، می‌توان مسئلهٔ ازدواج پایدار را حل کرد و الگوریتمی برای این کار ارائه دادند. هدف از اجرای این الگوریتم آن است که راهی پایدار برای تطبیق دادن و جفت کردن مردان با زنان (با توجه به اولویت‌های آن‌ها) بیابیم. انتخاب‌های ناپایدار راهی ناپایدار است که در آن مرد و زنی وجود داشته باشند که با یکدیگر جفت نشده‌اند اما یکدیگر را به جفت‌های فعلی خود ترجیح دهند. مرد C با انتخاب دوم خود جفت شده و زن B با انتخاب سوم خود، در حالی که اگر این دو با هم جفت می‌شدند هر دو به انتخاب اول خود می‌رسیدند. توضیح الگوریتم گیل-شاپلی پیدا کردن راهی پایدار برای جفت کردن مردها و زنها نیازمند آزمایش‌های متعدد است که گاه زمان زیادی می‌برد اما الگوریتم گیل-شاپلی راه حلی را برای یک انتخاب پایدار ارائه می‌کند. | ## بخش 2: مسئله ازدواج پایدار | این الگوریتم بیانگر این است که بدون توجه یه تعداد مردها و زن‌ها، همواره می‌توان راهی پایدار برای جفت کردن آن‌ها پیدا کرد. طرز کار این الگوریتم به صورت زیر است: ابتدا هر مرد از اولویت اول خود درخواست می‌کند، اگر زن مورد نظر قبلاً با کسی «نامزد» نشده باشد این درخواست را قبول می‌کند اما اگر فرد دیگری نیز از او درخواست کرده بود، زن شخصی را برمی‌گزیند که اولویت بالاتری نسبت به فرد دیگر دارد. مردی که درخواستش رد شده‌است از این درخواست صرف نظر کرده و درخواست دیگری را به اولویت بعدی خود مطرح می‌کند. در مثال زیر این روش مشخص تر است: وسط|750px در قدم اول مردهای A و B از زن‌هایی که در اولویت اول هستند درخواست می‌کنند و طبق الگوریتم اگر زن درخواست دیگری نداشته باشد خود به خود این درخواست را قبول می‌کند؛ بنابراین مرد A از زن B و مرد B از زن D درخواست می‌کند و آن‌ها نیز این درخواست را می‌پذیرند. زن B در اولویت اول مرد C قرار دارد بنابراین مرد C از وی درخواست می‌کند، اما زن B نامزد شده‌است پس طبق الگوریتم زن باید مردی را انتخاب کند که امتیاز بالاتری نسبت به دیگری دارد. طبق این دستورالعمل زن B مرد C را که اولویت اول خودش است، انتخاب می‌کند و مرد A مجبور است انتخاب دیگری بکند: وسط|800px در قدم بعدی، مرد A باید انتخاب بعدی خود را طبق اولویت‌هایش مطرح کند که در این‌جا اولویت دوم او زن D است. | ## بخش 3: مسئله ازدواج پایدار | اما مانند حالت قبل زن D نامزد شده‌است بنابراین باید یکی از دو مرد A یا B را انتخاب کند که چون مرد B برای زن دارای امتیاز بالاتری است، انتخاب می‌شود و به این ترتیب مرد A باید به سراغ اولویت بعدی خود یعنی زن A برود: وسط|950px زن A هیچ درخواست دیگری ندارد بنابراین این پیشنهاد را می‌پذیرد. همان‌طور که می‌بینیم اولویت اول او، زن B است اما از آن جا که زن B نامزد شده‌است مانند حالت قبل باید یکی از مردها را انتخاب کند که در این‌جا به علت اولویت‌های زن B، مرد D رد می‌شود و باید از اولویت بعدی خود یعنی زن C درخواست کند: وسط|950px زمانی که همهٔ مردها با زنی جفت شوند آنگاه مسئله به پایان رسیده‌است و راه پایدار برای آن پیدا شده‌است. همان‌طور که مشخص است طبق هدف این الگوریتم هیچ مرد و زنی نیستند که با وجود بیشتر خواستن فرد دیگری با شخصی دیگر جفت شده باشند. آن‌ها می‌توانند با هم انتخاب کنند و اگر کسانی باید جواب رد می‌گرفتند، در مرحلهٔ بعدی همه با هم به انتخاب‌های بعدی بپردازند. | ## جمع‌بندی | کاربرد در دنیای واقعی، الگوریتم گیل-شاپلی برای فرستادن دانشجویان پزشکی به بیمارستان مورد علاقهٔ آن‌ها، حل برخی مسائل گراف‌های وزن دار (برای مثال پیدا کردن کم خرج‌ترین مسیر در یک گراف وزن دار)، تقسیم دانشجویان در اتاق‌های خوابگاه و … به کار می‌رود.