الگوریتمی بهبود یافته برای حل مسئله MINIMAX به شکل n ضربدر n

امروزه بسیاری از مسائل در حوزه صنعت و خدمات در رویارویی با گلوگاهها در چارچوب مسائل با هدف حداقل کردن حداکثرها، فرموله می شوند. تاکنون الگوریتمهای هیورستیک متعددی برای تسهیل در حل این گونه مسائل ابداع شده است که از میان آنها می توان به الگوریتمهای گراس و ترشولند به عنوان معروفترین الگوریتمهای هیورستیک عمومی برای حل مسائل minimax به شکل n ضربدر n اشاره کرد. این مقاله به تبیین الگوریتم ابداعی و ارزیابی عملکرد آن در مقایسه با الگورتیم ترشولند می پردازد. نمودارهای مقایسه ای در حل مسائل تصادفی متعدد منتج از نرم افزار طراحی شده توسط نویسندگان، نشان می دهد که عموما جوابهای منتج از الگوریتم ابداعی نسبت به الگوریتم پیش گفته به مراتب بهتر بوده و هرچه ابعاد مسئله (n) بزرگتر باشد این اختلاف چشم گیر تر است.

Keywords:

تحقیق در عملیات , الگوریتم , حداقل حداکثر , تخصیص گلوگاهی