المطابقة المستقرة لا تترك زوجًا غير مقترن يفضل كل طرف فيه الآخر على شريكه الحالي. ندرس هنا جانبين متساويين، بسعة واحدة لكل طرف وقوائم كاملة مرتبة دون تعادل. [1]
سنختار أربعة أسماء رمزية في كل جانب، ونكتب اختيارات الطرفين قبل تشغيل الخوارزمية. ثم نراجع سجل العروض ونفحص جميع طرق الاقتران الممكنة. المقصود تجربة حسابية بقوائم مؤلفة؛ لم نجمع تفضيلات أشخاص ولم نطبق نظام قبول أو توظيف فعليًا.
الخلاصة السريعة
- أعطت قوائمنا النتيجة A–Z وB–W وC–X وD–Y بعد سبعة عروض من الجانب الأول.
- القبول أثناء التشغيل مؤقت: استبدل X الطرف A بالطرف C، ثم استبدل Y الطرف B بالطرف D.
- المطابقة A–W وB–X وC–Y وD–Z كاملة، لكنها تفشل بسبب الزوج B–W.
- حصرنا الطرق الأربع والعشرين الممكنة، فوجدنا نتيجتين مستقرتين فقط لهذه القوائم.
- بدء العروض من الجانب الآخر أعطى النتيجة الثانية؛ لذلك نسجل جهة المبادرة مع أي ناتج.
اكتب ترتيب كل طرف مستقلًا
لدينا A وB وC وD في جانب، وW وX وY وZ في الآخر. كل اسم في الجانب الأول يقبل الاقتران بأي اسم في الآخر، لكن ترتيب الرغبات مختلف. لا توجد خانات ممنوعة أو تعادلات أو سعات متعددة في هذه التجربة. اقرأ صف التفضيلات من اليسار إلى اليمين: الأقرب إلى عمود الاسم هو الخيار الأول.
| الطرف | الأول | الثاني | الثالث | الرابع |
|---|---|---|---|---|
| A | X | W | Z | Y |
| B | Y | W | X | Z |
| C | X | Z | W | Y |
| D | Y | X | Z | W |
| W | D | B | A | C |
| X | B | C | A | D |
| Y | C | D | A | B |
| Z | A | D | C | B |
مثلًا A يضع X أولًا، لكن X يضع A ثالثًا. لا تنسخ ترتيب أحد الجانبين إلى الآخر. وموضع الاسم في الصف لا يمثل درجة سعادة نقيسها بوحدة؛ نستعمل الأرقام هنا للمقارنة داخل قائمة صاحبها فقط.
اسمح باستبدال القبول المؤقت
في القبول المؤجل، يعرض الطرف الحر على أفضل خيار لم يطلبه بعد. يحتفظ المستقبل بأفضل عرض لديه مؤقتًا، ويرفض الباقي؛ يعود المرفوض إلى طابور العرض. لا يكرر المبادر العرض على الطرف نفسه. [2]
بدأ برنامجنا بطابور A ثم B ثم C ثم D. يضاف من يفقد قبولًا إلى نهاية الطابور، ويتابع قائمته من الموضع التالي. اختيار هذا الطابور يجعل السجل قابلًا لإعادة الإنتاج. لا نبدل تفضيلات الأطراف أثناء التنفيذ، ولا نعامل الرفض بوصفه حذفًا للاسم من البيانات الأصلية.
| رقم | العرض | قرار المستقبل |
|---|---|---|
| 1 | A→X | يحتفظ بـA |
| 2 | B→Y | يحتفظ بـB |
| 3 | C→X | يستبدل A بـC |
| 4 | D→Y | يستبدل B بـD |
| 5 | A→W | يحتفظ بـA |
| 6 | B→W | يستبدل A بـB |
| 7 | A→Z | يحتفظ بـA |
في العرض الثالث يقارن X بين C وA: ترتيب C ثانٍ وترتيب A ثالث، لذلك يحتفظ بـC. وفي السادس يقارن W بين B وA: كلاهما قبله في وقت ما، لكنه يفضل B. لا يعني ذلك أن العرض المتأخر يفوز دائمًا؛ القائمة هي التي تحسم، لا ساعة الوصول.
انتهى الطابور وأصبح لكل اسم شريك. نقرأ المقبولين عند المستقبلين: W يحتفظ بـB، وX بـC، وY بـD، وZ بـA. عند تحويل هذا التمثيل إلى قائمة للجانب الأول نكتب A–Z وB–W وC–X وD–Y؛ الانتباه لاتجاه القاموس يمنع عرض الأزواج بأسماء متبادلة خطأ.
ابحث عن اعتراض يحتاج موافقة الطرفين
خذ مطابقة مختلفة: A–W وB–X وC–Y وD–Z. يظهر كل اسم مرة واحدة، فهي تنجح في اختبار العدد وعدم التكرار. لكن B يفضل W على X، وW يفضل B على A. إذن B–W زوج يعترض وفق القاعدة المعلنة، رغم أن طرفيه ليسا حرين.
لا يكفي أن يرغب B في Y، مع أنه خياره الأول؛ في هذه المطابقة تقترن Y بـC، وهو خيارها الأول أيضًا، فلا تفضل B عليه. فاحصنا يمر على كل زوج محتمل ويختبر المقارنتين معًا. أعاد للمطابقة المعيبة الزوج B–W وحده، وأعاد قائمة فارغة لنتيجة العروض.
لماذا يحفظ الإجراء الاستقرار؟ لو فضل مبادر مستقبلًا على شريكه النهائي، فقد عرض عليه من قبل ورُفض. والمستقبل لا يستبدل المقبول إلا بمن يفضله، لذلك لا يفضل هذا المبادر على شريكه النهائي؛ لا يتحقق الاعتراض من الطرفين. [2]
احصر النتائج لتعرف ما الذي أثبته المثال
لأربعة أسماء في كل جانب توجد 24 مطابقة كاملة، لأننا نوزع أسماء W وX وY وZ على مواضع A وB وC وD دون تكرار. شغلنا فاحص الأزواج المعترضة على الأربع والعشرين، فبقيت نتيجتان فقط: نتيجة العروض الأولى، وA–Z وB–X وC–Y وD–W.
في النتيجة الأولى حصل A على خياره الثالث، وB على الثاني، وC وD على الأول. في الثانية بقي A عند الثالث، وأصبح B عند الثالث، وC وD عند الرابع. جميع هذه الرتب حسب قوائم الجانب الأول؛ لا نستنتج منها وحدها وضع الجانب الآخر.
أعدنا التشغيل مع W ثم X ثم Y ثم Z كمبادرين. قدم كل منهم عرضًا واحدًا فقط، فحصلنا على النتيجة الثانية. فيها حصل جميع أعضاء هذا الجانب على خيارهم الأول. مثالنا يبين أن قبول النتيجتين في فحص الاستقرار لا يجعلهما متساويتين عند كل طرف.
تضمن الخوارزمية في هذا النموذج أفضل شريك متاح للمبادر ضمن المطابقات المستقرة، لا ضمن جميع المطابقات الممكنة بلا شرط. وقد يتغير الناتج عند تبديل الجانب المبادر. [1]
اختبر الشروط قبل تعميم التشغيل
أعددنا 250 مجموعة قوائم مولدة ببذور ثابتة، خمسون لكل حجم من واحد إلى خمسة. وأضفنا جميع مجموعات التفضيلات الست عشرة لحجم اثنين. في كل حالة من الحالات الـ266 حصرنا المطابقات الكاملة، ثم قارنا الاستقرار وأفضلية رتبة كل مبادر بين النتائج المستقرة. وفحصنا تشغيل الجهة المعاكسة وتغيير ترتيب الطابور.
لأن كل مبادر يطلب كل مستقبل مرة على الأكثر، لا يتجاوز العدد n² عرضًا عند وجود n طرفًا في كل جانب. [2]
فحصنا هذا الحد وعدم تكرار زوج العرض في جميع المدخلات المختبرة. ورفض البرنامج ثلاث قوائم معيبة: صفًا يكرر اسمًا، وعددين مختلفين للطرفين، واسمًا خارج المجموعة. بلغ مجموع التأكيدات المنفذة 1599. هذه الاختبارات تخص ترتيبًا كاملًا وصارمًا وسعة واحدة؛ إذا غيرت تلك الشروط، فغيّر النموذج والفاحص معًا قبل الوثوق بالناتج.
المصادر
القوائم والرسوم ونتائج الحصر أُعدت لهذا المقال. أُعد النص بمساعدة الذكاء الاصطناعي، ولا يُنسب إلى مراجعة بشرية مستقلة.