حلّال مشكلة الزواج المستقر — أوجد تطابقًا مستقرًا بين مجموعتين
يجد حلّال مشكلة الزواج المستقر الخاص بنا تطابقًا بين مجموعتين متساويتي الحجم — مُقترحين ومُراجعين — بحيث لا يوجد زوج يُفضّل كلاهما بعضهما البعض على شريكه المُخصص، باستخدام خوارزمية Gale-Shapley للقبول المؤجل، بمعطى قائمة تفضيلات مُرتبة لكل مشارك على المجموعة الأخرى.
إجابة سريعة
أدخل قوائم تفضيلات مُرتبة لمجموعتين متساويتي الحجم لإيجاد تطابق مستقر فورًا عبر خوارزمية Gale-Shapley.
سطر واحد لكل مُقترح: الاسم: تفضيل1, تفضيل2, ... يُرتب كل مُراجع، مثل A1: B2, B1, B3.
سطر واحد لكل مُراجع: الاسم: تفضيل1, تفضيل2, ... يُرتب كل مُقترح، مثل B1: A3, A1, A2.
كيفية استخدام حلّال مشكلة الزواج المستقر — خوارزمية Gale-Shapley عبر الإنترنت
- 1
أدخل تفضيلات كل مُقترح كسطر واحد: الاسم: تفضيل1, تفضيل2, تفضيل3, ... (مُرتبة من الأكثر إلى الأقل تفضيلًا).
- 2
أدخل تفضيلات كل مُراجع بنفس الطريقة، مُرتبًا كل مُقترح.
- 3
انقر على 'احسب' لإيجاد تطابق مستقر عبر خوارزمية Gale-Shapley.
لماذا تستخدم حلّال مشكلة الزواج المستقر — خوارزمية Gale-Shapley عبر الإنترنت؟
التطابق بين مجموعتين 'مستقر' إذا لم يوجد زوج يُفضّل كلاهما أن يكونا معًا بدلاً من شريكيهما المُخصصين الحاليين — سيكون لدى مثل هذا الزوج حافز لكسر تطابقاتهما الحالية، مما يجعل التطابق غير مستقر. تجد خوارزمية Gale-Shapley دائمًا تطابقًا مستقرًا (نتيجة أساسية حازت على جائزة نوبل في الاقتصاد لعام 2012): يقترح كل مُقترح غير مُتطابق على أفضل خياره المتبقي، يقبل كل مُراجع مؤقتًا أفضل عرض تلقاه حتى الآن ويرفض الباقي (حتى إزاحة تطابق سابق إذا وصل عرض أفضل)، ويتكرر هذا حتى يتطابق الجميع. النتيجة ليست مستقرة فحسب بل مثلى للمُقترح — يحصل كل مُقترح على أفضل شريك ممكن قد يحصل عليه في أي تطابق مستقر.
الأسئلة الشائعة
أدوات ذات صلة
آلة حاسبة تدفق الشبكة — أقصى تدفق عبر خوارزمية Edmonds-Karp عبر الإنترنت
أوجد أقصى تدفق من مصدر إلى مصرف في رسم بياني موجه ذي سعات باستخدام خوارزمية Edmonds-Karp. آلة حاسبة مجانية بإدخال قائمة حواف بسيط.
آلة حاسبة تلوين الرسم البياني — خوارزمية Welsh-Powell عبر الإنترنت
لوّن رؤوس رسم بياني بحيث لا تشترك عقدتان متصلتان في نفس اللون، باستخدام خوارزمية Welsh-Powell الجشعة. آلة حاسبة مجانية بإدخال قائمة حواف بسيط.
آلة حاسبة التباديل — احسب P(n,r) عبر الإنترنت
احسب التباديل P(n,r) — عدد طرق ترتيب r عناصر من أصل n عنصرًا حيث يهم الترتيب. آلة حاسبة مجانية مع حلول خطوة بخطوة وتفصيل الصيغة.