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

محل انتشار: اولین کنفرانس ملی محاسبات نرم و فن آوری اطلاعات

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

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

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

چکیده:

مسئله کوتاهترین ابر رشته (SSP) یک مسئله NP-Hard است که کاربرد بسیاری در الگوریتمهای فشرده سازی داده ها ، رمزنگاری اطلاعات و همچنین محسابات پزشکی و بیولوژیکی دارد .این مسئله حتی با اعمال محدودیتهای مختلف به سایز الفبای ابر رشته ، باز هم یک مسئله NP-Hard خواهد بود.در این مقاله راه حلی بهینه برای مسئله کوتاهترین ابر رشته با استفاده از الگوریتم ممتیک ارائه می گردد.الگوریتم ممتیک گونه ای از الگوریتمهای تکاملی است که با استفاده از ترکیب الگوریتم ژنتیک با جستجوهای محلی و بهینه سازیهای مقطعی ، به پاسخ هایی با کیفیت بیشتری نسبت به دیگر الگوریتمهای تکاملی مانند الگوریتم ژنتیک دست پیدا می کند.