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

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

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

تعرّف المتغيرات التالية : 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}$
لجميع الأسطر في Q { تفحّص السطر من اليسار إلى اليمين
غيّر أول 1 تواجهه إلى *1 إذا لا يوجد *1 في عموده}

#### الإجراء I

// سرد عمليات الانتقال الممكنة بدءًا من عمود مؤهل لجميع أعمدة 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 في التسلسل }
    } // لا يوجد عمود مؤهل : لا يوجد انتقال ممكن ، الإسناد كامل

#### الإجراء II

    إذا لم يوجد سطر غير ضروري و لا عمود غير مغطى
       { كل *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

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

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

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

المسألة تطرح بالنظر إلى مصفوفة 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 هو الإسناد الأمثل
وصف الخوارزمية هذا لا يتطرق إلى تفاصيل إجراء اختيار أدنى تغطية في كل تكرار.

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

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

## مراجع

* ↑ KUHN, Harold W. The Hungarian method for the assignment problem. Naval research logistics quarterly, 1955, vol. 2, no 1‐2, p. 83-97
* ↑ KUHN, Harold W. Variants of the Hungarian method for assignment problems, 1956
* ↑ HALL, Marshall. An algorithm for distinct representatives. The American Mathematical Monthly, 1956, vol. 63, no 10, p. 716-717.
* ↑ FORD JR, Lester Randolph et FULKERSON, Delbert Ray. Solving the transportation problem. Management Science, 1956, vol. 3, no 1, p. 24-32.
* ↑ 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
* ↑ 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
* بوابة علم الحاسوب