حل مساله بزرگترین مجموعه مستقل توسط اتوماتای یادگیر سلولی

  • سال انتشار: 1383
  • محل انتشار: دهمین کنفرانس سالانه انجمن کامپیوتر ایران
  • کد COI اختصاصی: ACCSI10_089
  • زبان مقاله: فارسی
  • تعداد مشاهده: 1616
دانلود فایل این مقاله

نویسندگان

سیدعلیرضا متولیان

آزمایشگاه محاسبات نرم دانشگاه صنعتی امیرکبیر

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

چکیده

مساله بزرگترین مجموعه مستقل در یک گراف عبارتست از یافتن بزرگترین زیرمجموعه ای از یک گراف بطوریکه هیچ دو راسی از این مجموعه با یالی بهم متصل نباشند این مساله از جمله مسائل NP-complete می باشد و بهمین دلیل الگوریتمهای مکاشفه ای و تقریبی متعددی از جمله تابکاری فلزات، شبکه های عصبی و الگوریتمهای ژنتیکی تاکنون برای آن ارائه نشدها ند اتوماتای یادگیر سلولی یک ابزار جستجوی تصادفی است که می توان از آن درحل مسائل NP-complete استفاده نمود. دراین مقاله یک الگوریتم مبتنی بر اتوماتای یادگیر سلولی برای حل مساله بزرگترین مجموعه مستقل ارائه شده و کارایی آن برروی تعدادی گراف نمونه استاندارد آزمایش شده است.

کلیدواژه ها

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

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

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

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

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