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

**بزرگترین زیردنباله مشترک** ، روشی است که برای پیدا کردن بزرگترین زیردنباله در مجموعه‌ای از دنباله‌ها (غالباً دو دنباله) به کار می‌رود و مسئله‌ای قدیمی در علم کامپیوتر است. تفاوت این مسئله با مسئله ی بزرگترین زیررشته ی مشترک در این است که برای یک زیردنباله از یک رشته، نیازی نیست که اعضای آن مجاور یک دیگر باشند و به‌طور متوالی آمده باشند. این مسئله اساس کار برنامه‌های مقایسه‌کننده فایل است که تفاوت دو فایل را نمایش می‌دهد. همین طور در بیوانفورماتیک برای مقایسه رشته‌های دی ان ای کاربرد دارد.

## با مسئله [[بزرگترین زیررشته مشترک]] اشتباه نشود

در علوم کامپیوتر، مسئله بلندترین زیررشته مشترک برای یافتن بلندترین رشته(یا رشته‌هایی) که زیر رشته (یا زیررشته‌هایی)از دویاچندین رشته هستند،می‌باشد.این مسئله نباید با مسئله بلندترین زیردنباله مشترک اشتباه گرفته شود.(برای توضیحی در مورد تفاوت میان یک زیررشته و یک زیردنباله به زیررشته درمقابل زیردنباله رجوع کنید).

## شرح مسئله
دو رشته زیر را در نظر بگیرید:


S_{1}=ACCGGTCGAGTGCGCGGAGCCGGCCGAA\,\!



S_{2}=GTCGTTCGGAATGCCGTTGCTCTGTAAA\,\!



هدف مقایسه این دو رشته و پیدا کردن شباهت بین آن‌ها است. بزرگترین زیردنباله مشترک این‌طور تعریف می‌شود که دنباله‌ای مانند S_{3} است
به‌طوری‌که حروف موجود در S_{3} با حفظ ترتیب در S_{1} و S_{2} موجود باشد. اما مطلقاً لزومی ندارد که متوالی باشد. از طرفی S_{3} باید بزرگترین دنباله ممکن با خواص بالا باشد.
به‌طور کلی اگر دو رشته X=\langle x_{1},x_{2},... ,x_{n}\rangle و Y=\langle y_{1},y_{2},... ,y_{n}\rangle را در نظر بگیریم، یک بلندترین زیر دنباله مشترک را می‌توان با استفاده از برنامه نویسی پویا پیدا کرد.

## راه حل برای دو دنباله
مسئله LCS دارای خصوصیت زیر ساختار بهینه (Optimal Substructure) است:

مسئله LCS را می‌توان به زیر مسئله‌های کوچک تر تقسیم نمود.

که این زیر مسئله‌ها جفت دنباله‌های پیشوندی دو دنباله ورودی هستند.
اگر داشته باشیم: X=\langle x_{1},x_{2},... ,x_{n}\rangle٫ آن گاه X_{i} به این صورت تعریف می‌شود:
X_{i}=\langle x_{1},x_{2},... ,x_{i}\rangle

فرض کنید X=\langle x_{1},x_{2},... ,x_{m}\rangle و Y=\langle y_{1},y_{2},... ,y_{n}\rangle دو رشته باشند و Z=\langle z_{1},z_{2},... ,z_{k}\rangle بلندترین زیردنباله مشترک یا LCS دو رشته Y و X باشند.
پیاده‌سازی الگوریتم با استفاده از روش برنامه‌نویسی پویا به این صورت است:

۱)اگر X_{m}=Y_{n}\,\! باشد٫ آن گاه Z_{k}=X_{m}=Y_{n} و Z_{k-1} یک LCS برای Y_{k-1} و X_{k-1} است.

۲)اگر X_{m}\ne\; Y_{n} باشد٫ آن گاه Z_{k}\ne\;X_{m} نتیجه می‌دهد که Z یک LCS برای Y و X_{m-1} است.

۳)اگر X_{m}\ne\; Y_{n} باشد٫ آن گاه Z_{k}\ne\;Y_{m} نتیجه می‌دهد که Z یک LCS برای Y_{n-1} و X است.

قضیه فوق نشان می‌دهد:
LCS دو رشته٫ در داخل خودش٫ حاوی یک LCS برای پیشوندهای آن دو رشته نیز می‌باشد.

### یک راه حل بازگشتی برای پیداکردن LCS
فرض کنید c[i,j]\,\! یک عنصر از آرایه C باشد که نشان دهنده طول LCS دو دنبالهX_{i} و Y_{i} است. بنابراین اگر i=0 یا j=0 باشد٫ یکی از دنباله‌ها دارای طول صفر است و در نتیجه LCS دو دنباله صفر خواهد شد.

