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

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

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

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

شرح مسئله

دو رشته زیر را در نظر بگیرید:

$S_1=ACCGGTCGAGTGCGCGGAGCCGGCCGAA$

$S_2=GTCGTTCGGAATGCCGTTGCTCTGTAAA$

هدف مقایسه این دو رشته و پیدا کردن شباهت بین آن‌ها است. بزرگترین زیردنباله مشترک این‌طور تعریف می‌شود که دنباله‌ای مانند $S_3$ است به‌طوری‌که حروف موجود در $S_3$ با حفظ ترتیب در $S_1$ و $S_2$ موجود باشد. اما مطلقاً لزومی ندارد که متوالی باشد. از طرفی $S_3$ باید بزرگترین دنباله ممکن با خواص بالا باشد. به‌طور کلی اگر دو رشته $X=⟨x_1,x_2,...,x_n⟩$ و $Y=⟨y_1,y_2,...,y_n⟩$ را در نظر بگیریم، یک بلندترین زیر دنباله مشترک را می‌توان با استفاده از برنامه نویسی پویا پیدا کرد.

راه حل برای دو دنباله

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

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

که این زیر مسئله‌ها جفت دنباله‌های پیشوندی دو دنباله ورودی هستند. اگر داشته باشیم: $X=⟨x_1,x_2,...,x_n⟩$٫ آن گاه $X_i$ به این صورت تعریف می‌شود: $X_i=⟨x_1,x_2,...,x_i⟩$

فرض کنید $X=⟨x_1,x_2,...,x_m⟩$ و $Y=⟨y_1,y_2,...,y_n⟩$ دو رشته باشند و $Z=⟨z_1,z_2,...,z_k⟩$ بلندترین زیردنباله مشترک یا 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{array}{cc}0& i=0orj=0\\ c[i-1,j-1]+1& i,j>0and{X}_i=Y_j\\ max(c[i-1,j],c[i,j-1])& i,j>0and{X}_i\ne Y_j\end{array}$ بنابراین وقتی که $X_i\ne Y_j$ باشد٫ زیر مسئله ما پیدا کردن LCS برای $X_{i-1}$ و $Y_{i-1}$ است. در غیر این صورت ما دو زیر مسئله داریم:

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

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

پرونده:Lcs-Fig1.PNG

شکل ۱

االگوریتم را با استفاده از روش برنامه‌نویسی پویا پیاده‌سازی می‌کنیم. الگوریتم دو رشته $X=⟨x_1,x_2,...,x_m⟩$ و $Y=⟨y_1,y_2,...,y_n⟩$ را به عنوان ورودی دریافت می‌کند(شکل ۲). الگوریتم مقادیر $c[i,j]$ که نشان دهدنده طول LCS است را داخل آرایه $c[1..m,1..n]$ ذخیره می‌کند. عناصر آرایه به ترتیب row-major پر می‌شوند. یهنی ابتدا اولین سطر c به ترتیب از چپ به راست پر می‌شود، سپس سطر دوم و الی آخر. علاوه بر این الگوریتم آرایه دیگری به نام $b[1..m,1..n]$ را نیز پر می‌کند. این آرایه جهت حرکت را ذخیره می‌کند.

پرونده:Lcs-Fig2.PNG

شکل ۲

مقدار 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).$

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

منابع

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