إسناد أكبر عدد من المهام: لماذا نغيّر اختيارات سابقة؟

الخلاصة السريعة

في مثالنا، الإسناد A–X و C–Y يترك B و Z بلا إسناد، ولا يمكن إضافة زوج إليهما. لكن تغيير الزوجين السابقين إلى B–X و A–Y و C–Z يرفع العدد من 2 إلى 3، دون إعطاء شخص مهمتين أو إسناد مهمة لشخصين.

• نموذجنا مخطط ثنائي: أشخاص في جانب ومهام في الآخر، والحافة أهلية مسموحة. المطابقة تختار حواف لا تشترك في رأس؛ هدفنا أكبر عدد من الأزواج. [1]
• عدم إمكانية إضافة زوج مباشرة لا يثبت بلوغ أكبر عدد. المطابقة العظمى في العدد تختلف عن المطابقة التي لا تقبل إضافة حافة وحدها. [1]
• ابدأ في مثالنا بزوجي A–X و C–Y. بقي B و Z حُرّين، لكن B مؤهل لـ X فقط؛ لذلك لا يمكن إلحاق B–Z.
• المسار B→X→A→Y→C→Z يتناوب بين حواف غير مختارة ومختارة. يبدأ وينتهي برأسين حرين؛ تبديل حالة حوافه يزيد عدد الأزواج بواحد. [1]
• نحذف A–X و C–Y، ثم نختار B–X و A–Y و C–Z. الحساب 2 − 2 + 3 = 3، وهو الحد الأعلى هنا لوجود ثلاثة أشخاص وثلاث مهام.
• إذا ألغينا أهلية C لـ Z، تبقى Z بلا شخص مؤهل، ويصبح الحد الأقصى 2. هدف هذا المثال عدد الإسنادات فقط؛ لا يتضمن تكاليف أو تفضيلات أو أزمنة عمل.

حوّل الخيارات إلى حواف، والاختيارات إلى أزواج

المطابقة مجموعة حواف لا يشترك اثنان منها في رأس. وفي مخطط ثنائي تصل الحافة بين الجانبين. نبحث عن مطابقة ذات أكبر عدد من الحواف. [1]

في نموذجنا A مؤهل للمهمتين X و Y؛ و B للمهمة X فقط؛ و C للمهمتين Y و Z. هذه قائمة كاملة للأهلية: لا توجد حافة B–Y أو B–Z أو A–Z. كل شخص يقبل مهمة واحدة على الأكثر، وكل مهمة شخصًا واحدًا على الأكثر.

الرسم يعرض الأشخاص بترتيب B ثم A ثم C لتسهيل رؤية الخطوط. هذا ترتيب في الصفحة فقط، وليس ترتيب المعالجة. الخط الباهت خيار مسموح؛ والخط السميك زوج اخترناه. لا نطلب اختيار كل الحواف، بل اختيار أكبر مجموعة تحترم الحد الواحد عند كل طرف.

زوجان لا يمكن إضافة ثالث إليهما مباشرة

لنجرّب الأشخاص بترتيب A ثم B ثم C، ونأخذ أول مهمة متاحة حسب ترتيب أسماء المهام. نختار A–X أولًا. يصل الدور إلى B، لكن X مشغولة و B لا يملك خيارًا آخر، فنتركه دون مهمة. ثم نختار C–Y، وهي أول خيار متاح له.

أصبح لدينا زوجان:A–X و C–Y. الرأس الحر في جانب الأشخاص هو B، وفي جانب المهام Z. لا توجد حافة بينهما، وأي حافة مسموحة غير مختارة تشترك مع زوج قائم في رأس. لذا لا نستطيع إضافة زوج وحده مع إبقاء الزوجين كما هما.

المطابقة التي لا يمكن توسيعها بإضافة حافة وحدها تسمى maximal، أما maximum فتعني أكبر عدد ممكن. بلوغ الأولى لا يضمن الثانية. [1]

