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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

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

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

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

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

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

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

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

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

منابع[ویرایش]

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