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

الخوارزمية المجرية أو الطريقة المجرية هي خوارزمية تحسين توافقي تحل مسألة التخصيص في وقت متعدد الحدود ، وقد سبقت طرقًا أولية-ثنائية لاحقة . طُوّرت ونُشرت عام 1955 على يد هارولد كون ، الذي أطلق عليها اسم "الطريقة المجرية" لأنها استندت بشكل كبير إلى أعمال سابقة لعالمي الرياضيات المجريين دينيس كونيغ وجينو إيغرفاري . ^[¹^]^[²^] مع ذلك، في عام 2006، اكتُشف أن كارل غوستاف جاكوبي قد حلّ مسألة التخصيص في القرن التاسع عشر، ونُشر الحل بعد وفاته عام 1890 باللغة اللاتينية. ^[³^]

قام جيمس مونكرز بمراجعة الخوارزمية عام 1957 ولاحظ أنها متعددة الحدود (بشكل قوي) . ^{[ 4 ]} ومنذ ذلك الحين، عُرفت الخوارزمية أيضًا باسم خوارزمية كون-مونكرز أو خوارزمية تعيين مونكرز . وكان التعقيد الزمني للخوارزمية الأصلية هو $O(n^{4})$ ومع ذلك، لاحظ كل من إدموندز وكارب ، وتوميزاوا بشكل مستقل، أنه يمكن تعديله لتحقيق $O(n^{3})$ وقت التشغيل. ^{[ 5 ]}^{[ 6 ]} قام فورد وفولكرسون بتوسيع الطريقة لتشمل مشاكل التدفق الأقصى العامة في شكل خوارزمية فورد-فولكرسون .

المشكلة

مثال

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

مهمة عامل	حمام نظيف	كنس الأرضيات	اغسل النوافذ
أليس	8 دولارات	4 دولارات	7 دولارات
بوب	5 دولارات	2 دولار	3 دولارات
كارول	9 دولارات	4 دولارات	8 دولارات

عند تطبيق الطريقة المجرية على الجدول أعلاه، نحصل على أقل تكلفة: 15 دولارًا، وذلك بتكليف أليس بتنظيف الحمام، وكارول بكنس الأرضيات، وبوب بغسل النوافذ. ويمكن التأكد من ذلك بالتجربة والخطأ.

ينظف مسح	أليس	بوب	كارول
أليس	—	17 دولارًا	16 دولارًا
بوب	18 دولارًا	—	18 دولارًا
كارول	15 دولارًا	16 دولارًا	—

(يقوم الشخص غير المكلف بغسل النوافذ)

تركيبة المصفوفة

في صياغة المصفوفة، لدينا مصفوفة من الرتبة n × n ، حيث يمثل العنصر في الصف i والعمود j تكلفة إسناد المهمة j للعامل i . المطلوب هو إيجاد طريقة لتوزيع المهام على العمال، بحيث تُسند كل مهمة إلى عامل واحد، ويُسند كل عامل مهمة واحدة، بحيث تكون التكلفة الإجمالية للتوزيع في أدنى حد ممكن.

يمكن التعبير عن ذلك بتبديل صفوف مصفوفة التكلفة C لتقليل أثر المصفوفة،

\min _{P}\operatorname {Tr} (PC)\;,

حيث P هي مصفوفة التبديل . (وبصورة مكافئة، يمكن تبديل الأعمدة باستخدام CP .)

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

صياغة الرسم البياني ثنائي الأجزاء

يمكن وصف الخوارزمية بشكل مكافئ من خلال صياغة المشكلة باستخدام رسم بياني ثنائي الأجزاء. لدينا رسم بياني ثنائي الأجزاء كامل $G=(S,T;E)$ مع $n$ من رؤوس العمال ( $S$ ) و $n$ من رؤوس الوظائف ( $T$ )، ولكل حافة ( $E$ ) تكلفة $c(i,j)$ نريد إيجاد تطابق مثالي بأقل تكلفة إجمالية.

الخوارزمية من حيث الرسوم البيانية الثنائية

لنقم باستدعاء دالة $y:(S\cup T)\to \mathbb {R}$ احتمال إذا $y(i)+y(j)\leq c(i,j)$ لكل $i\in S,j\in T$ .

قيمة الجهد y هي مجموع الجهد على جميع الرؤوس $:$

\sum _{v\in S\cup T}y(v)

.

تكلفة كل تطابق مثالي لا تقل عن قيمة كل جهد محتمل. ويتضح ذلك من خلال ملاحظة أن التكلفة الإجمالية للتطابق هي مجموع تكاليف جميع الحواف التي يحتويها. تكلفة كل حافة لا تقل عن مجموع جهود نقاط نهايتها. وبما أن التطابق مثالي، فإن كل رأس يمثل نقطة نهاية لحافة واحدة فقط. وبالتالي، فإن التكلفة الإجمالية لا تقل عن إجمالي الجهد المحتمل.

تجد الطريقة الهنغارية تطابقًا مثاليًا وقيمة محتملة بحيث تتساوى تكلفة التطابق مع القيمة المحتملة. وهذا يثبت أن كليهما مثالي. في الواقع، تجد الطريقة الهنغارية تطابقًا مثاليًا للحواف الضيقة : حافة $ij$ يُطلق عليه اسم ضيق بالنسبة لـ $y$ المحتمل إذا $y(i)+y(j)=c(i,j)$ لنرمز إلى الرسم البياني الفرعي للحواف الضيقة بـ $G_{y}$ تكلفة التوافق المثالي في $G_{y}$ (إن وجد) يساوي قيمة $y$ .