هذا الفرق مهم عند فحص نتيجة الاختيار المتتابع: قلة الخيارات المتبقية لا تكفي للحكم على أفضلية العدد. في المثال نفسه يوجد تغيير منسق يحل مشكلة B، دون تخفيف شرط الأهلية أو شرط المهمة الواحدة.

اتبع سلسلة تبديل تبدأ وتنتهي بطرف حر

مسار الزيادة مسار بسيط تتناوب حوافه بين غير مختارة ومختارة، وطرفاه غير مشغولين. قلب الاختيار على حوافه يضيف حافة أكثر مما يحذف، فتزيد المطابقة بواحد. [1]

نبدأ بالشخص B الحر ونتحرك إلى X عبر خيار B–X غير المختار. المهمة X مشغولة بالشخص A، فنعود إلى A على الحافة المختارة A–X. من A نستعمل خياره الآخر Y، لكن Y مشغولة بـ C، فنعود إلى C عبر C–Y. وأخيرًا نصل إلى Z، وهي حرة، عبر C–Z.

ترتيب الرؤوس هو B→X→A→Y→C→Z. الحواف الأولى والثالثة والخامسة غير مختارة، والثانية والرابعة مختارتان. لا يتكرر رأس في هذه السلسلة؛ وطرفاها B و Z هما الحران في الإسناد الأول.

نغيّر حالة حواف المسار معًا: نحذف A–X و C–Y، ونضيف B–X و A–Y و C–Z. لا نضيف الأزواج الجديدة إلى القديمة دون حذف؛ فالقيام بذلك سيعطي X شخصين، و A مهمتين، و Y شخصين، و C مهمتين.

بعد التبديل، يحصل B على X و A على Y و C على Z. احتفظنا بقائمة الأهلية نفسها وبحد واحد عند كل شخص ومهمة. تغير الاختيار، ولم نضف أهلية جديدة إلى الرسم. الحصيلة 2 − 2 + 3 = 3.

قارن النتيجة بحد العدد الأعلى

يلخص الجدول الأهلية والإسنادين. كل زوج في العمود الأخير مسموح، وكل اسم مهمة يظهر مرة واحدة. العدد 3 لا يمكن تجاوزه: لدينا ثلاثة أشخاص فقط، وكل منهم يقبل مهمة واحدة؛ ولدينا أيضًا ثلاث مهام فقط، وكل منها تقبل شخصًا واحدًا.

الإسناد النهائي إذن يحقق أكبر عدد في هذا المثال. ويمكن إثبات إجبارية اختياراته عند إسناد المهام كلها: لا بد أن يحصل B على X، لأنها خياره الوحيد. عندئذ يأخذ A المهمة Y، ويأخذ C المهمة Z. وجود ثلاثة أسماء على كل جانب وحده لم يكن كافيًا؛ ما أثبت الإسناد هو الأزواج المسموحة فعلًا.

غيّر شرط الأهلية لتختبر حدود النتيجة

احذف الحافة C–Z من قائمة الأهلية، وأبقِ كل شيء آخر. يصبح Z رأسًا معزولًا، فلا يمكن إسناد هذه المهمة إلى أحد. الحد الأعلى عندئذ 2 لأن المهمتين الممكن إسنادهما هما X و Y فقط، ويمكن تحقيقه مثلًا بزوجي A–X و C–Y.

لا يعمل مسارنا السابق بعد هذا الحذف: آخر انتقال C→Z غير مسموح. لذا لا تنقل نتيجة 3 إلى رسم تغيرت حوافه. ولا تعالج الأمر بتكرار إسناد المهمة X لشخصين، لأن ذلك يخرق سعة المهمة في النموذج.

لم نعط الحواف أسعارًا أو مددًا أو درجات جودة، ولم نسمح للشخص بأكثر من مهمة. المثال يجيب عن أكبر عدد ممكن من الإسنادات تحت هذه الشروط المحددة. إذا كانت مهمتك الفعلية ذات تكاليف أو سعات مختلفة، فأنت تحتاج نموذجًا يعبّر عنها قبل مقارنة الحلول.