مسئله بزرگترین زیردنباله مشترک
بزرگترین زیردنباله مشترک ، روشی است که برای پیدا کردن بزرگترین زیردنباله در مجموعه‌ای از دنباله‌ها (غالباً دو دنباله) به کار می‌رود و مسئله‌ای قدیمی در علم کامپیوتر است. تفاوت این مسئله با مسئله ی بزرگترین زیررشته ی مشترک در این است که برای یک زیردنباله از یک رشته، نیازی نیست که اعضای آن مجاور یک دیگر باشند و به‌طور متوالی آمده باشند. این مسئله اساس کار برنامه‌های مقایسه‌کننده فایل است که تفاوت دو فایل را نمایش می‌دهد. همین طور در بیوانفورماتیک برای مقایسه رشته‌های دی ان ای کاربرد دارد.
در علوم کامپیوتر، مسئله بلندترین زیررشته مشترک برای یافتن بلندترین رشته(یا رشته‌هایی) که زیر رشته (یا زیررشته‌هایی)از دویاچندین رشته هستند،می‌باشد.این مسئله نباید با مسئله بلندترین زیردنباله مشترک اشتباه گرفته شود.(برای توضیحی در مورد تفاوت میان یک زیررشته و یک زیردنباله به زیررشته درمقابل زیردنباله رجوع کنید).
دو رشته زیر را در نظر بگیرید:
formula_1
formula_2
هدف مقایسه این دو رشته و پیدا کردن شباهت بین آن‌ها است. بزرگترین زیردنباله مشترک این‌طور تعریف می‌شود که دنباله‌ای مانند formula_3 است به‌طوری‌که حروف موجود در formula_3 با حفظ ترتیب در formula_5 و formula_6 موجود باشد. اما مطلقاً لزومی ندارد که متوالی باشد. از طرفی formula_3 باید بزرگترین دنباله ممکن با خواص بالا باشد. به‌طور کلی اگر دو رشته formula_8 و formula_9 را در نظر بگیریم، یک بلندترین زیر دنباله مشترک را می‌توان با استفاده از برنامه نویسی پویا پیدا کرد.
مسئله LCS دارای خصوصیت زیر ساختار بهینه (Optimal Substructure) است:
مسئله LCS را می‌توان به زیر مسئله‌های کوچک تر تقسیم نمود.
که این زیر مسئله‌ها جفت دنباله‌های پیشوندی دو دنباله ورودی هستند. اگر داشته باشیم: formula_8٫ آن گاه formula_11 به این صورت تعریف می‌شود: formula_12
فرض کنید formula_13 و formula_9 دو رشته باشند و formula_15 بلندترین زیردنباله مشترک یا LCS دو رشته Y و X باشند. پیاده‌سازی الگوریتم با استفاده از روش برنامه‌نویسی پویا به این صورت است:
۱)اگر formula_16 باشد٫ آن گاه formula_17 و formula_18 یک LCS برای formula_19 و formula_20 است.
۲)اگر formula_21 باشد٫ آن گاه formula_22 نتیجه می‌دهد که Z یک LCS برای formula_23 و formula_24 است.
۳)اگر formula_21 باشد٫ آن گاه formula_26 نتیجه می‌دهد که Z یک LCS برای formula_27 و formula_28 است.
قضیه فوق نشان می‌دهد: LCS دو رشته٫ در داخل خودش٫ حاوی یک LCS برای پیشوندهای آن دو رشته نیز می‌باشد.
فرض کنید formula_29 یک عنصر از آرایه C باشد که نشان دهنده طول LCS دو دنبالهformula_11 و formula_31 است. بنابراین اگر i=0 یا j=0 باشد٫ یکی از دنباله‌ها دارای طول صفر است و در نتیجه LCS دو دنباله صفر خواهد شد. formula_32 بنابراین وقتی که formula_33 باشد٫ زیر مسئله ما پیدا کردن LCS برای formula_34 و formula_35 است. در غیر این صورت ما دو زیر مسئله داریم:
پیدا کردن LCS برای formula_31 و formula_34 و
پیدا کردن LCS برای formula_35 و formula_11
االگوریتم را با استفاده از روش برنامه‌نویسی پویا پیاده‌سازی می‌کنیم. الگوریتم دو رشته formula_13 و formula_9 را به عنوان ورودی دریافت می‌کند(شکل ۲). الگوریتم مقادیر formula_29 که نشان دهدنده طول LCS است را داخل آرایه formula_43 ذخیره می‌کند. عناصر آرایه به ترتیب row-major پر می‌شوند. یهنی ابتدا اولین سطر c به ترتیب از چپ به راست پر می‌شود، سپس سطر دوم و الی آخر. علاوه بر این الگوریتم آرایه دیگری به نام formula_44 را نیز پر می‌کند. این آرایه جهت حرکت را ذخیره می‌کند.
مقدار b با علامت‌های جهت formula_45 پر می‌شود. همین طور مقدار formula_29 به این بستگی دارد که آیا formula_47 باشد (خط ۹). جهت فلش‌ها طوری انتخاب می‌شود که همواره حرکت به سمت خانه‌ای با طول LCS بزرکتر را تضمین می‌کند. در نهایت برای پیدا کردن LCS از گوشه سمت راست و پایین آرایه b در جهت پیکان‌ها به سمت گوشه بالا و چپ آرایه حرکت می‌کنیم.
زمانی که تعداد دنباله‌های ورودی ثابت باشند٫ این مسئله توسط برنامه‌نویسی پویا در زمان چندجمله‌ای حل می‌شود. فرض کنید N دنباله ورودی به طول formula_51 داشته باشیم. یک راه حل ابتدایی برای جستجوی LCS این است که هر یک ازformula_52 زیردنباله دنباله اولی را برررسی کنیم که آیا زیر دنباله برای دیگر دنباله‌های ورودی است یا خیر. هر زیر ددنباله در زمانی خطی متناسب با طول دنباله‌های باقی‌مانده بررسی می‌شود. بنابراین زمان الگوریتم برابر خواهد بود با:formula_53 برای حالت ورودی با دو دنباله با n و m عنصر٫ پیچیدگی زمانی الگوریتم برابر formula_54 خواهد بود. برای تعداد ورودی‌های دلخواه برنامه‌نویسی پویا راه حلی با این زمان ارائه می‌کند:formula_55
توابعی با پیچیدگی کمتر موجود است،