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

سال انتشار: 1392
محل انتشار: کنگره ملی مهندسی برق، کامپیوتر و فناوری اطلاعات
کد COI اختصاصی: CECIT01_677
زبان مقاله: فارسی
تعداد مشاهده: 1458

دانلود فایل این مقاله

نویسندگان

محدثه گریوانی

دانشجوی کارشناسی ارشد مهندسی کامپیوتر -نرم افزار،دانشگاه آزاد اسلامی واحد مشهد،مشهد

مجید وفایی جهان

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

سیدجواد سیدمهدوی چابک

استادیارگروه کامپیوتر -سخت افزار،دانشگاه آزاد اسلامی واحد مشهد،مشهد

چکیده

مسئله یافتن بزرگ ترین کلیک، از جمله مسائلNP-Completeاست که به یافتن بزرگ ترین زیرگراف کامل در یک گراف بدون جهت اشاره دارد. در این مقاله روشی مبتنی بر الگوریتم فرا اکتشافی بهینه سازی اکسترمال پیشنهاد شده است که رئوس کم ارزش را با احتمالبیشتری از بزرگ ترین کلیک فعلی حذف می کند، در نتیجه رئوس با ارزش بیشتر، احتمال حضور بیشتری نیز خواهند داشت. با هر جابجاییجزئی، تغییرات زیادی در کلیک ایجاد می شود و مرحله به مرحله به سمت یافتن بزرگ ترین کلیک پیش می رود. نتایج حاصل از اجرای روش پیشنهادی روی گراف هایDIMACS پاسخ های مطلوبی را از نظر اندازه کلیک های یافت شده و سرعت همگرایی در مقایسه با سایر روش ها نشان می دهد. در نهایت، روش پیشنهادی و پاسخ ها، با استفاده از نمودارهای همگرایی و آزمون آماریtصحت سنجی شده اند.

کلیدواژه ها

بزرگ ترین کلیک، بهینه سازی اکسترمال، کلیک، گراف

مقالات مرتبط جدید

اطلاعات بیشتر در مورد COI

COI مخفف عبارت CIVILICA Object Identifier به معنی شناسه سیویلیکا برای اسناد است. COI کدی است که مطابق محل انتشار، به مقالات کنفرانسها و ژورنالهای داخل کشور به هنگام نمایه سازی بر روی پایگاه استنادی سیویلیکا اختصاص می یابد.

کد COI به مفهوم کد ملی اسناد نمایه شده در سیویلیکا است و کدی یکتا و ثابت است و به همین دلیل همواره قابلیت استناد و پیگیری دارد.