|
تضامنًا مع حق الشعب الفلسطيني |
خوارزمية هوبكروفت-كارب
 | هذه مقالة غير مراجعة. (يونيو 2019) |
خوارزمية هوبكروفت-كارب |
هذه الخوارزمية تبحث عن الاقتران الأقصى في بيان ثنائي (G(U,V,E و هو الاقتران M ذو أكبر عدد ممكن من الحواف. هذه المشكلة NP-كاملة. خوارزمية هوبكروفت وكارب أول من حلت الاقتران الأقصى في وقت متعدد الأطراف.[1]
إن هذه المشكلة تحظى باهتمام عملي كبير، تم طرحها في خمسينيات القرن العشرين وتبقى اليوم ذات أهمية كبيرة على سبيل المثال في ميدان التعلّم العميق وما يعرف بمشكلة تخصيص المهام في الأنظمة متعددة الروبوتات (أو أ سراب الروبوتات).
مصطلحات خوارزمية هوبكروفت كارب
رأس على حافة تنتمي إلى الإقتران M يقال رأس مشبع في M
رأس على حافة لا تنتمي إلى M يقال رأس حر بالنسبة إلى M
الاقتران الأقصى هو اقتران يحتوي على أكبر عدد ممكن من الحواف في (G(U,V,E
اقتران كامل في بيان ليس بالضرورة ثنائي متكون من 2N رأس، هو اقتران يتكون من N حواف
مسار M-متناوب في (G(U,V,E هو مسار تنتمي حوافه بالتناوب إلى اقتران (M ⊆ E(G و إلى المجموعته التكميلية E(G)-M
مسار M-متزايد هو مسار M-متناوب كلا طرفيه حران
يحتوي هذا المسار على حافة واحدة في E(G)-M إضافة إلى حواف M
الخوارزمية تعتمد على نظرية بيرج (1957)[2] الاقتران M هو الاقتران الأقصى إذا وفقط إذا كان (G(U,V,E لا يحتوي على مسار M-متزايد
خوارزمية هوبكروفت كارب (1973)
- التهيئة M ← φ
- علامة φ هنا تعني المجموعة الفارغة
- طالما (G(U،V،E لديه مسار M متزايد Pi
- ابحث عن أكبر مجموعة من أقصر المسارات M-متزايدة {P1 ، P2 ، ... ، Pmax} التي تكون رؤوسها متمايزة
- M ← M ⊖ P1 ⊖ P2 ⊖ ... ⊖ Pmax
- تهاية طالما
هنا العلانة ⊖ تدل على الفرق المتناظر أو الاختلاف الحصري للمجموعات
اِنغراز الإجراء الأساسي من أجل برمجة الخوارزمية
في كل خطوة أو تكرار، عملية البحث عن أكبر مجموعة من أقصر مسارات Mi-متزايدة بدون رؤوس مشتركة ترتكز على اقتران موجود Mi-1.
- وجّه (G(U,V,E بحيث تكون حواف M في اتجاه vi→ui و حواف E(G)-M في الاتجاه المعاكس ui → vi. يصبح هكذا (G(U,V,E بيانا موجها غير حلقي
- استخرج البيان الفرعي الذي تتوافق فيه الطرق الموجهة من رأس ui حر إلى رأس vi حر واحدة تلو الأخرى مع أقصر مسارات M-متزايدة، لذلك يجب :
- تعليم البيان الفرعي حسب طبقات من الرؤوس ....، L0 ،L1 ، L2 ، تنتمي الطبقات الزوجية إلى U ، والطبقات الفردية إلى V. تحتوي L0 على رؤوس ui حرة، المستوى الأخير Lt هو أدنى مستوى يحتوي على رؤوس vi حرة
- يجب إلغاء حواف ui→vj) E(G)-M) النازلة إلى مستوى أدنى
- في الممارسة العملية، يمكن أن يؤدي تخصيص لخوارزمية BFS كل هذه الإجراءات في عملية موحدة في كل تكرار
مراجع
- ^ HOPCROFT, John E. et KARP, Richard M. An n^5/2 algorithm for maximum matchings in bipartite graphs. SIAM Journal on computing, 1973, vol. 2, no 4, p. 225-231.
- ^ BERGE, Claude. Two theorems in graph theory. Proceedings of the National Academy of Sciences of the United States of America, 1957, vol. 43, no 9, p. 842.
