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

از ویکی‌پدیا، دانشنامهٔ آزاد

الگوریتم مجارستانی (به انگلیسی: Hungarian algorithm) در دستهٔ الگوریتم‌های بهینه سازی ترکیباتی (Combinatorial Oprimization) قرار می‌گیرد که مسئله تخصیص وظایف را در زمان چند جمله‌ای حل می‌کند. این الگوریتم توسط هارولد کاهن (Harold W. Kuhn) ارائه شد و توسط او "مجارستانی" نام گرفت چرا که این الگوریتم عمدتاً بر اساس کارهای ریاضی‌دانان مجارستانی بنا شده بود. بعدها این الگوریتم توسط جیمز مانکرس بازبینی شد. بعد از آن زمان این الگوریتم به نام‌های مشابه کاهن-مانکرس (Kuhn-Munkres) یا الگوریتم توزیع وظابف مانکرس (به انگلیسی: Munkres assignment algorithm) نیز مشهور است. پیچیدگی زمانی الگوریتم اصلی در مرتبهٔ بود که بعدها به زمان کاهش یافت.

توضیح سادهٔ مسئله[ویرایش]

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

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

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

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

فرض کنید ماتریس 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) در ۱۹ ژوئیه ۲۰۱۱. دریافت‌شده در ۱۲ سپتامبر ۲۰۱۲.

پیوند به بیرون[ویرایش]