خوارزمية هوبكروفت-كارب
المحتويات
على سبيل التعريف، هذه الخوارزمية تبحث عن الاقتران الأقصى في بيان ثنائي (G(U,V,E و هو الاقتران M ذو أكبر عدد ممكن من الحواف. هذه المشكلة NP-كاملة. خوارزمية هوبكروفت وكارب أول من حلت الاقتران الأقصى في وقت متعدد الأطراف. ونتناول فيما يلي مزيدًا من التفاصيل.
وفي هذا السياق، إن هذه المشكلة تحظى باهتمام عملي كبير، تم طرحها في خمسينيات القرن العشرين وتبقى اليوم ذات أهمية كبيرة مثلًا في ميدان التعلّم العميق وما يعرف بمشكلة تخصيص المهام في الأنظمة متعددة الروبوتات (أو أ سراب الروبوتات).
طالما (G(U،V،E لديه مسار M متزايد Pi
وفي هذا السياق، ابحث عن أكبر مجموعة من أقصر المسارات M-متزايدة {P1 ، P2 ، ... ، Pmax} التي تكون رؤوسها متمايزة
M ← M ⊖ P1 ⊖ P2 ⊖ ... ⊖ Pmax
تهاية طالما
كذلك، هنا العلانة ⊖ تدل على الفرق المتناظر أو الاختلاف الحصري للمجموعات
مصطلحات خوارزمية هوبكروفت كارب
من جانب آخر، الاقتران M هو الاقتران الأقصى إذا وفقط إذا كان (G(U,V,E لا يحتوي على مسار M-متزايد
- رأس على حافة تنتمي إلى الإقتران M يقال رأس مشبع في M
- رأس على حافة لا تنتمي إلى M يقال رأس حر بالنسبة إلى M
- الاقتران الأقصى هو اقتران يحتوي على أكبر عدد ممكن من الحواف في (G(U,V,E
- خوارزمية هوبكروفت كارب (1973)
- التهيئة M ← φ
- علامة φ هنا تعني المجموعة الفارغة
- مسار M-متزايد هو مسار M-متناوب كلا طرفيه حران
- يحتوي هذا المسار على حافة واحدة في E(G)-M إضافة إلى حواف M
- الخوارزمية تعتمد على نظرية بيرج (1957)
وفي هذا الصدد، اقتران كامل في بيان ليس بالضرورة ثنائي متكون من 2N رأس، هو اقتران يتكون من N حواف
كذلك، مسار M-متناوب في (G(U,V,E هو مسار تنتمي حوافه بالتناوب إلى اقتران (M ⊆ E(G و إلى المجموعته التكميلية E(G)-M
اِنغراز الإجراء الأساسي من أجل برمجة الخوارزمية
يجب إلغاء حواف ui→vj) E(G)-M) النازلة إلى مستوى أدنى
وفي السياق ذاته، في كل خطوة أو تكرار، عملية البحث عن أكبر مجموعة من أقصر مسارات Mi-متزايدة بدون رؤوس مشتركة ترتكز على اقتران موجود Mi-1.
ومن ناحية أخرى، تعليم البيان الفرعي حسب طبقات من الرؤوس ....، L0 ،L1 ، L2 ، تنتمي الطبقات الزوجية إلى U ، والطبقات الفردية إلى V. تحتوي L0 على رؤوس ui حرة، المستوى الأخير Lt هو أدنى مستوى يحتوي على رؤوس vi حرة
من جانب آخر، في الممارسة العملية، يمكن أن يؤدي تخصيص لخوارزمية BFS كل هذه الإجراءات في عملية موحدة في كل تكرار
وعلى صعيد آخر، استخرج البيان الفرعي الذي تتوافق فيه الطرق الموجهة من رأس ui حر إلى رأس vi حر واحدة تلو الأخرى مع أقصر مسارات M-متزايدة، لذلك يجب :
كذلك، وجّه (G(U,V,E بحيث تكون حواف M في اتجاه vi→ui و حواف E(G)-M في الاتجاه المعاكس ui → vi. يصبح هكذا (G(U,V,E بيانا موجها غير حلقي
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