حل مسأله بزرگترین برش در گراف با استفاده از اتوماتای یادگیر سلولی

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

Keywords:

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