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

هذه الخوارزمية تطبق على مشكلة الاقتران الأمثل المتمثل بمصفوفة الحدوث **R** و عناصرها **r<sub>ij</sub> ≥ 0** . تبحث الخوارزمية عن عناصر **r<sub>ij</sub>** ليس لها أي صف مشترك (لا سطر مشترك و لا عمود مشترك) و مجموعها المتراكم  له أكبر قيمة ممكنة. صممت هذه الخوارزمية سنة 1955 من طرف هارولد كوهن.

## الخوارزمية
### تعريفات

تعرّف المتغيرات التالية :
**u<sub>i</sub>** يسمى **كمون السطر i**  ،  و **v<sub>j</sub> كمون العمود j** ، مع الشرط لكل عنصر **u<sub>i</sub> +  v<sub>j</sub> ≥ r<sub>ij</sub><br />**
المصفوفة **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

:::}

::}

تصغير

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

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

### صيغة كوهن ميونكرز للطريقة المجرية
المسألة تطرح بالنظر إلى مصفوفة **A** وسعها n×n تسمى مصفوفة التكلفة ، عناصرها **a<sub>ij</sub>**  أعداد حقيقية غير سالبة ، المطلوب هو إيجاد **n** عناصر لا تشترك في صف بحيث تحقق أقل مبلغ **a<sub>ij</sub>**∑** ممكن

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

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

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

==== الخوارزمبة ====
• لجميع أسطر **A**  أطرح أصغر عنصر في السطر من جميع عناصر السطر

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

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

طالما **k ij** غير مغطى في **A**

:لجميع العناصر a<sub>ij</sub>

::{

::إذا a<sub>ij</sub> غير مغطى فإن **aij = aij - h**

::إذا a<sub>ij</sub> مغطى بصف فإن **aij** يبقى على قيمته

::إذا a<sub>ij</sub> مغطى بصفين متقاطعين فإن **aij = aij + h**

::}

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

:}

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

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

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

تصغير

## وصلات خارجية

* شريط فيديو(طراز فلاش ، مدة 75 دقيقة) محاضرة عن «الطريقة المجرية» ألقاها هارولد كوهن في 13 يوليو 2010 أثناء ندوة EURO XXIV في بحوث العمليات بلشبونة ، البرتغال. يلفت الانتباه أن نسخة مطبوعة مختصرة لهذه المحاضرة قد نشرت كمقال.

## مراجع

تصنيف:استمثال توافقي