c[i,j] =
 \begin{cases}
 0 & i=0\ or\ j=0 \\
  c[i-1,j-1]+1 & i,j>0\ and\ X_{i}= Y_{j} \\
 max(c[i-1,j],c[i,j-1]) & i,j>0\ and\ X_{i}\ne Y_{j}
 \end{cases}
 
بنابراین وقتی که X_{i}\ne\; Y_{j} باشد٫ زیر مسئله ما پیدا کردن LCS برای X_{i-1} و Y_{i-1} است. در غیر این صورت ما دو زیر مسئله داریم:

پیدا کردن LCS برای Y_{i} و X_{i-1} و

پیدا کردن LCS برای Y_{i-1} و X_{i}
center|frame|شکل ۱
االگوریتم را با استفاده از روش برنامه‌نویسی پویا پیاده‌سازی می‌کنیم.
الگوریتم دو رشته X=\langle x_{1},x_{2},... ,x_{m}\rangle و Y=\langle y_{1},y_{2},... ,y_{n}\rangle را به عنوان ورودی دریافت می‌کند(شکل ۲).
الگوریتم مقادیر c[i,j]\,\! که نشان دهدنده طول LCS است را داخل آرایه c[1..m,1..n]\,\! ذخیره می‌کند. عناصر آرایه به ترتیب row-major پر می‌شوند. یهنی ابتدا اولین سطر c به ترتیب از چپ به راست پر می‌شود، سپس سطر دوم و الی آخر.
علاوه بر این الگوریتم آرایه دیگری به نام b[1..m,1..n]\,\! را نیز پر می‌کند. این آرایه جهت حرکت را ذخیره می‌کند.
center|frame|شکل ۲
مقدار b با علامت‌های جهت \leftarrow,\uparrow,\nwarrow پر می‌شود.
همین طور مقدار c[i,j]\,\! به این بستگی دارد که آیا x_i=y_i باشد (خط ۹). جهت فلش‌ها طوری انتخاب می‌شود که همواره حرکت به سمت خانه‌ای با طول LCS بزرکتر را تضمین می‌کند. در نهایت برای پیدا کردن LCS از گوشه سمت راست و پایین آرایه b در جهت پیکان‌ها به سمت گوشه بالا و چپ آرایه حرکت می‌کنیم.

 **function** print_LCS (b,X,i,j)
   **if** i=0 or j=0 **then**
      **return**
   **if** b[i,j] = '\nwarrow' then
      print_LCS(b,X,i-1,j-1)
      print x_i
   **else if** b[i,j]= '\uparrow' **then**
      print_LCS(b,X,i-1,j)
   **else** print_LCS(b,X,i,j-1)

## پیچیدگی زمانی
زمانی که تعداد دنباله‌های ورودی ثابت باشند٫ این مسئله توسط برنامه‌نویسی پویا در زمان چندجمله‌ای حل می‌شود. فرض کنید N دنباله ورودی به طول n_1,n_2,... ,n_N داشته باشیم. یک راه حل ابتدایی برای جستجوی LCS این است که هر یک از2^{n_1} زیردنباله دنباله اولی را برررسی کنیم که آیا زیر دنباله برای دیگر دنباله‌های ورودی است یا خیر. هر زیر ددنباله در زمانی خطی متناسب با طول دنباله‌های باقی‌مانده بررسی می‌شود.
بنابراین زمان الگوریتم برابر خواهد بود با:O\left(2^{n_1} \sum_{i>1} n_i\right).
برای حالت ورودی با دو دنباله با n و m عنصر٫ پیچیدگی زمانی الگوریتم برابر O(mn)\,\! خواهد بود.
برای تعداد ورودی‌های دلخواه برنامه‌نویسی پویا راه حلی با این زمان ارائه می‌کند:O\left(N \prod_{i=1}^{N} n_i\right).

توابعی با پیچیدگی کمتر موجود است،

## پانویس‌ها

## منابع
* 
* دکتر جم زاد، منصور. *جزوه درسی ساختمان داده و الگوریتم ها*٫ نسخه ویرایش نشده. تهران: دانشگاه صنعتی شریف، ۱۳۸۵.
* 

رده:برنامه‌نویسی پویا
رده:ترکیبیات
رده:مسئله‌های با پیچیدگی زمانی چندجمله‌ای
رده:مسئله‌های ان‌پی کامل