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

الخوارزمية المجرية (وتُسمَّى أيضًا خوارزمية Kuhn-Munkres) هي خوارزمية التحسين التجميعي التي تحلّ مسألة التخصيص — مطابقة n عامل/مورد إلى n مهمّة واحد-لواحد تحت مصفوفة تكلفة n×n، مع تقليل التكلفة الإجمالية — في زمن متعدّد الحدود O(n³). قدّم Harold Kuhn الخوارزمية في ورقته عام 1955 في *Naval Research Logistics Quarterly*؛ سُمِّيت تكريمًا لمبرهنات المطابقة الثنائية التي طوّرها في مطلع القرن العشرين الرياضيّان المجريّان Dénes König وJenő Egerváry. صاغ James Munkres الخوارزمية عام 1957 إجراءً متعدّد الحدود O(n³) رسميًا تمامًا، ومن ثَمّ التسمية الحديثة البديلة خوارزمية Kuhn-Munkres. مبدأ العمل: اطرح الحدود الدنيا للصفوف/الأعمدة (تخفيض)، جد مطابقة قصوى على خلايا الكلفة الصفرية بمبرهنة König-Egerváry، إن لم تكن كاملة طبّق إجراء تغطية متسلسلًا لتحديث المصفوفة، وكرّر حتى المطابقة الكاملة. أمثل مضمون، زمن متعدّد الحدود، تجميعي. البدائل الحديثة الأسرع: LAP — أقصر مسار توسيعي (Jonker وVolgenant 1987، أسرع 5-20× عمليًا)؛ خوارزمية المزاد (Bertsekas 1988، مهيّأة للتوازي). Kuhn (1955)، Munkres (1957).