مشكلة الإقران المتكافئ
يهدف الإقران الأمثل إلي المزاوجة بين عناصر متساوية العدد منتمية لفصيلتين. يقوم كل عنصر س منتمي للنوع الأول بسرد العناصر المنتمية للنوع الثانى كلها بأفضلية اقترانه بها، و في النهاية يتكون الزوجان (س، ص). يعدهذا الاقتران هو الأمثل في أى من الحالتين التاليتين:
1- ألا يفضل العنصر س عنصراً آخر من النوعية الأخرى أكثر ممن اقترن به.
2- ألا يفضل ص عنصرا آخر من النوعية الأولى عن هذا الذي اقترن به.
إذن، تعد المزاوجة هي المثلي حين لا يتواجد أقران أفضل ممن اقترن بهما كل من س و ص. و لقد تم تعريف مشكلة الإقران الأمثل عن طريق الزواج غير المتعدد بين أفراد من جنسين مختلفين ثابتين مع الزمن على الوجه التالي:
بوجود عدد ن من الرجال والنساء، يقوم كل فرد بترتيب أفراد الجنس الآخر حسب الأفضلية. يتم إقران الرجال و النساء بحيث لا يفضل فرد من كلى المجموعتين شخصا آخر من المجموعة المقابلة أكثر ممن اقترن به وحينها يعتد هذا الاقران، وبشكل عملي، توجد تطبيقات لمشكلة الإقران الأمثل عن طريق خوارزميات لإيجاد الحل في مختلف المشاكل الحياتية و منها على سبيل المثال لا الحصر تكليف الأطباء المقيمين بالمستشفيات المختلفة. في عام 2012، حصل كل من لويد شابلي و ألفين روث على جائزة نوبل فى العلوم الاقتصادية، و ذلك تقديرا لمساهمتهما في نظرية التوزيع الأمثل في تصميم السوق.
حل المشكلة[عدل]
في عام 1962، أثبت دافيد جيل و لويد شابلى أن الوصول لحالة الإقران الأمثل دائما متاح بوجود عدد متساوٍ من الذكور و الإنات عن طريق خوارزمية جيل-شابلى.
تتكون خوارزمية جيل-شابلى من عدة تكرارات أو دورات. في أول دورة للخوارزمية، يقوم كل من الرجال بالتقدم لأكثر امرأة يفضلها و تقوم كل النساء بالموافقة غير النهائية على واحد ممن تقدموا لها حسب الأفضلية و تقوم برفض الآخرين، و بهذا يتكون عدد من الأزواج من النساء و الرجال المقترنين بصفة غير نهائية و يكون عدد هذه الأزواج أقل من أو مساو للعدد الكلى للرجال أو النساء. في كل من الدورات التالية، يتقدم كل رجل لم يرتبط بعد للمرأة التى لم يتقدم لها بعد حتى و إن كانت مرتبطة بترتيب الأفضلية بالنسبة له، و حينها إن كانت تلك المرأة مرتبطة بالفعل توافق عليه إن كان ذو أفضلية عن من كانت قد ارتبطت به بشكل مؤقت، أو ترفضه ان كان بترتيب أفضلية أقل ممن قد ارتبطت به أو حتى أقل ممن العروض الجديدة خلال هذه الدورة إن كانت لم ترتبط بعد. و تستمر الدورات حتى يقترن عدد ن من الرجال بعدد ن من النساء.
و تعد هعملية الإقران تلك من العمليات معقدة حسابياً حيث انها تتكون من عدد من العمليات قد يصل إلى مربع عدد الرجال/النساء، و بذا برمز O الكبير تكون العملية O(ن^2)
نتاج الخوارزمية[عدل]
هذه الخوارزمية تضمن كلٍ من:
يتم المقارنة للعدد الكلي للرجال و النساء
حيث انه في النهاية، لا يتبقى فرد دون اقتران، حيث أن الرجل سيكون قد تقدم لكل النساء في حالة الضرورة (تم رفضه من ن-1 من النساء أو بعدما اقترن بامرأة فضلت آخر عليه)
تكون تلك الزيجات مستقرة
بفرض أنه يوجد فردين في المجموعة: مريم و علىّ كلٍ منهما مرتبط بشخص ما. تضمن طريقة جيل-شابلى أنه بانتهاء الدورات، لن يفضل علىّ مريم أو تفضل مريم علىّ عن قرنائهم الحاليين.
إن كان عليّ قد يفضّل مريم عن قرينته الحالية، فهذا يعنى أنه قد تقدم لمريم قبل قرينته الحالية. و لو كانت مريم قد قبلت عرضه و لكنها لم تتزوج به بالنهاية، فهذا يعنى انها وافقت على من تفضلّه عن علىّ و بهذا فإنها حتماً لا تحب علىّ أكثر من زوجها الحالى. أما إن كانت مريم قد رفضت عرضه، فهذا يعنى أنها كانت مع من تحب بشكل مسبق لعلىّ.
و هذا ينفى احتمالية تفضيل أى منهما للآخر بعد الارتباط بآخرين.
الخوارزمية[عدل]
دالة الإقران الأمثل{
تُعَرَّف القائمتان أ تضم جميع الرجال، و ب تضم جميع النساء كغير مرتبطين
أعد لطالما تواجد رجل ج غير مرتبطين{
م: المرأة ذات أعلى أفضلية بالنسبة ل"ج" و لم يتقدم لها بعد
إذا لم تكن المرأة م مرتبطة، يرتبط (م، ج) بشكل مؤقت
ّإذا كانت المرأة م مرتبطة ب"د":
إذا فضّلت المرأة م الرجل ج عن د، يرتبط( م، ج) و يصبح الرجل د غير مرتبط
إذا لم تُفَضِّل المرأة م الرجل ج عن د، يظل (م، د) مرتبطين}
}
مثال[عدل]
أ = {ج، د، س}، و ب = {و، ز، ط}
يُعرف كل فرد ترتيب أفضلية كل الأفراد من القائمة بالنسبة له:
ج: و، ز، ط
د: ز، و، ط
س: و، ط، ز
و: س، ج، د
ز: ج، س، د
ط: ج، س، د
- أول تكرار: يرتبط كلٍ من (س، و) و (د، ز) و ترفض "و" "ج"
- ثانى تكرار: يرتبط (ج، ز) و يصبح "د" غير مرتبط مرة ثانية
- ثالث تكرار: يتقدم "د" ل "و" و لكنها تظل مع "س" حيث أنه أكثر من "د" أفضلية
- رابع تكرار: يرتبط (د، ط)
تطبيقات مشابهة[عدل]
- مشكلة قرناء السكن: تشبه مشكلة الإقران الأمثل لكنها تختلف عنها حيث يقبع كل الأفراد في فصيلة واحدة بدلا من تكوُّن فصيلتين متساويين في العدد.
- مشكلة الأطباء النوبتجيين بالمشافى / إلحاق الطلبة بالكليات: تختلف عن مشكلة الإرقان الأمثل في تكرار ارتباط المشفي بأكثر من طبيب او التحاق أكثر من طالب بقسم ما في الكلية. يتم الامثلة إما لصالح المشفى / الكلية، أو لصالح الأطباء / الطلاب.
- مشكلة الإقران بالعقود: و هى الصورة الأعم لمشكلة الإقران الأمثل حيث يتم إقرار التعاقدات مع الموظفين بأجور متغيرة و وَفق شروط متغيرة أيضاً.
روابط خارجية[عدل]
- Interactive Flash Demonstration of SMP
- http://kuznets.fas.harvard.edu/~aroth/alroth.html#NRMP
- http://www.dcs.gla.ac.uk/research/algorithms/stable/EGSapplet/EGS.html
- Gale–Shapley JavaScript Demonstration
- SMP Lecture Notes
مراجع[عدل]
Gale, D.; Shapley, L. S. (1962). "College Admissions and the Stability of Marriage". American Mathematical Monthly 69: 9–14. JSTOR 2312726
S Sawhney. (2014,Jan.) "Gale Shapley Algorithm for Stable Matching", Retrieved from https://www.youtube.com/watch?v=pc5WSJkFk24
Emily Reihl, PhD. Mathematical Sciences Research Institute. (2014, Sept.)"Stable Marriage Problem - Numberphile", Retrieved from https://www.youtube.com/watch?v=Qcv1IqHWAzg
