مسئله بزرگترین زیردنباله مشترک
بزرگترین زیردنباله مشترک (به انگلیسی: Longest Common Subsequence)، روشی است که برای پیدا کردن بزرگترین زیردنباله در مجموعهای از دنبالهها (غالباً دو دنباله) به کار میرود و مسئلهای قدیمی در علم کامپیوتر است. تفاوت این مسئله با مسئله ی بزرگترین زیررشته ی مشترک در این است که برای یک زیردنباله از یک رشته، نیازی نیست که اعضای آن مجاور یک دیگر باشند و بهطور متوالی آمده باشند. این مسئله اساس کار برنامههای مقایسهکننده فایل است که تفاوت دو فایل را نمایش میدهد. همین طور در بیوانفورماتیک برای مقایسه رشتههای دی ان ای کاربرد دارد.
با مسئله بزرگترین زیررشته مشترک اشتباه نشود
در علوم کامپیوتر، مسئله بلندترین زیررشته مشترک برای یافتن بلندترین رشته(یا رشتههایی) که زیر رشته (یا زیررشتههایی)از دویاچندین رشته هستند،میباشد.این مسئله نباید با مسئله بلندترین زیردنباله مشترک اشتباه گرفته شود.(برای توضیحی در مورد تفاوت میان یک زیررشته و یک زیردنباله به زیررشته درمقابل زیردنباله رجوع کنید).
شرح مسئله
دو رشته زیر را در نظر بگیرید:
هدف مقایسه این دو رشته و پیدا کردن شباهت بین آنها است. بزرگترین زیردنباله مشترک اینطور تعریف میشود که دنبالهای مانند
راه حل برای دو دنباله
مسئله LCS دارای خصوصیت زیر ساختار بهینه (Optimal Substructure) است:
مسئله LCS را میتوان به زیر مسئلههای کوچک تر تقسیم نمود.
که این زیر مسئلهها جفت دنبالههای پیشوندی دو دنباله ورودی هستند.
اگر داشته باشیم:
فرض کنید
۱)اگر
۲)اگر
۳)اگر
قضیه فوق نشان میدهد: LCS دو رشته٫ در داخل خودش٫ حاوی یک LCS برای پیشوندهای آن دو رشته نیز میباشد.
یک راه حل بازگشتی برای پیداکردن LCS
فرض کنید
پیدا کردن LCS برای
پیدا کردن LCS برای
االگوریتم را با استفاده از روش برنامهنویسی پویا پیادهسازی میکنیم.
الگوریتم دو رشته
مقدار b با علامتهای جهت
function print_LCS (b,X,i,j) if i=0 or j=0 then return if b[i,j] = '' then print_LCS(b,X,i-1,j-1) printelse if b[i,j]= '' then print_LCS(b,X,i-1,j) else print_LCS(b,X,i,j-1)
پیچیدگی زمانی
زمانی که تعداد دنبالههای ورودی ثابت باشند٫ این مسئله توسط برنامهنویسی پویا در زمان چندجملهای حل میشود. فرض کنید N دنباله ورودی به طول
توابعی با پیچیدگی کمتر موجود است،
پانویسها
- ↑ L. Bergroth and H. Hakonen and T. Raita (۲۰۰۰), "A Survey of Longest Common Subsequence Algorithms", SPIRE (به انگلیسی), IEEE Computer Society, vol. ۰۰, p. ۳۹–۴۸
منابع
- دکتر جم زاد، منصور. جزوه درسی ساختمان داده و الگوریتم ها٫ نسخه ویرایش نشده. تهران: دانشگاه صنعتی شریف، ۱۳۸۵.
- توماس اچ کورمن, Charles E. Leiserson, رونالد ریوست and کلیفورد استین (2001), "۱۵٫۴", مقدمهای بر الگوریتمها (به انگلیسی) (second ed.), MIT Press and McGraw-Hill, p. ۳۵۰–۳۵۵