مرجع
آخر الزيارات

الخوارزمية المجرية

938 كلمة•0 مشاهدة•🗒️ منذ يومين
باختصار: هذه الخوارزمية تطبق على مشكلة الاقتران الأمثل المتمثل بمصفوفة الحدوث R و عناصرها rij ≥ 0 . تتناول المقالة 15 قسماً، منها «{»، «الاجراءات» و«تحسينات الطريقة الأصلية».
المحتويات
  1. {
  2. الاجراءات
  3. تحسينات الطريقة الأصلية
  4. }
  5. صيغة كوهن ميونكرز للطريقة المجرية
  6. وإلا
  7. وإلا
  8. { تفحّص السطر من اليسار إلى اليمين
  9. الإجراء II
  10. التهيئة
  11. الإجراء I
  12. }
  13. تعريفات
  14. ui + vj > rij
  15. إذا كان عدد العناصر في التسلسل فردي

في البداية، هذه الخوارزمية تطبق على مشكلة الاقتران الأمثل المتمثل بمصفوفة الحدوث 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 في التسلسل }
  • }
  • }

ما رأيك في هذه المقالة؟

📝 هل في هذه المقالة خطأ؟

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