الگوریتم مجارستانی

الگوریتم مجارستانی (به انگلیسی: Hungarian algorithm) در دستهٔ الگوریتم‌های بهینه سازی ترکیباتی (Combinatorial Optimization) قرار می‌گیرد که مسئله تخصیص وظایف را در زمان چند جمله‌ای حل می‌کند. این الگوریتم توسط هارولد کاهن (Harold W. Kuhn) ارائه شد و توسط او "مجارستانی" نام گرفت چرا که این الگوریتم عمدتاً بر اساس کارهای ریاضی‌دانان مجارستانی بنا شده بود. بعدها این الگوریتم توسط جیمز مانکرس بازبینی شد. بعد از آن زمان این الگوریتم به نام‌های مشابه کاهن-مانکرس (Kuhn-Munkres) یا الگوریتم توزیع وظابف مانکرس (به انگلیسی: Munkres assignment algorithm) نیز مشهور است. پیچیدگی زمانی الگوریتم اصلی در مرتبهٔ ${\displaystyle O(n^{4})}$ بود که بعدها به زمان ${\displaystyle O(n^{3})}$ کاهش یافت.

توضیح سادهٔ مسئله

فرض کنید که ۳ کارگر دارید:جیم، استیو و آلن. به یکی از آن‌ها برای تمیز کردن حمام، یکی برای جارو کشیدن زمین و دیگری برای شستن پنجره‌ها. بهترین (کم هزینه ترین) راه برای تخصیص کارها چیست؟ ابتدا به یک ماتریس هزینه انجام دادن هر کار به وسیلۀ هر کارگر نیاز داریم.

	شستن حمام	جارو کشیدن به کف زمین	شستن پنجره‌ها
جیم	۱ ریال	۳ ریال	۳ ریال
استیو	۳ ریال	۲ ریال	۳ ریال
آلن	۳ ریال	۳ ریال	۲ ریال

با اعمال الگوریتم مجارستانی به جواب بهینه برای مسئلهٔ فوق به صورت زیر خواهیم رسید: - جیم حمام را بشوید. - استیو کف زمین را جارو بکشد. - آلن پنجره را بشوید

توصیف ریاضی مسئله

فرض کنید ماتریس n×n داده شده‌است که در آن درایهٔ سطر i-ام و ستون j-ام، هزینهٔ انجام j-امین کار نوسط i-امین فرد است. ما اکنون باید طوری تقسیم وظایف بین افراد را پیدا کنیم که مجموع هزینه‌های افراد حداقل شود. حتی اگر هدف پیدا کردن حداکثر میزان هزینه باشد، می‌توان آن را با حداقل کردن اختلاف هزینه‌ها با مقداری حداکثر از هزینه‌ها به‌دست آورد.^[۱]

حل مسئله در صورتی که بصورتی یک گراف دوبخشی بیان شود راحت‌تر است. فرض کنیم گراف دوبخشی کامل به صورت G=(S, T; E) داریم که در آن n راس کارگر (S) و n راس شغل (T) داریم. هر یال دارای وزنی غیر منفی c(i,j) است که همان هزینهٔ انجام کار مورد نظر توسط فرد مربوطه است. هدف است که تطابق کامل با کمترین هزینه را بدست آوریم.

منابع

1. «Beryl Castello, The Hungarian Algorithm» (PDF). بایگانی‌شده از اصلی (PDF) در ۱۹ ژوئیه ۲۰۱۱. دریافت‌شده در ۱۲ سپتامبر ۲۰۱۲.

پیوند به بیرون

• Mordecai J. Golin, Bipartite Matching and the Hungarian Method, Course Notes, Hong Kong University of Science and Technology.
• R. A. Pilgrim, Munkres' Assignment Algorithm. Modified for Rectangular Matrices, Course notes, Murray State University.
• Mike Dawes, The Optimal Assignment Problem, Course notes, دانشگاه وسترن انتاریو.
• On Kuhn's Hungarian Method – A tribute from Hungary, András Frank, Egervary Research Group, Pazmany P. setany 1/C, H1117, Budapest, Hungary.
• Lecture: Fundamentals of Operations Research - Assignment Problem - Hungarian Algorithm در یوتیوب، Prof. G. Srinivasan, Department of Management Studies, IIT Madras.