مسئله ازدواج پایدار

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

مسأله ازدواج پایدار در ریاضیات برای مدل سازی تطابق پایدار به کار می رود.

تعریف[ویرایش]

به طور کلی این قضیه بیانگر این است که اگر مجموعه ای از مردها و مجوعه ای از زن ها داشته باشیم که هر یک دارای اولویت هایی برای ازدواج باشند، در این راستا حتماً راهی وجود داردکه در نهایت امکان ندارد دو نفر که یکدیگر را می خواهند(در واقع در اولویت یکدیگر هستند) با یکدیگر نباشند.این راه از طریق الگوریتم گیل-شاپلی پیدا می شود. توجه کنید که طبق این الگوریتم حتماً راهی وجود دارد که شرایط بالا را داشته باشد.

در شکل روبه رو : 4 مرد (شاه) و 4 زن (ملکه) وجود دارند. برای مثال مرد A زن ها را با ترتیب C ، A ، D ، B امتیاز دهی کرده است و به همان صورت زن B مردها را با ترتیب A ، B ، D ، C ترجیح می دهد.

الگوریتم[ویرایش]

در سال ۱۹۶۲ دیوید گیل و لوید شاپلی اثبات کردند که برای هر تعداد مساوی زن و مرد، می توان مسأله ی ازدواج پایدار را حل کرد و الگوریتمی برای این کار ارائه دادند.هدف از اجرای این الگوریتم آن است که راهی پایدار برای تطبیق دادن و جفت کردن مردان با زنان (با توجه به اولویت های آن ها) بیابیم.

انتخاب های ناپایدار[ویرایش]

راهی ناپایدار است که در آن مرد و زنی وجود داشته باشند که با یکدیگر جفت نشده اند اما یکدیگر را به جفت های فعلی خود ترجیح دهند.

همان طور که می بینیم این یک انتخاب ناپایدار است. به مرد C و زن B نگاه کنید.هر دوی آنها یکدیگر را به جفت های فعلی خود ترجیح می دهند . مرد C با انتخاب دوم خود جفت شده و زن B با انتخاب سوم خود، در حالی که اگر این دو با هم جفت می شدند هر دو به انتخاب اول خود می رسیدند. قلب ها نشان دهنده ی بی ثبات بودن انتخاب های کنونی می باشند.

توضیح الگوریتم گیل-شاپلی[ویرایش]

پیدا کردن راهی پایدار برای جفت کردن مردها و زنها نیازمند آزمایش‌های متعدد است که گاه زمان زیادی می‌برد اما الگوریتم گیل-شاپلی راه حلی را برای یک انتخاب پایدار ارائه می کند. این الگوریتم بیانگر این است که بدون توجه یه تعداد مرد ها و زن ها، همواره می توان راهی پایدار برای جفت کردن آنها پیدا کرد. طرز کار این الگوریتم به صورت زیر است : ابتدا هر مرد از اولویت اول خود درخواست می کند، اگر زن مورد نظر قبلاً با کسی "نامزد" نشده باشد این درخواست را قبول می کند اما اگر فرد دیگری نیز از او درخواست کرده بود، زن شخصی را برمیگزیند که اولویت بالاتری نسبت به فرد دیگر دارد.مردی که درخواستش رد شده است از این درخواست صرف نظر کرده و درخواست دیگری را به اولویت بعدی خود مطرح می کند . در مثال زیر این روش مشخص تر است :

Sahel07.jpg

در قدم اول مردهای A و B از زن هایی که در اولویت اول هستند درخواست می کنند و طبق الگوریتم اگر زن درخواست دیگری نداشته باشد خود به خود این درخواست را قبول می کند. بنا بر این مرد A از زن B و مرد B از زن D درخواست میکند و آنها نیز این درخواست را می پذیرند. در مرحله ی بعدی نوبت مرد C است که درخواست خود را مطرح کند. زن B در اولویت اول مرد C قرار دارد بنابراین مرد C از وی درخواست می کند، اما زن B نامزد شده است پس طبق الگوریتم زن باید مردی را انتخاب کند که امتیاز بالاتری نسبت به دیگری دارد.طبق این دستورالعمل زن B مرد C را که اولویت اول خودش است، انتخاب می کند و مرد A مجبور است انتخاب دیگری بکند :

Sahel04.jpg

در قدم بعدی، مرد A باید انتخاب بعدی خود را طبق اولویت هایش مطرح کند که در این جا اولویت دوم او زن D است.اما مانند حالت قبل زن D نامزد شده است بنابراین باید یکی از دو مرد A یا B را انتخاب کند که چون مرد B برای زن دارای امتیاز بالاتری است، انتخاب می شود و به این ترتیب مرد C باید به سراغ اولویت بعدی خود یعنی زن A برود :

Sahel05.jpg

زن A هیچ درخواست دیگری ندارد بنابراین این پیشنهاد را می پذیرد. در مرحله ی بعد، نوبت مرد D است که انتخاب خود را انجام دهد. همان طور که میبینیم اولویت اول او، زن B است اما از آن جا که زن B نامزد شده است مانند حالت قبل باید یکی از مرد ها را انتخاب کند که در این جا به علت اولویت های زن B، مرد D رد می شود و باید از اولویت بعدی خود یعنی زن C درخواست کند :

Sahel06.jpg

زمانی که همه ی مردها با زنی جفت شوند آنگاه مسأله به پایان رسیده است و راه پایدار برای آن پیدا شده است. همان طور که مشخص است طبق هدف این الگوریتم هیچ مرد و زنی نیستند که با وجود بیشتر خواستن فرد دیگری با شخصی دیگر جفت شده باشند.

نکته[ویرایش]

در این روش، ترتیب انتخاب مردان مهم نیست . آنها می توانند با هم انتخاب کنند و اگر کسانی باید جواب رد می گرفتند، در مرحله ی بعدی همه با هم به انتخاب های بعدی بپردازند . این روش که یک زیر شاخه از الگوریتم گیل-شاپلی است به الگوریتم McVitie-Wilson معروف می باشد.

کاربرد[ویرایش]

در دنیای واقعی، الگوریتم گیل-شاپلی برای فرستادن دانشجویان پزشکی به بیمارستان مورد علاقه ی آن ها، حل برخی مسائل گراف های وزن دار ( برای مثال پیدا کردن کم خرج ترین مسیر در یک گراف وزن دار)، تقسیم دانشجویان در اتاق های خوابگاه و ... به کار می رود.

منابع[ویرایش]