أثناء تنفيذ الخوارزمية ، نحافظ على جهد $y$ واتجاه $G_{y}$ (يرمز إليه بـ ${\overrightarrow {G_{y}}}$ تتميز هذه الطريقة بأن الحواف الموجهة من $النقطة T$ إلى $النقطة S$ تُشكل تطابقًا $M.$ في البداية، تكون $قيمة y$ تساوي صفرًا في كل مكان، وجميع الحواف موجهة من $S$ إلى $T$ (أي أن $M$ فارغة). في كل خطوة، إما أن نُعدّل قيمة $y$ لزيادة قيمتها، أو نُعدّل اتجاه الحواف للحصول على تطابق ذي حواف أكثر. نحافظ على شرط أن جميع حواف $M$ متقاربة. تنتهي العملية إذا كان $M$ تطابقًا تامًا.

في خطوة عامة، دع $R_{S}\subseteq S$ و $R_{T}\subseteq T$ لتكن الرؤوس غير المغطاة بواسطة $M$ (لذا $R_{S}$ يتكون من الرؤوس في $S$ التي لا تحتوي على حافة واردة و $R_{T}$ تتكون من الرؤوس في $T$ التي ليس لها حافة خارجية). ليكن $Z$ مجموعة الرؤوس التي يمكن الوصول إليها في ${\overrightarrow {G_{y}}}$ من $R_{S}$ عن طريق مسار موجه. ويمكن حساب ذلك باستخدام البحث بالعرض أولاً .

لو $R_{T}\cap Z$ إذا كانت غير فارغة، فقم بعكس اتجاه جميع الحواف على طول مسار موجه في ${\overrightarrow {G_{y}}}$ من $R_{S}$ ل $R_{T}$ وبالتالي، يزداد حجم المطابقة المقابلة بمقدار 1.

لو $R_{T}\cap Z$ إذا كان فارغًا، فليكن

{\displaystyle \Delta

$Δ$ مُعرَّف جيدًا لأنه يوجد على الأقل ضلع واحد من هذا النوع $ij$ يجب أن يكون موجودًا عندما لا يكون التطابق قد بلغ بعد أقصى حجم ممكن (انظر القسم التالي)؛ وهو موجب لأنه لا توجد حواف ضيقة بين $Z\cap S$ و $T\setminus Z$ قم بزيادة قيمة $y$ بمقدار $Δ$ على رؤوس $Z\cap S$ وخفض قيمة $y$ بمقدار $Δ$ على رؤوس $Z\cap T$ $لا تزال قيمة y$ الناتجة قيمة كامنة، وعلى الرغم من أن الرسم البياني $G_{y}$ مع التغييرات، لا يزال يحتوي على $M$ (انظر الأقسام الفرعية التالية). نوجه الحواف الجديدة من $S$ إلى $T.$ بحسب تعريف $Δ،$ فإن مجموعة $Z$ من الرؤوس التي يمكن الوصول إليها من $R_{S}$ يزداد (لاحظ أن عدد الحواف الضيقة لا يزداد بالضرورة). إذا تمت إضافة الرأس إلى $Z\cap T$ لا مثيل له (أي أنه موجود أيضًا في $R_{T}$ ثم في التكرار التالي، سيكون للرسم البياني مسار معزز.

نكرر هذه الخطوات حتى يصبح $M$ تطابقًا تامًا، وفي هذه الحالة نحصل على تخصيص بأقل تكلفة. زمن تشغيل هذه النسخة من الطريقة هو $O(n^{4})$ إذا زادت قيمة $M بمقدار$ $n$ مرة، وفي مرحلة لا تتغير فيها $M$ ، فإن عدد التغيرات المحتملة لا يتجاوز $n (لأن$ $Z$ تزداد في كل مرة). والوقت الكافي لحدوث تغيير محتمل هو $O(n^{2})$ .

دليل على أن الخوارزمية تحرز تقدماً

يجب أن نُثبت أنه طالما لم يصل التطابق إلى أقصى حجم ممكن، فإن الخوارزمية قادرة دائمًا على إحراز تقدم، أي إما زيادة عدد الحواف المتطابقة، أو تحسين حافة واحدة على الأقل. يكفي إثبات أن أحد الشرطين التاليين على الأقل يتحقق في كل خطوة:

$M$ هو أكبر حجم ممكن.
$G_{y}$ يحتوي على مسار مُعزز.
تحتوي $G على$ مسار ذي ذيل فضفاض : مسار من رأس ما في $R_{S}$ إلى رأس في $T\setminus Z$ يتكون هذا المسار من أي عدد (ربما صفر) من الحواف الضيقة متبوعة بحافة فضفاضة واحدة. وبالتالي، فإن الحافة الفضفاضة الأخيرة لمسار ذي ذيل فضفاض تكون من $Z\cap S$ ، مما يضمن أن $Δ$ محددة جيدًا.

إذا كان $M$ بأقصى حجم ممكن، فقد انتهينا بالطبع. وإلا، فبحسب مبرهنة بيرج ، يجب أن يوجد مسار مُعزِّز $P$ بالنسبة إلى $M$ في الرسم البياني الأساسي $G.$ ومع ذلك، قد لا يكون هذا المسار موجودًا في $G_{y}$ على الرغم من أن كل حافة ذات رقم زوجي في $P$ تكون محكمة وفقًا لتعريف $M$ ، إلا أن الحواف ذات الأرقام الفردية قد تكون فضفاضة وبالتالي غائبة عن $G_{y}$ تقع إحدى نهايتي النقطة $P$ في $R_{S}$ والآخر في $R_{T}$ لنفترض أن مدونة الويب تبدأ في $R_{S}$ إذا كانت كل حافة على $P$ محكمة، فإنها تظل مسارًا متزايدًا في $G_{y}$ وهكذا نكون قد انتهينا. وإلا، فلنترك $uv$ ليكن أول حافة غير مثبتة على النقطة $P.$ $v\notin Z$ عندئذٍ نكون قد وجدنا مسارًا ذا حواف غير متماسكة، وبذلك نكون قد انتهينا. وإلا، فإن $v$ يمكن الوصول إليه من مسار آخر $Q$ ذي حواف متماسكة من رأس في $R_{S}$ . يترك $P_{v}$ ليكن المسار الفرعي لـ $P$ الذي يبدأ عند $v$ ويستمر حتى النهاية، وليكن $P'$ ليكن المسار المتكون من السير على طول $Q$ حتى رأس على $P_{v}$ يتم الوصول إلى ذلك، ثم الاستمرار حتى نهاية $P_{v}$ لاحظ أن $P'$ هو مسار مُعزِّز في $G$ يحتوي على حافة سائبة أقل بواحدة على الأقل من $P.$ يمكن استبدال $P بـ$ $P'$ وتكررت عملية الاستدلال هذه (رسميًا، باستخدام الاستقراء على عدد الحواف غير المثبتة) حتى تم العثور على مسار مُعزز في $G_{y}$ أو يتم العثور على مسار ذي ذيل فضفاض في $G.$

دليل على أن تعديل الجهد y لا يغير M

لإثبات أن كل حافة في $M$ تبقى بعد تعديل $y$ ، يكفي إثبات أنه بالنسبة لحافة عشوائية في $M$ ، إما أن تكون كلتا نقطتي نهايتها، أو لا تكون أي منهما، في $Z.$ ولتحقيق هذه الغاية، ليكن $vu$ ليكن v حافة في $M$ من $T$ إلى $S.$ من السهل أن نرى أنه إذا كان $v$ في $Z$ ، فلا بد أن يكون $u$ كذلك، لأن كل حافة في $M$ متقاربة. الآن، لنفترض، على سبيل التناقض، أن $u\in Z$ لكن $v\notin Z$ لا يمكن أن يكون $u$ نفسه في $R_{S}$ لأنها نقطة نهاية لحافة متطابقة، لذلك يجب أن يكون هناك مسار موجه من الحواف الضيقة من رأس في $R_{S}$ إلى $u$ . يجب أن يتجنب هذا المسار $v$ ، لأنه، بحسب الفرضية، ليس في $Z$ ، لذا فإن الرأس الذي يسبق $u$ مباشرةً في هذا المسار هو رأس آخر. $v'\in T$ . $v'u$ يمثل ضلعًا ضيقًا من $T$ إلى $S$ ، وبالتالي فهو ينتمي إلى $M.$ ولكن $M$ يحتوي على ضلعين يشتركان في الرأس $u$ ، مما يناقض حقيقة أن $M$ عبارة عن تطابق. لذا، فإن كل ضلع في $M$ إما أن يكون طرفاه في Z أو لا يكون أي من طرفيه في $Z.$

إثبات أن $y$ لا يزال احتمالًا

لإثبات أن $y$ يظل جهدًا كامنًا بعد تعديله، يكفي إثبات أنه لا يوجد ضلع تزيد طاقته الكامنة الكلية عن تكلفتها. وقد تم إثبات ذلك بالفعل بالنسبة للأضلاع في $M$ في الفقرة السابقة، لذا لنفترض ضلعًا عشوائيًا $uv$ من $S$ إلى $T.$ إذا $y(u)$ إذا زادت بمقدار $Δ$ ، فإما $v\in Z\cap T$ وفي هذه الحالة $y(v)$ ينخفض بمقدار $Δ$ ، مما يترك الجهد الكلي للحافة دون تغيير، أو $v\in T\setminus Z$ وفي هذه الحالة، يضمن تعريف $Δ$ أن $y(u)+y(v)+\Delta \leq c(u,v)$ وبالتالي، يبقى $y$ احتمالاً.

الخوارزمية تعمل في زمن O ( n ^{3 )}

لنفترض أن هناك $J$ الوظائف و $W$ العمال ( $J\leq W$ نشرح كيفية حساب الحد الأدنى للتكلفة الإجمالية لكل بادئة من الوظائف لتخصيص كل وظيفة من هذه الوظائف لعمال مختلفين. على وجه التحديد، نضيف $j$ إنجاز المهمة وتحديث التكلفة الإجمالية في الوقت المناسب $O(jW)$ مما ينتج عنه تعقيد زمني إجمالي قدره $O\left(\sum _{j=1}^{J}jW\right)=O(J^{2}W)$ لاحظ أن هذا أفضل من $O(W^{3})$ عندما يكون عدد الوظائف صغيراً مقارنة بعدد العمال.

إضافة المهمة رقم j في زمن قدره O ( jW )

نستخدم نفس الرموز المستخدمة في القسم السابق، مع تعديل تعريفاتها حسب الضرورة. ليكن $S_{j}$ يرمز إلى مجموعة الأول $j$ الوظائف و $T$ تشير إلى مجموعة جميع العمال.

قبل $j$ في الخطوة رقم n من الخوارزمية، نفترض أن لدينا تطابقًا على $S_{j-1}\cup T$ هذا يطابق جميع الوظائف في $S_{j-1}$ والإمكانيات $y$ يتحقق الشرط التالي: أن يكون التطابق دقيقًا فيما يتعلق بالإمكانيات، وأن تكون إمكانيات جميع العمال غير المتطابقين صفرًا، وإمكانيات جميع العمال المتطابقين غير موجبة. تجدر الإشارة إلى أن هذه الإمكانيات تؤكد أمثلية التطابق.

خلال $j$ في الخطوة 1، نضيف $j$ الوظيفة إلى $S_{j-1}$ لتشكيل $S_{j}$ وقم بالتهيئة $Z=\{j\}$ في جميع الأوقات، كل رأس في $Z$ يمكن الوصول إليه من $j$ الوظيفة رقم 1 في $G_{y}$ . بينما $Z$ لا يحتوي على عامل لم يتم تعيين وظيفة له، دع

{\displaystyle \Delta

و $w_{\text{next}}$ يشير إلى أي $w$ حيث يتم الوصول إلى الحد الأدنى. بعد تعديل الإمكانات بالطريقة الموضحة في القسم السابق، توجد الآن حافة ضيقة من $Z$ ل $w_{\text{next}}$ .

لو $w_{\text{next}}$ إذا لم يكن هناك تطابق، فسنحصل على مسار مُعزِّز في الرسم البياني الفرعي للحواف الضيقة من $j$ ل $w_{\text{next}}$ بعد تفعيل خاصية المطابقة على طول هذا المسار، نكون قد طابقنا الآن العنصر الأول $j$ الوظائف، وينتهي هذا الإجراء.
وإلا، نضيف $w_{\text{next}}$ وتمت مطابقة الوظيفة معها $Z$ .

يتطلب تعديل الإمكانيات $O(W)$ الوقت. إعادة الحساب $\Delta$ و $w_{\text{next}}$ بعد تغيير الإمكانيات و $Z$ ويمكن القيام بذلك أيضًا في $O(W)$ الوقت. يمكن أن تحدث الحالة 1 على الأكثر $j-1$ عدد المرات قبل حدوث الحالة الثانية وانتهاء الإجراء، مما ينتج عنه التعقيد الزمني الإجمالي لـ $O(jW)$ .

التنفيذ بلغة C++

لتسهيل التنفيذ، يضيف الكود أدناه عاملًا إضافيًا $w_{W}$ بحيث $y(w_{W})$ يخزن نفي مجموع كل $\Delta$ تم حسابها حتى الآن. بعد $j$ عند إضافة الوظيفة رقم 1 وتحديث المطابقة، فإن تكلفة المطابقة الحالية تساوي مجموع جميع التكاليف. $\Delta$ المحسوبة حتى الآن، أو $-y(w_{W})$ .

تم اقتباس هذا الكود من e-maxx :: algo. ^{[ 7 ]}

/** * حل المسألة https://open.kattis.com/problems/cordonbleu باستخدام الخوارزمية الهنغارية. */ import std ;باستخدام std :: integral ؛ باستخدام std :: istream ؛ باستخدام std :: numeric_limits ؛ باستخدام std :: pair ؛ باستخدام std :: stringstream ؛ باستخدام std :: string_view ؛ باستخدام std :: vector ؛constexpr string_view SAMPLE_INPUT = R " ( 2 2 1 0 0 -1 -1 1 2 -1 0 0 ) " ;/** * @brief تُنفّذ خوارزمية المجر. * * بمعلومية J وظيفة و W عامل (J <= W)، تحسب هذه الدالة الحد الأدنى لتكلفة تخصيص كل * بادئة من الوظائف لعمال مختلفين. * * @tparam T نوع بيانات كبير بما يكفي لتمثيل الأعداد الصحيحة من رتبة J * * max(|C|) * @param C مصفوفة بأبعاد JxW بحيث C[j][w] = تكلفة تخصيص الوظيفة رقم j * للعامل رقم w (قد تكون سالبة) * * @return متجه بطول J، حيث يساوي العنصر رقم j الحد الأدنى لتكلفة تخصيص أول j + 1 وظيفة لعمال مختلفين */ template < integral T > vector < T > hungarian ( const vector < vector < T >>& C ) { auto lessThan = [] < integral T > ( T & a , const T & b ) -> bool { return b < a ? a = b , true : false ; const int J = static_cast <int> ( C.size ( )); const int W = static_cast <int> ( C [ 0 ] .size ( ) ) ; contract_assert ( J <= W ); // job [ w ] = المهمة المُسندة للعامل رقم w، أو -1 إذا لم تُسند أي مهمة // ملاحظة: تمت إضافة عامل رقم W للتسهيل vector <int> job ( W + 1 , -1 ); vector <T> ys ( J ); vector <T> yt ( W + 1 ) ; // الإمكانيات // -yt [ W ] يساوي مجموع جميع التغييرات vector <T> answers ; const T inf = numeric_limits <T> ::max (); for ( int jCur = 0 ; jCur < J ; ++ jCur ) { // تعيين المهمة رقم jCur int wCur = W ; job [ wCur ] = jCur ; // تقليل التكلفة المخفضة على الحواف من Z إلى العامل w vector <T> minTo ( W + 1 , inf ) ; vector <int> prev ( W + 1 , -1 ) ; // العامل السابق على المسار البديل vector <bool> inZ ( W + 1 ) ; // ما إذا كان العامل في Z while ( job [ wCur ] != -1 ) { // يتم تشغيلها على الأكثر jCur + 1 مرة inZ [ wCur ] = true ; const int j = job [ wCur ] ; T delta = inf ; int wNext ; for ( int w = 0 ; w < W ; ++ w ) { if ( ! inZ [ w ]) { if ( ckmin ( minTo [ w ], C [ j ][ w ] - ys [ j ] - yt [ w ])) { prev [ w ] = wCur ; } if ( ckmin ( delta , minTo [ w ])) { wNext = w ; } } } // ستكون قيمة delta دائمًا غير سالبة، // باستثناء ربما خلال المرة الأولى التي يتم فيها تشغيل هذه الحلقة // إذا كانت أي من مدخلات C[jCur] سالبة for ( int w)= 0 ; w <= W ; ++ w ) { if ( inZ [ w ]) { ys [ job [ w ]] += delta ; yt [ w ] -= delta ; } else { minTo [ w ] -= delta ; } } wCur = wNext ; } // تحديث التعيينات على طول المسار المتناوب for ( int w ; wCur != W ; wCur = w ) { job [ wCur ] = job [ w = prev [ wCur ]]; } answers . push_back ( - yt [ W ]); } return answers ; }/** * @brief يحل المسألة https://open.kattis.com/problems/cordonbleu */ int cordonBleu ( istream & is ) { int N ; int M ; is >> N >> M ; vector < pair < int , int >> B ( N ); vector < pair < int , int >> C ( M ); vector < pair < int , int >> bottles ( N ); vector < pair < int , int >> couriers ( M ); for ( auto & [ a , b ] : bottles ) { is >> a >> b ; } for ( auto & [ c , d ] : couriers ) { is >> a >> d ; } pair < int , int > rest ; std :: cin >> rest . first >> rest . second ; vector < vector < int >> costs ( N , vector < int > ( N + M - 1 )); auto dist = [ & ]( const pair < int , int >& x , const pair < int , int >& y ) -> int { return std :: abs ( x . first - y .أول ) +std :: abs ( x.second - y.second ); } ; for ( int b = 0 ; b < N ; ++ b ) { for ( int c = 0 ; c < M ; ++ c ) { // courier -> bottle -> restaurant costs [ b ][ c ] = dist ( couriers [ c ] , bottles [ b ]) + dist ( bottles [ b ], rest ); } for ( int c = 0 ; c < N - 1 ; ++ c ) { // restaurant - > bottle -> restaurant costs [ b ][ c + M ] = 2 * dist ( bottles [ b ], rest ); } } return hungarian ( costs ) .back (); }/** * @brief نقطة الدخول إلى البرنامج. * * @return رمز الإرجاع للبرنامج. */ int main () { stringstream sampleInput1 ( SAMPLE_INPUT );std :: println ( stderr , "{}" , cordonBleu ( sampleInput1 )); // 5 std :: println ( "{}" , cordonBleu ( std :: cin )); } // https://godbolt.org/z/Wen35833G

الاتصال بأقصر المسارات المتتالية

يمكن اعتبار الخوارزمية الهنغارية مكافئة لخوارزمية أقصر مسار متتالي لتدفق التكلفة الأدنى، ^{[ 8 ]}^{[ 9 ]} حيث تُستخدم تقنية إعادة الترجيح من خوارزمية جونسون لإيجاد أقصر المسارات. تمت إعادة كتابة التنفيذ من القسم السابق أدناه بطريقة تُبرز هذا الارتباط؛ ويمكن التحقق من أن الإمكانيات $h$ للعمال $0\dots W-1$ تساوي الكمونات $y$ من الحل السابق وصولاً إلى إزاحة ثابتة. عندما يكون الرسم البياني متفرقًا (لا يوجد سوى $M$ (الوظيفة المسموح بها، أزواج العمال)، من الممكن تحسين هذه الخوارزمية لتشغيلها في $O(JM+J^{2}\log W)$ الوقت باستخدام كومة فيبوناتشي لتحديد $w_{\text{next}}$ بدلاً من التكرار على الكل $W$ العمال للعثور على الشخص ذي المسافة الأقل (المشار إليه هنا ).

template < typename T > vector < T > hungarian ( const vector < vector < vector < T >>& C ) { auto lessThan = [] < integral T > ( T & a , const T & b ) -> bool { return b < a ? a = b , true : false ; } const int J = static_cast < int > ( C . size ()); const int W = static_cast < int > ( C [ 0 ]. size ()); contract_assert ( J <= W ); // job[w] = job assigned to w-th worker, or -1 if no job assigned // note: a W-th worker was added for ease vector < int > job ( W + 1 , -1 ); vector < T > h ( W ); // Johnson potentials vector < T > answers ; T ansCur = 0 ; const T inf = numeric_limits < T >:: max (); // تعيين المهمة رقم jCur باستخدام خوارزمية ديكسترا مع الإمكانات for ( int jCur = 0 ; jCur < J ; ++ jCur ) { int wCur = W ; // عامل غير مُزار ذو أقصر مسافة job [ wCur ] = jCur ; vector < T > dist ( W + 1 , inf ); // مسافات جونسون المختزلة dist [ W] = 0 ; vector < bool > vis ( W + 1 ); // ما إذا تمت زيارته بعد vector < int > prev ( W + 1 , -1 ); // العامل السابق على أقصر مسار while ( job [ wCur ] != -1 ) { // خطوة ديكسترا: إزالة أصغر عامل من الكومة T minDist = inf ; vis [ wCur ] = true ; int wNext = -1 ; // العامل التالي غير المُزار ذو أقصر مسافة // ضع في اعتبارك تمديد أقصر مسار بمقدار wCur -> job[wCur] -> w for ( int w = 0 ; w < W ; ++ w ) { if ( ! vis [ w ]) { // مجموع أوزان الحواف المُخفّضة wCur -> job[wCur] -> w T edge = C [ job [ wCur ]][ w ] - h [ w ]; إذا كان ( wCur != W ) { edge -= C [ job [ wCur ]][ wCur ] - h [ wCur ]; contract_assert ( edge >= 0 ); // نتيجة لجهود جونسون } إذا كان ( lessThan ( dist [ w ], dist [ wCur ] + edge )) { prev [ w ] = wCur ; } إذا كان ( lessThan ( minDist , dist [ w ])) { wNext = w ; } } } wCur = wNext ; } for ( int w =0 ; w < W ; ++ w ) { // تحديث الإمكانيات أقل من ( dist [ w ], dist [ wCur ]); h [ w ] += dist [ w ]; } ansCur += h [ wCur ]; for ( int w ; wCur != W ; wCur = w ) { job [ wCur ] = job [ w = prev [ wCur ]]; } answers . push_back ( ansCur ); } return answers ; }

تفسير المصفوفة

يتبع هذا النوع من الخوارزمية الصيغة التي قدمها فلوود، ^{[ 10 ]} والتي وصفها مونكرز لاحقًا بشكل أكثر وضوحًا، والذي أثبت أنها تعمل في ${\mathcal {O}}(n^{4})$ الوقت. ^{[ 4 ]} بدلاً من تتبع إمكانيات الرؤوس، تعمل الخوارزمية فقط على مصفوفة:

a_{ij}:=c(i,j)-y(i)-y(j)

أين $c(i,j)$ هي مصفوفة التكلفة الأصلية و $y(i),y(j)$ تمثل هذه القيم الجهد الناتج عن تحليل الرسم البياني. ويؤدي تغيير هذه القيم إلى إضافة أو طرح قيم من صفوف أو أعمدة هذه المصفوفة. تبدأ الخوارزمية بـ $a_{ij}=c(i,j)$ وعلى هذا النحو، يمكن اعتبار ذلك بمثابة أخذ مصفوفة التكلفة الأصلية وتعديلها.

بفرض وجود $n$ من العمال والمهام، تُكتب المسألة على شكل مصفوفة تكلفة $n$ × $n$

أ ₁	2	3	4
ب ₁	ب ₂	ب ₃	ب ₄
ج ₁	ج ₂	ج ₃	ج ₄
د ₁	د ₂	د ₃	د ₄

حيث أن a و b و c و d هم عمال يتعين عليهم أداء المهام 1 و 2 و 3 و 4. تشير a ₁ و a ₂ و a ₃ و a ₄ إلى العقوبات المتكبدة عندما يقوم العامل "a" بالمهام 1 و 2 و 3 و 4 على التوالي.

تُعادل هذه المسألة تكليف كل عامل بمهمة فريدة بحيث يتم تقليل إجمالي العقوبة إلى أدنى حد. لاحظ أنه لا يمكن إنجاز كل مهمة إلا بواسطة عامل واحد.

الخطوة 1

لكل صف، يُطرح أصغر عنصر فيه من جميع عناصر ذلك الصف. هذا يجعل جميع العناصر ذات قيم غير سالبة. لذلك، فإن عملية إسناد بقيمة إجمالية للعقوبة تساوي صفرًا هي، بحكم التعريف، عملية إسناد دنيا.

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

0	2	3	4
ب ₁	ب ₂	ب ₃	0
ج ₁	0	ج ₃	ج ₄
د ₁	د ₂	0	د ₄

الأصفار المذكورة أعلاه تمثل المهام الموكلة.

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

الخطوة الثانية

في بعض الأحيان قد يتبين أنه لا يمكن استخدام المصفوفة في هذه المرحلة للتخصيص، كما هو الحال بالنسبة للمصفوفة أدناه.

0	2	0	4
ب ₁	0	ب ₃	0
0	ج ₂	ج ₃	ج ₄
0	د ₂	د ₃	د ₄

للتغلب على هذا، نكرر الإجراء المذكور أعلاه لجميع الأعمدة (أي يتم طرح العنصر الأدنى في كل عمود من جميع العناصر في ذلك العمود ) ثم نتحقق مما إذا كان من الممكن إجراء تعيين بعقوبة 0.

في معظم الحالات سيؤدي هذا إلى النتيجة المرجوة، ولكن إذا لم يكن ذلك ممكناً بعد، فعلينا الاستمرار.

الخطوة 3

يجب تغطية جميع الأصفار في المصفوفة بتحديد أقل عدد ممكن من الصفوف و/أو الأعمدة. تشكل الخطوتان 3 و4 إحدى طرق تحقيق ذلك.

حاول تعيين قيمة صفرية عشوائية لكل صف. تُمثل المهام المُسندة بوضع نجمة بجانب الصفر. لاحظ أنه لا يمكن أن تكون المهام المُسندة في نفس الصف أو العمود.

نُعيّن الصفر الأول للصف الأول. لا يمكن تعيين الصفر الثاني للصف الأول.
نُعيّن الصفر الأول للصف الثاني. لا يمكن تعيين الصفر الثاني للصف الثاني.
لا يمكن تعيين أصفار في الصف 3 والصف 4، لأنها تقع في نفس العمود الذي تم تعيين الصفر فيه في الصف 1.

يمكننا أن ننتهي بمهمة أخرى إذا اخترنا ترتيبًا مختلفًا للصفوف والأعمدة.

0*	2	0	4
ب ₁	0*	ب ₃	0
0	ج ₂	ج ₃	ج ₄
0	د ₂	د ₃	د ₄

الخطوة الرابعة

قم بتغطية جميع الأعمدة التي تحتوي على الصفر (المميز بنجمة).

×	×
0*	2	0	4
ب ₁	0*	ب ₃	0
0	ج ₂	ج ₃	ج ₄
0	د ₂	د ₃	د ₄

ابحث عن صفر غير مغطى وقم بتمييزه بعلامة الفتحة (ضع علامة الفتحة ). إذا لم يتم العثور على صفر من هذا النوع، مما يعني أن جميع الأصفار مغطاة، فانتقل إلى الخطوة 5.

إذا كان الصفر في نفس الصف الذي يوجد فيه صفر مميز بنجمة، فقم بتغطية الصف المقابل، واكشف عمود الصفر المميز بنجمة.
ثم، انتقل إلى "ابحث عن صفر غير مغطى وقم بتهيئته".
- هنا، تم كشف الصفر الثاني في الصف الأول. ولأن هناك صفرًا آخر مميزًا بنجمة في الصف الأول، فإننا نغطي الصف الأول ونكشف العمود الأول.
- ثم، يتم كشف الصفر الثاني في الصف الثاني. نقوم بتغطية الصف الثاني وكشف العمود الثاني.

	×
0*	2	0'	4	×
ب ₁	0*	ب ₃	0
0	ج ₂	ج ₃	ج ₄
0	د ₂	د ₃	د ₄


0*	2	0'	4	×
ب ₁	0*	ب ₃	0'	×
0	ج ₂	ج ₃	ج ₄
0	د ₂	د ₃	د ₄

وإلا، فإن الصفر غير المغطى لا يحتوي على صفر مُعيّن في صفه. نقوم بإنشاء مسار يبدأ من الصفر باتباع الخطوات التالية:
1. الخطوة الفرعية 1: ابحث عن صفر مميز بنجمة في العمود المقابل. إذا وجدته، فانتقل إلى الخطوة الفرعية 2، وإلا فتوقف.
2. الخطوة الفرعية 2: ابحث عن صفر مُعَلَّم بعلامة (') في الصف المقابل (يجب أن يكون هناك صفر دائمًا). انتقل إلى الخطوة الفرعية 1.

تم كشف الصفر في الصف الثالث. نضيف إلى المسار الصفر الأول من الصف الأول، ثم الصفر الثاني من الصف الأول، وبذلك نكون قد انتهينا.


0*	2	0'	4	×
ب ₁	0*	ب ₃	0'	×
0'	ج ₂	ج ₃	ج ₄
0	د ₂	د ₃	د ₄

(استمر فرع else) لجميع الأصفار التي تمت مواجهتها أثناء المسار، الأصفار المميزة بعلامة النجمة والأصفار غير المميزة بعلامة النجمة.
- بما أن المسار يبدأ وينتهي بصفر مميز عند تبديل الأصفار المميزة بنجمة، فقد قمنا بتعيين صفر إضافي.

0	2	0*	4
ب ₁	0*	ب ₃	0
0*	ج ₂	ج ₃	ج ₄
0	د ₂	د ₃	د ₄

(وإلا استمر الفرع) قم بإزالة علامة التمييز من جميع الأصفار واكشف جميع الأسطر.
كرر الخطوات السابقة (استمر في التكرار حتى يتم الوصول إلى "الانتقال إلى الخطوة 5" المذكورة أعلاه).
- نغطي الأعمدة 1 و2 و3. الصفر الثاني في الصف 2 غير مغطى، لذلك نغطي الصف 2 ونكشف العمود 2:

×		×
0	2	0*	4
ب ₁	0*	ب ₃	0'	×
0*	ج ₂	ج ₃	ج ₄
0	د ₂	د ₃	د ₄

تم الآن تغطية جميع الأصفار بأقل عدد ممكن من الصفوف والأعمدة.

الوصف التفصيلي المذكور أعلاه هو مجرد طريقة واحدة لرسم أقل عدد ممكن من الخطوط لتغطية جميع الأصفار. هناك طرق أخرى فعالة أيضاً.

الخطوة 5

إذا كان عدد الأصفار المميزة بنجمة هو $n$ (أو في الحالة العامة $min(n,m)$ (حيث $n$ هو عدد الأشخاص و $m$ هو عدد الوظائف)، ينتهي عمل الخوارزمية. راجع قسم النتائج أدناه لمعرفة كيفية تفسير النتائج.

وإلا، فابحث عن أقل قيمة غير مغطاة. اطرح هذه القيمة من كل عنصر غير مغطى، ثم أضفها إلى كل عنصر مغطى بخطين. ارجع إلى الخطوة 4.

هذا يُعادل طرح رقم من جميع الصفوف غير المغطاة وإضافة نفس الرقم إلى جميع الأعمدة المغطاة. هذه العمليات لا تُغير التعيينات المثلى.

نتيجة

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

استنادًا إلى نظرية كونيغ ^{[ 11 ]،} فإن الحد الأدنى لعدد الخطوط (الحد الأدنى لتغطية الرؤوس ^{[ 12 ]} ) هو $n$ (حجم المطابقة القصوى ^{[ 13 ]} ). وبالتالي، عندما يكون المطلوب $n$ خطًا، يمكن إيجاد التخصيص ذي التكلفة الدنيا بالنظر إلى الأصفار فقط في المصفوفة.

فهرس

RE Burkard، M. Dell'Amico، S. Martello: مشاكل التخصيص (طبعة منقحة). سيام، فيلادلفيا (بنسلفانيا) 2012. ISBN 978-1-61197-222-1
م. فيشيتي، "Lezioni di Ricerca Operativa"، Edizioni Libreria Progetto Padova، إيطاليا، 1995.
R. Ahuja , T. Magnanti , J. Orlin , "تدفقات الشبكة"، برنتيس هول، 1993.
س. مارتيلو، "جينو إيغرفاري: من أصول الخوارزمية المجرية إلى الاتصالات عبر الأقمار الصناعية". المجلة الأوروبية المركزية لبحوث العمليات 18، 47-58، 2010

مراجع

↑ هارولد دبليو كون، "الطريقة الهنغارية لمشكلة التخصيص"، مجلة البحوث اللوجستية البحرية الفصلية ، 2 : 83-97، 1955. منشور كون الأصلي.
↑ هارولد دبليو كون، "متغيرات الطريقة الهنغارية لمشاكل التخصيص"، مجلة البحوث اللوجستية البحرية الفصلية ، 3 : 253-258، 1956.
↑ "عرض تقديمي" . مؤرشف من الأصل في 16 أكتوبر 2015.
1 2 ج. مونكرز، "خوارزميات لمشاكل التخصيص والنقل"، مجلة جمعية الرياضيات الصناعية والتطبيقية ، 5 (1):32-38، مارس 1957.
↑ إدموندز، جاك؛ كارب، ريتشارد م. (1 أبريل 1972). "تحسينات نظرية في كفاءة الخوارزميات لمشاكل تدفق الشبكة" . مجلة ACM . 19 (2): 248-264 . doi : 10.1145/321694.321699 . S2CID 6375478 .
↑ توميزاوا، ن. (1971). "حول بعض التقنيات المفيدة لحل مشاكل شبكات النقل". الشبكات . 1 (2): 173-194 . doi : 10.1002/net.3230010206 . ISSN 1097-0037 .
↑ "خوارزمية مجرية لحل مشكلة التخصيص" . e-maxx :: algo . 23 أغسطس 2012. تم الاطلاع عليه بتاريخ 13 مايو 2023 .
↑ جاكوب كوجلر (20 ديسمبر 2022). "خوارزمية التدفق الأدنى تكلفة - خوارزمية أقصر مسار متتالي" . خوارزميات البرمجة التنافسية . تم الاطلاع عليه بتاريخ 14 مايو 2023 .
↑ "حل مشكلة التخصيص باستخدام تدفق التكلفة الأدنى" . خوارزميات البرمجة التنافسية . 17 يوليو 2022. تم الاطلاع عليه في 14 مايو 2023 .
↑ فلود، ميريل م. (1956). "مسألة البائع المتجول". بحوث العمليات . 4 (1): 61-75 . doi : 10.1287/opre.4.1.61 . ISSN 0030-364X .
↑ نظرية كونيغ (نظرية الرسم البياني) نظرية كونيغ
↑ الحد الأدنى لتغطية الرؤوس
↑ المطابقة (نظرية الرسم البياني) المطابقة

للمزيد من القراءة

كورمن، توماس؛ ليسرسون، تشارلز؛ ريفست، رونالد؛ شتاين، كليفورد. "25.3: الخوارزمية الهنغارية لمسألة التخصيص". مقدمة في الخوارزميات ( الطبعة الرابعة). الصفحات 723-739 . ISBN 978-0-262-04630-5.

روابط خارجية

بروف، ديريك، مشكلة التخصيص والطريقة الهنغارية (الصيغة المصفوفية).
موردخاي ج. جولين، المطابقة الثنائية والطريقة الهنغارية (شكلية الرسم البياني الثنائي)، ملاحظات الدورة، جامعة هونغ كونغ للعلوم والتكنولوجيا .
خوارزمية المطابقة القصوى المجرية (بصيغتيها الرسميتين)، في موقع Brilliant الإلكتروني.
خوارزمية تعيين مونكرز ، آر إيه بيلغريم. معدلة للمصفوفات المستطيلة ، ملاحظات الدورة، جامعة موراي ستيت .
مايك داوز ، مشكلة التخصيص الأمثل ، ملاحظات الدورة، جامعة ويسترن أونتاريو .
حول طريقة كون المجرية – تحية من المجر ، أندراس فرانك ، مجموعة أبحاث إيجيرفاري، بازماني بي سيتاني 1/C، H1117، بودابست، المجر.
محاضرة: أساسيات بحوث العمليات - مشكلة التخصيص - الخوارزمية الهنغارية ، الأستاذ جي. سرينيفاسان، قسم الدراسات الإدارية، معهد مدراس للتكنولوجيا.
امتداد: تحليل حساسية التعيين (مع تعقيد زمني O(n^4)) ، ليو، شل.
حل أي مسألة واجبات عبر الإنترنت ، ويقدم شرحًا خطوة بخطوة للخوارزمية الهنغارية.

التطبيقات

لاحظ أن ليس كل هذه الأمور تفي بالغرض $O(n^{3})$ التعقيد الزمني، حتى وإن ادعوا ذلك. قد تحتوي بعض العمليات على أخطاء، لذا يُنصح بتنفيذ العمليات الأبطأ. $O(n^{4})$ قد تحتوي الخوارزمية على عيوب أخرى، أو قد تتضمن أوجه قصور أخرى. في أسوأ الأحوال، قد يتم تعديل مثال برمجي منشور على ويكيبيديا لاحقًا ليحتوي على شيفرة استغلالية. لذا، يُعد التحقق والتقييم ضروريين عند استخدام أمثلة برمجية من مؤلفين مجهولين.

نسخ من كود آر إيه بيلغريم بلغة لوا وبايثون (يدعي $O(n^{3})$ التعقيد الزمني)
تطبيق جوليا
تطبيق C يدّعي $O(n^{3})$ التعقيد الزمني
تطبيق جافا يدّعي $O(n^{3})$ التعقيد الزمني
تطبيق بايثون
تطبيق روبي مع اختبارات الوحدة
تطبيق C# يدّعي $O(n^{3})$ التعقيد الزمني
تطبيق بلغة D مع اختبارات الوحدة (نسخة معدلة من إصدار جافا تدعي $O(n^{3})$ أُرشف بتاريخ 30 ديسمبر 2019 في أرشيف الإنترنت (Wayback Machine) .
تطبيق تفاعلي عبر الإنترنت
التنفيذ التسلسلي والمتوازي.
ماتلاب وسي ( مؤرشفة في 3 مايو 2008 على موقع Wayback Machine)
تنفيذ بيرل
تنفيذ بلغة C++
تطبيق بلغة C++ يدّعي $O(n^{3})$ تعقيد الوقت (مرخصة بنظام BSD مفتوح المصدر)
تطبيق MATLAB
تنفيذ بلغة C
تطبيق جافا سكريبت مع اختبارات الوحدة (نسخة معدلة من إصدار جافا) $O(n^{3})$ التعقيد الزمني)
تقترح حزمة Clue R تطبيقًا باسم solve_LSAP
تطبيق Node.js على GitHub
تنفيذ بلغة بايثون في حزمة scipy

[kuhn1955-1] هارولد دبليو كون، "الطريقة الهنغارية لمشكلة التخصيص"، مجلة البحوث اللوجستية البحرية الفصلية ، 2 : 83-97، 1955. منشور كون الأصلي.

[kuhn1956-2] هارولد دبليو كون، "متغيرات الطريقة الهنغارية لمشاكل التخصيص"، مجلة البحوث اللوجستية البحرية الفصلية ، 3 : 253-258، 1956.

[3] "عرض تقديمي" . مؤرشف من الأصل في 16 أكتوبر 2015.

[munkres-4] 1 2 ج. مونكرز، "خوارزميات لمشاكل التخصيص والنقل"، مجلة جمعية الرياضيات الصناعية والتطبيقية ، 5 (1):32-38، مارس 1957.

[5] إدموندز، جاك؛ كارب، ريتشارد م. (1 أبريل 1972). "تحسينات نظرية في كفاءة الخوارزميات لمشاكل تدفق الشبكة" . مجلة ACM . 19 (2): 248-264 . doi : 10.1145/321694.321699 . S2CID 6375478 .

[6] توميزاوا، ن. (1971). "حول بعض التقنيات المفيدة لحل مشاكل شبكات النقل". الشبكات . 1 (2): 173-194 . doi : 10.1002/net.3230010206 . ISSN 1097-0037 .

[7] "خوارزمية مجرية لحل مشكلة التخصيص" . e-maxx :: algo . 23 أغسطس 2012. تم الاطلاع عليه بتاريخ 13 مايو 2023 .

[8] جاكوب كوجلر (20 ديسمبر 2022). "خوارزمية التدفق الأدنى تكلفة - خوارزمية أقصر مسار متتالي" . خوارزميات البرمجة التنافسية . تم الاطلاع عليه بتاريخ 14 مايو 2023 .

[9] "حل مشكلة التخصيص باستخدام تدفق التكلفة الأدنى" . خوارزميات البرمجة التنافسية . 17 يوليو 2022. تم الاطلاع عليه في 14 مايو 2023 .

[flood-10] فلود، ميريل م. (1956). "مسألة البائع المتجول". بحوث العمليات . 4 (1): 61-75 . doi : 10.1287/opre.4.1.61 . ISSN 0030-364X .

[11] نظرية كونيغ (نظرية الرسم البياني) نظرية كونيغ

[12] الحد الأدنى لتغطية الرؤوس

[13] المطابقة (نظرية الرسم البياني) المطابقة

[

[

[

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]،

[ 12 ]

[ 13 ]