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

مهدی عنایت زارع; محمدرضا میبدی

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

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

سال انتشار: 1386

نوع سند: مقاله کنفرانسی

زبان: فارسی

مشاهده: 1,514

فایل این مقاله در 7 صفحه با فرمت PDF قابل دریافت می باشد

دریافت فایل کامل مقاله

صدور گواهی نمایه سازی
من نویسنده این مقاله هستم

استخراج به نرم افزارهای پژوهشی:

لینک ثابت به این مقاله:

https://civilica.com/doc/41679

شناسه ملی سند علمی:

ACCSI13_085

تاریخ نمایه سازی: 25 آبان 1386

چکیده مقاله:

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

کلیدواژه ها:

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

نویسندگان

مهدی عنایت زارع

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

محمدرضا میبدی

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

مراجع و منابع این مقاله:

لیست زیر مراجع و منابع استفاده شده در این مقاله را نمایش می دهد. این مراجع به صورت کاملا ماشینی و بر اساس هوش مصنوعی استخراج شده اند و لذا ممکن است دارای اشکالاتی باشند که به مرور زمان دقت استخراج این محتوا افزایش می یابد. مراجعی که مقالات مربوط به آنها در سیویلیکا نمایه شده و پیدا شده اند، به خود مقاله لینک شده اند :

F. Barahona, M. Grotschel, M. Junger and G. Reinelt, 4An ...
R. Karp, Reducibility among combinatorial problems , Complexity of computer ...
S. Sahni and T. Gonzalez, *P-Complete App roximation Problems?, Journal ...
T. Hofmeister and H. Lefmann, ،A Comb inatorial Design Approach ...
M. X. Goemans and D. P. Williamson, *'Improved App roximation ...
P. M. Vitanyi, *How Well Can a Graph _ n-Colored?, ...
S. Poljak and D. Turzik, ،A Polynomial Algorithm for Constructing ...
D. J. Haglin and S. M. Venkatesan, ،، Ap proximation ...
P. Festa, P. M. Pardalos, M. G. C. Resende and ...
O. Dolezal, T. Hofmeister and _ Lefmann., ،A Comparison of ...
A. Khurti, Th. Back and J. Heitkotter, ،0An Evolutionary Approach ...
S. Wolfram, "Cellular Automata", Los Alamos Science, Vol. 9, pp. ...
S. Wolfram, "Universality and complexity in cellular automata", Physica D, ...
K. S. Narendra and M.A.L. Thathacha, "Learning Automata: An Introduction" ...
of Varieties؛، [15] M. _ L. Thathachar and P. S. ...
M. R. Meybodi, H. Beigy and M. Taherkhani; "Cellular Learning ...
H. Beigy and M. R. Meybodi., ،A Mathematical Framework for ...
H. Beigy and M. R. Meybodi, "Open Synchronous Cellular Learning ...
H. Beigy and M. R. Meybodi, *Open Synchronous Cellular Learning ...
M. Asnaashari and M. R. Meybodi, "Irregular Cellular Learning Automata ...
H. Beigy and M. R. Meybodi *Asynchronou s Cellular Learning ...
H. Beigy and M. R. Meybodi, _ 'Asynchronous Cellular Learning ...
M. R. Meybodi and M. R. Kharazmi, "Cellular Learning Automata ...
M. R. Meybodi and F. Mehdipour, "Application of Cellular Learning ...
httn0//«imars _ _ _ _ _ th/Inctancec ...

نمایش کامل مراجع