مهدی عنایت زارع - آزمایشگاه محاسبات نرم دانشکده مهندسی کامپیوتر و فناوری اطلاعات دانش
محمدرضا میبدی - آزمایشگاه محاسبات نرم دانشکده مهندسی کامپیوتر و فناوری اطلاعات دانش

مساله بزرگترین برش در گراف دارای کاربردهای فراوانی از جمله طراحی مدارهای مجتمع متراکم و فیزیک آماری می باشد. بزرگترین برش در گراف عبارت است از افراز مجموعه راس های گراف به دو زیرمجموعه غیر مشترک به گونه ای که تعداد (وزن) یالهایی که یک سرآنها در یک زیرمجموعه و سردیگرشان در زیرمجموعه دیگر قرار گرفته است. بیشینه شود. مساله بزرگترین برش یکی از مسایل NP-Complete می باشد و به همین دلیل الگوریتمهای تقریبی متعددی برای حل آن ارایه شده است در این مقاله یک الگوریتم مبتنی بر اتوماتای یادگیر سلولی جدید برای حل این مساله پیشنهاد میگردد الگوریتمهای پیشنهادی با الگوریتمهای تقریبی سهنی، ژئومنس، الگوریتمهای مبتنی بر اتوماتای سلولی یادگیر و الگوریتمهای ترکیبی و ژنتیک مقایسه شده است. طبق نتایج به دست آمده، الگوریتمهای پیشنهادی نتایج بهتری را در مقایسه با الگوریتمهای فوق الذکر تولید می کند.

مساله بزرگترین برش، الگوریتمهای تقریبی، اتوماتای یادگیر سلولی