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

تعرّف المتغيرات التالية :
u_i يسمى كمون السطر i ، و v_j كمون العمود j ، مع الشرط لكل عنصر u_i + v_j ≥ r_ij
المصفوفة Q ، تدعى مصفوفة المساواة و عناصرها q_ij

إذا u_i + v_j > r_ij فإن q_ij = 0

إذا u_i + v_j = r_ij والسطر i مسند للعمود j فإن *q_ij = 1

إذا u_i + v_j = r_ij والسطر i غير مسند للعمود j فإن q_ij = 1

عملية الانتقال : السطر i المسند في عمود j يتم إسناده إلى عمود k مع k ≠ j ، في المصفوفة Q ، الانتقال يستبدل *1 ب 1 ، و 1 ب *1 في نفس السطر
سطر ضروري : سطر مسند فيه إمكانية للانتقال ، في المصفوفة Q ، هو سطر يحتوي على *1 و 1 في عمود غير مغطى
عمود مغطى : عمود تم إليه إسناد سطر، لا توجد إمكانية انتقال ، في المصفوفة Q ، هو عمود يحتوي على *1 في سطر غير ضروري
عمود مؤهل : عمود لا يحتوي على *1
الإسناد كامل إذا لم يمكن إسناد سطرا غير مسند في عمود غير مسند إلا بعد القيام بانتقال

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

u_i = أكبر عنصر r_ij في كل سطرi
0 = v_j في كل عمود j
q_ij = 0 إذا u_i + v_j > r_ij

qij = 1  إذا ui + vj = rij

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

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

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

{ إذا كان العمود لا يحتوي على 1

{ انتقل إلى العمود التالي}

وإلا

// 1 موجود في العمود (نفرض j_k-1)

{ كرر لكل 1 موجود في العمود j_k-1 (نفرض في السطر i_k)

{ إذا وجد *1 في السطر i_k // فإن أي انتقال يعطي اسنادا كاملا

{ // بناء تسلسل 1 ، *1 ، 1 ، *1 ، 1 ، ...

ضع العلامات كالتالي :

1 في الموقع (i_k, j_k-1)

1* في الموقع (i_k, j_k)

1 في الموقع (i_k+1, j_k)

... ...... .....

إذا كان عدد العناصر في التسلسل فردي

{ // عثرنا على انتقال يحرر عمودًا يحتوي على 1 غير مسند

اعكس كل 1 إلى *1 و كل *1 إلى 1 في التسلسل }

}

}

}

} // لا يوجد عمود مؤهل : لا يوجد انتقال ممكن ، الإسناد كامل

إذا لم يوجد سطر غير ضروري و لا عمود غير مغطى

{ كل *1 هو الاسناد الأمثل}

وإلا

{ احسب (d = min (u_i + v_j - r_ij على الأسطر غير الضرورية والأعمدة غير المغطاة

إذا جميع الأسطر غير الضرورية لها u_i > 0

{ (m = min(d، u_i مأخوذ على جميع الأسطر غير الضرورية

لجميع الأسطر غير الضرورية u_i = u_i - m

لجميع الأعمدة المغطاة v_j = v_j + m

}

إذا كان سطر غير ضروري فيه 0 = u_i

{ (m = min(d، v_j مأخوذة على جميع الأعمدة غير المغطاة j

لجميع الأسطر الضرورية u_i = u_i + m

لجميع الأعمدة غير المغطاة v_j = v_j – m

}

}

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

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

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

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

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

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

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

طالما k < n

{

فليكن h قيمة أصغر عنصر a_ij غير مغطى في A

لجميع العناصر a_ij

{

إذا a_ij غير مغطى فإن a_ij = a_ij - h

إذا a_ij مغطى بصف فإن aij يبقى على قيمته

إذا a_ij مغطى بصفين متقاطعين فإن a_ij = a_ij + h

}

k = أدنى عدد الصفوف اللازمة لتغطية كل 0 في A

}

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

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

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