سال انتشار: ۱۳۸۶

محل انتشار: سیزدهمین کنفرانس سالانه انجمن کامپیوتر ایران

تعداد صفحات: ۷

نویسنده(ها):

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

چکیده:

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