تطبیقِ پایدار یعنی زوجِ نامتطابقی وجود نداشته باشد که هر دو طرف،یکدیگر را به شریکِ فعلی ترجیح دهند. این تعریف،کمینه‌کردنِ هزینه یا راضی‌بودنِ همگان نیست. الگوریتمِ پذیرشِ معوق،پیشنهاد و نگه‌داشتنِ موقت را جدا می‌کند؛ اینجا دو اجرایِ دوطرفه و همهٔ تطبیق‌هایِ ممکن را واقعاً می‌سنجیم.
دو گروهِ خیالی با ترجیحِ کامل
گروهِ چپ A،B،C وD وگروهِ راست X،Y،Z وW هستند. هر فهرست از مطلوب‌تر به کم‌مطلوب‌تر نوشته شده و همهٔ گزینه‌هایِ طرفِ مقابل را دقیقاً یک بار دارد. نمونهٔ چهاردرچهارِ این صفحه اصیل است؛ مثالِ سه‌درسهٔ مقالهٔ اصلی را با نام‌هایِ عوض‌شده بازنشر نکرده‌ایم.
| چپ | ترجیح | راست | ترجیح |
|---|---|---|---|
| A | Y,X,Z,W | X | A,C,D,B |
| B | X,Z,W,Y | Y | B,D,A,C |
| C | Z,W,Y,X | Z | D,B,C,A |
| D | W,Y,X,Z | W | C,A,B,D |
این‌ها افراد یا سازمان‌هایِ واقعی نیستند؛ ترجیحِ ساخته‌شده،دادهٔ رضایت یا مجوزِ تخصیصِ واقعی نیست.
نگه‌داشتنِ پیشنهاد،قبولِ نهایی نیست
هر پیشنهاددهندهٔ آزاد به بهترین گزینه‌ای پیشنهاد می‌دهد که هنوز امتحان نکرده است. گیرنده اگر خالی باشد موقتاً نگه می‌دارد؛ اگر پیشنهادِ مطلوب‌تری برسد،قبلی را آزاد می‌کند؛ وگرنه تازه‌وارد را رد می‌کند. طرفِ آزاد به گزینهٔ بعدی می‌رود. اشاره‌گرِ هر پیشنهاددهنده جلو می‌رود؛ همان پیشنهاد بی‌پایان تکرار نمی‌شود.
دفترِ اجرا برای هر پیشنهاد،گیرنده،نگه‌داشتهٔ قبلی،عمل و وضعیتِ تازه را دارد. برای نشان‌دادنِ واقعیِ جایگزینی و رد،یک fixtureِ اضافیِ اصیل نیز داریم: A وB وC ابتدا Y را می‌خواهند؛ Y نخست A را نگه می‌دارد،با B عوض می‌کند وC را رد می‌کند. این شاخه‌ها فقط در توضیح ادعا نشده‌اند.
دو جهت،دو جوابِ پایدار
در مثالِ اصلی،پیشنهاد از چپ،AY،BX،CZ وDW می‌دهد. پیشنهاد از راست پس از برگرداندنِ جهتِ نمایش،AX،BY،CW وDZ می‌دهد. کد هر دو را یک‌به‌یک و بدونِ زوجِ مسدودکننده کنترل کرده است؛ متفاوت‌بودن به معنیِ غلط‌بودنِ یکی نیست.
در تعریفِ blocking pair،ترجیحِ سخت‌گیرانهٔ هر دو طرف لازم است. اینکه فقط A گزینه‌ای را بیشتر دوست دارد،به‌تنهایی ناپایداری نمی‌سازد؛ باید آن گیرنده هم A را به نگه‌داشتهٔ فعلی ترجیح دهد. oracle همین دو شرط را برای تمامِ زوج‌هایِ نامتطابق می‌سنجد.
تمامِ ۲۴تطبیق را مستقل بررسی کنیم
همهٔ جایگشت‌هایِ چهار عضوِ راست را به اعضایِ چپ اختصاص می‌دهیم و برای هر کدام،فهرستِ زوج‌هایِ مسدودکننده را می‌سازیم. از۲۴تطبیق،سه مورد پایدارند: AX/BY/CW/DZ،AX/BZ/CW/DY وAY/BX/CZ/DW. هر دو خروجیِ الگوریتم در همین مجموعه‌اند.
همچنین تمامِ ۲۴ترتیبِ آغازینِ پیشنهاددهندگانِ چپ،همان جوابِ چپ را می‌دهند. تمامِ ۱۶پروفایلِ ترجیحِ کاملِ دو‌در‌دو هم در هر دو جهت اجرا و از نظرِ پایداری کنترل شده‌اند. این بررسیِ متناهی جایِ اثباتِ همهٔ اندازه‌ها یا ارزیابیِ عدالتِ یک سیاست را نمی‌گیرد.
دامنهٔ کوچک را با تخصیصِ واقعی یکی نکنیم
فهرستِ ناقص،گزینهٔ تکراری،عضوِ ناشناخته و دو گروهِ نامساوی در چهار آزمون رد می‌شوند. دامنهٔ این کد۱تا۴عضو در هر طرف،فهرستِ کامل و بدونِ تساوی است. روش‌هایِ دارایِ ظرفیت،ترجیحِ ناقص یا tie مسئله‌هایِ قراردادِ گسترده‌تری دارند و اینجا اجرا نشده‌اند.
تخصیصِ کم‌هزینهٔ یک‌به‌یک مجموعِ عددهایِ هزینه را کمینه می‌کند؛ پایداریِ ترجیح معیارِ دیگری است. هیچ‌یک از این جدول‌ها مجوزِ تصمیم دربارهٔ انسان‌ها،تضمینِ انصاف یا معرفیِ موتورِ تخصیصِ اپرا نیست. برای ادامهٔ آموزش به مبانی هوش مصنوعی بروید و معیارِ هدف و قیود را پیش از انتخابِ الگوریتم مشخص کنید.
فایل تمرین و منبع
کد مستقلِ تمرین و کنترل‌ها؛ Python · تمامِ ورودی‌ها و نتیجهٔ اجرای واقعیِ تمرین؛ JSON
منابع در 2026-11-04 خوانده شدند؛ این تاریخ، تاریخ انتشار منبع نیست. مثال‌ها و فایل‌های این راهنما آموزشی و ساختهٔ تحریریه‌اند.