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

هذه الخوارزمية تطبق على مشكلة الاقتران الأمثل المتمثل بمصفوفة الحدوث R و عناصرها rij ≥ 0 . تبحث الخوارزمية عن عناصر rij ليس لها أي صف مشترك (لا سطر مشترك و لا عمود مشترك) و مجموعها المتراكم له أكبر قيمة ممكنة. صممت هذه الخوارزمية سنة 1955 من طرف هارولد كوهن.[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 ، و 1 ب *1 في نفس السطر
سطر ضروري : سطر مسند فيه إمكانية للانتقال ، في المصفوفة Q ، هو سطر يحتوي على *1 و 1 في عمود غير مغطى
عمود مغطى : عمود تم إليه إسناد سطر، لا توجد إمكانية انتقال ، في المصفوفة Q ، هو عمود يحتوي على *1 في سطر غير ضروري
عمود مؤهل : عمود لا يحتوي على *1
الإسناد كامل إذا لم يمكن إسناد سطرا غير مسند في عمود غير مسند إلا بعد القيام بانتقال

الاجراءات

[عدل]

الخوارزمية بعد عملية تهيئة تتمثل في التكرار المتناوب لإجراءين (I البحث عن انتقال متزايد) و (II تسوية المصفوفة Q)

التهيئة

[عدل]

ui = أكبر عنصر rij في كل سطرi
0 = vj في كل عمود j
qij = 0 إذا ui + vj > rij 

qij = 1  إذا ui + vj = rij

لجميع الأسطر في Q
{ تفحّص السطر من اليسار إلى اليمين

غيّر أول 1 تواجهه إلى *1 إذا لا يوجد *1 في عموده}

الإجراء I

[عدل]

// سرد عمليات الانتقال الممكنة بدءًا من عمود مؤهل
لجميع أعمدة Q المؤهلة (لا تحتوي على *1)

{ إذا كان العمود لا يحتوي على 1
{ انتقل إلى العمود التالي}
وإلا
// 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 و كل *1 إلى 1 في التسلسل }
}
}
}
} // لا يوجد عمود مؤهل : لا يوجد انتقال ممكن ، الإسناد كامل

الإجراء II

[عدل]
إذا لم يوجد سطر غير ضروري و لا عمود غير مغطى
{ كل *1 هو الاسناد الأمثل}
وإلا
{ احسب (d = min (ui + vj - rij على الأسطر غير الضرورية والأعمدة غير المغطاة
إذا جميع الأسطر غير الضرورية لها ui > 0
{ (m = min(d، ui مأخوذ على جميع الأسطر غير الضرورية
لجميع الأسطر غير الضرورية ui = ui - m
لجميع الأعمدة المغطاة vj = vj + m
}
إذا كان سطر غير ضروري فيه 0 = ui
{ (m = min(d، vj مأخوذة على جميع الأعمدة غير المغطاة j
لجميع الأسطر الضرورية ui = ui + m
لجميع الأعمدة غير المغطاة vj = vj – m
}
}

تحسينات الطريقة الأصلية

[عدل]

ألحق كوهن تعديلات [2] على الطريقة المجرية مستوحاة من الأعمال المتزامنة لمارشال هول [3] و فورد و فيولكرسون [4] ، و خاصة ميونكرز الذي أتى بالبرهان النظري لصحة الخوارزمية.[5]

تتمثل مراجعة الطريقة المجرية في إعادة النظر إلى الإجراء I للخوارزمية من زاوية نظرية البيان. يجدي اعتبار Q مصفوفة حدوث لبيان ثنائي و عناصرها التي تساوي *1 تمثل حواف إقتران M ، في هذه الحالة عملية إيجاد تسلسل 1 ،*1 ، 1، *1 ، 1 ... يرجع إلى البحث عن مسار متزايد حول الاقتران M. لم يأتي الحل الأمثل لهذا المشكل إلا بعد عمل هوبكروفت و كارب حيث أصبحت طريقتهما تستغل على نطاق واسع في إطار الاسناد الأمثل لغرض البرمجة الحازمة لالإجراء I

صيغة كوهن ميونكرز للطريقة المجرية

[عدل]

المسألة تطرح بالنظر إلى مصفوفة A وسعها n×n تسمى مصفوفة التكلفة ، عناصرها aij أعداد حقيقية غير سالبة ، المطلوب هو إيجاد n عناصر لا تشترك في صف بحيث تحقق أقل مبلغ aij∑ ممكن

ترجع الطريقة المستخدمة لحل هذه المشكلة إلى جهود كوهن ثم ميونكرر لتحسين وتبسيط تطبيق الطريقة المجرية

المصطلحات

[عدل]

الصف يعني سطر أو عمود من المصفوفة A

الغطاء هو مجموعة الصفوف التي تحتوي على جميع الأصفار 0 في A

الخوارزمبة

[عدل]

• لجميع أسطر A أطرح أصغر عنصر في السطر من جميع عناصر السطر

• لجميع أعمدة A أطرح أصغر عنصر في العمود من جميع عناصر العمود

• قم بتغطية كل 0 في المصفوفة A بأقل عدد ممكن من الصفوف k

طالما k < n

{
فليكن h قيمة أصغر عنصر aij غير مغطى في A
لجميع العناصر aij
{
إذا aij غير مغطى فإن aij = aij - h
إذا aij مغطى بصف فإن aij يبقى على قيمته
إذا aij مغطى بصفين متقاطعين فإن aij = aij + h
}
k = أدنى عدد الصفوف اللازمة لتغطية كل 0 في A
}

ليكن G البيان الثنائي الذي يمثل حوافه كل 0 في A

الاقتران الكامل في G هو الإسناد الأمثل

وصف الخوارزمية هذا لا يتطرق إلى تفاصيل إجراء اختيار أدنى تغطية في كل تكرار.

وصلات خارجية

[عدل]

مراجع

[عدل]
  1. ^ KUHN, Harold W. The Hungarian method for the assignment problem. Naval research logistics quarterly, 1955, vol. 2, no 1‐2, p. 83-97
  2. ^ KUHN, Harold W. Variants of the Hungarian method for assignment problems, 1956
  3. ^ HALL, Marshall. An algorithm for distinct representatives. The American Mathematical Monthly, 1956, vol. 63, no 10, p. 716-717.
  4. ^ FORD JR, Lester Randolph et FULKERSON, Delbert Ray. Solving the transportation problem. Management Science, 1956, vol. 3, no 1, p. 24-32.
  5. ^ MUNKRES, James. Algorithms for the assignment and transportation problems. Journal of the society for industrial and applied mathematics, 1957, vol. 5, no 1, p. 32-38
  6. ^ KUHN, Harold W. A tale of three eras: The discovery and rediscovery of the Hungarian Method. European Journal of Operational Research, vol. 219, no 3, p. 641-651, 2012