الخوارزمية المجرية
المحتويات
في البداية، هذه الخوارزمية تطبق على مشكلة الاقتران الأمثل المتمثل بمصفوفة الحدوث R و عناصرها rij ≥ 0 . تبحث الخوارزمية عن عناصر rij ليس لها أي صف مشترك (لا سطر مشترك و لا عمود مشترك) و مجموعها المتراكم له أكبر قيمة ممكنة. صممت هذه الخوارزمية سنة 1955 من طرف هارولد كوهن. ونتناول فيما يلي مزيدًا من التفاصيل.
الخوارزمية
{
ومن جهة أخرى، ليكن G البيان الثنائي الذي يمثل حوافه كل 0 في Aالاقتران الكامل في G هو الإسناد الأمثل
إضافةً إلى ذلك، وصف الخوارزمية هذا لا يتطرق إلى تفاصيل إجراء اختيار أدنى تغطية في كل تكرار.
ومن ناحية أخرى، إذا aij مغطى بصفين متقاطعين فإن aij = aij + h}k = أدنى عدد الصفوف اللازمة لتغطية كل 0 في A}
وفي السياق ذاته، إذا aij غير مغطى فإن aij = aij - hإذا aij مغطى بصف فإن aij يبقى على قيمته
الاجراءات
إضافةً إلى ذلك، الخوارزمية بعد عملية تهيئة تتمثل في التكرار المتناوب لإجراءين (I البحث عن انتقال متزايد) و (II تسوية المصفوفة Q)
تحسينات الطريقة الأصلية
من جهة ثانية، تتمثل مراجعة الطريقة المجرية في إعادة النظر إلى الإجراء I للخوارزمية من زاوية نظرية البيان. يجدي اعتبار Q مصفوفة حدوث لبيان ثنائي و عناصرها التي تساوي *1 تمثل حواف إقتران M ، في هذه الحالة عملية إيجاد تسلسل 1 ،*1 ، 1، *1 ، 1 ... يرجع إلى البحث عن مسار متزايد حول الاقتران M. لم يأتي الحل الأمثل لهذا المشكل إلا بعد عمل هوبكروفت و كارب حيث أصبحت طريقتهما تستغل على نطاق واسع في إطار الاسناد الأمثل لغرض البرمجة الحازمة لالإجراء I
وفي هذا السياق، ألحق كوهن تعديلات على الطريقة المجرية مستوحاة من الأعمال المتزامنة لمارشال هول و فورد و فيولكرسون ، و خاصة ميونكرز الذي أتى بالبرهان النظري لصحة الخوارزمية.
}
- إذا كان سطر غير ضروري فيه 0 = ui
- { (m = min(d، vj مأخوذة على جميع الأعمدة غير المغطاة j
- لجميع الأسطر الضرورية ui = ui + m
- لجميع الأعمدة غير المغطاة vj = vj – m
- }
- }
صيغة كوهن ميونكرز للطريقة المجرية
- • لجميع أسطر A أطرح أصغر عنصر في السطر من جميع عناصر السطر
- • لجميع أعمدة A أطرح أصغر عنصر في العمود من جميع عناصر العمود
- • قم بتغطية كل 0 في المصفوفة A بأقل عدد ممكن من الصفوف kطالما k < n{
- فليكن h قيمة أصغر عنصر aij غير مغطى في Aلجميع العناصر aij
في هذا الإطار، المصطلحات الصف يعني سطر أو عمود من المصفوفة Aالغطاء هو مجموعة الصفوف التي تحتوي على جميع الأصفار 0 في A الخوارزمبة
ومن ناحية أخرى، المسألة تطرح بالنظر إلى مصفوفة A وسعها n×n تسمى مصفوفة التكلفة ، عناصرها aij أعداد حقيقية غير سالبة ، المطلوب هو إيجاد n عناصر لا تشترك في صف بحيث تحقق أقل مبلغ aij∑ ممكن
علاوةً على ذلك، ترجع الطريقة المستعملة لحل هذه المشكلة إلى جهود كوهن ثم ميونكرر لتحسين وتبسيط تطبيق الطريقة المجرية
وإلا
- { احسب (d = min (ui + vj - rij على الأسطر غير الضرورية والأعمدة غير المغطاة
- إذا جميع الأسطر غير الضرورية لها ui > 0
- { (m = min(d، ui مأخوذ على جميع الأسطر غير الضرورية
- لجميع الأسطر غير الضرورية ui = ui - m
- لجميع الأعمدة المغطاة vj = vj + m
وإلا
- // 1 موجود في العمود (نفرض jk-1)
- { كرر لكل 1 موجود في العمود jk-1 (نفرض في السطر ik)
- { إذا وجد *1 في السطر ik // فإن أي انتقال يعطي اسنادا كاملا
- { // بناء تسلسل 1 ، *1 ، 1 ، *1 ، 1 ، ...
- ضع العلامات كالتالي :
- 1 في الموقع (ik, jk-1)
- 1* في الموقع (ik, jk)
- 1 في الموقع (ik+1, jk)
- ... ...... .....
{ تفحّص السطر من اليسار إلى اليمين
غيّر أول 1 تواجهه إلى *1 إذا لا يوجد *1 في عموده}
الإجراء II
إذا لم يوجد سطر غير ضروري و لا عمود غير مغطى
{ كل *1 هو الاسناد الأمثل}
التهيئة
- ui = أكبر عنصر rij في كل سطرi
- 0 = vj في كل عمود j
- qij = 0 إذا
الإجراء I
- // سرد عمليات الانتقال الممكنة بدءًا من عمود مؤهل
- لجميع أعمدة Q المؤهلة (لا تحتوي على *1)
- { إذا كان العمود لا يحتوي على 1
- { انتقل إلى العمود التالي}
}
} // لا يوجد عمود مؤهل : لا يوجد انتقال ممكن ، الإسناد كامل
تعريفات
ومن جهة أخرى، الإسناد كامل إذا لم يمكن إسناد سطرا غير مسند في عمود غير مسند إلا بعد القيام بانتقال
سطر ضروري : سطر مسند فيه إمكانية للانتقال ،
وفي هذا السياق، في المصفوفة Q ، الانتقال يستبدل *1 ب 1 ، و 1 ب *1 في نفس السطر
إضافةً إلى ذلك، عمود مغطى : عمود تم إليه إسناد سطر، لا توجد إمكانية انتقال ،
عمود مؤهل : عمود لا يحتوي على *1
في المصفوفة Q ، هو عمود يحتوي على *1 في سطر غير ضروري
- تعرّف المتغيرات التالية :
- ui يسمى كمون السطر i ، و vj كمون العمود j ، مع الشرط لكل عنصر ui + vj ≥ rij
- المصفوفة Q ، تدعى مصفوفة المساواة و عناصرها qij
- إذا ui + vj > rij فإن qij = 0
- إذا ui + vj = rij والسطر i مسند للعمود j فإن *qij = 1
- إذا ui + vj = rij والسطر i غير مسند للعمود j فإن qij = 1
من جهة ثانية، عملية الانتقال : السطر i المسند في عمود j يتم إسناده إلى عمود k مع k ≠ j ،
في المصفوفة Q ، هو سطر يحتوي على *1 و 1 في عمود غير مغطى
ui + vj > rij
لجميع الأسطر في Q
qij = 1 إذا ui + vj = rij
إذا كان عدد العناصر في التسلسل فردي
- { // عثرنا على انتقال يحرر عمودًا يحتوي على 1 غير مسند
- اعكس كل 1 إلى *1 و كل *1 إلى 1 في التسلسل }
- }
- }
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