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

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

Keywords:

کوتاهترین ابر رشته , الگوریتم ممتیک , Memetic =SSP =Superstring