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

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

Keywords:

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