طولانی‌ترین زیررشته صعودی

مسئلهٔ طولانی‌ترین زیر رشته صعودی (به انگلیسی: Longest increasing subsequence) یا LIS این است که در یک رشتهٔ داده شده طولانی‌ترین زیر رشته‌ای را بیابیم که عناصر آن زیر رشته از کوچک به بزرگ مرتب شده باشند. اعضای زیر رشتهٔ انتخاب شده لزومی ندارد متوالی باشد.

یک رشته از اعداد که طولانی‌ترین زیر رشتهٔ صعودی ان به یک رنگ دیگر نمایا است.

مسئلهٔ طولانی‌ترین زیر رشتهٔ صعودی در زمان (O(n log n قابل حل است البته الگوریتم‌های ساده‌تری با زمان $n^{2}$ نیز دارد. با فرض این که n طول رشتهٔ اصلی باشد که می‌خواهیم در ان مسئله را حل کنیم.

مثال

برای مثال به رشته زیر توجه کنید.

۰، ۸، ۴، ۱۲، ۲، ۱۰، ۶، ۱۴، ۱، ۹، ۵، ۱۳، ۳، ۱۱، ۷، ۱۵، …

یک طولانی‌ترین زیر رشتهٔ صعودی از رشتهٔ داده شده برابر رشتهٔ زیر است.

۰، ۲، ۶، ۹، ۱۳، ۱۵.

زیر رشتهٔ بالا طولی برابر ۶ دارد و در رشته اصلی داده شده هیچ زیر رشتهٔ صعودی به طول۷ وجود ندارد. طولانی‌ترین زیر رشتهٔ صعودی یکتا نیست برای مثال در رشتهٔ داده شده یک زیر رشتهٔ صعودی دیگر به طول ۶ در زیر آورده شده‌است.

۰، ۴، ۶، ۹، ۱۱، ۱۵

روابط با دیگر الگوریتم‌ها

مسئلهٔ طولانی‌ترین زیر رشتهٔ صعودی رابطهٔ نزدیکی با مسئلهٔ طولانی‌ترین زیر رشتهٔ مشترک میان ۲ رشته Longest common subsequence problem دارد. به این صورت که طولانی‌ترین زیر رشتهٔ صعودی در یک رشته داده شده برابر طولانی‌ترین زیر رشتهٔ مشترک میان رشته داده شده و رشته دیگری (که برابر مرتب شدهٔ رشتهٔ اولیه است) است.

بزرگترین خوشه در گراف جایگشت، تعریف می‌شود طولانی‌ترین زیر رشته نزولی در جایگشتی که گراف از آن ساخته شده‌است. با منفی کردن تمامی اعداد می‌توان این مسئله را با مسئلهٔ طولانی‌ترین زیر رشتهٔ صعودی حل کرد و در حقیقت نیز برای یافتن بزرگترین خوشه در گراف جایگشت از مسئله طولانی‌ترین زیر رشتهٔ مشترک استفاده می‌کنند.

یک الگوریتم کارامد

الگوریتمی که بزودی شرح می‌دهیم می‌تواند مسئلهٔ ما را در زمان(O(n log n حل کند؛ و تنها از آرایه‌ها و جستجوی دودویی استفاده می‌کند.

برای اولین بار این الگوریتم در سال ۱۹۷۵ توسط M.L.Fredman طراحی شد.

شرح الگوریتم بدین صورت است که فرض کنید که رشتهٔ اصلی ما در آرایه X ذخیره شده باشد و طول آن n است. الگوریتم داده‌ها را در ۲ آرایهٔ دیگر ذخیره خواهد کرد.

[M[j - برابر مکان کوچک‌ترین عنصر در آرایهٔ x است که زیر رشته‌ای با طول j به آن عنصر ختم شود.

[P[k - مکان عنصر ماقبل [x[k را در طولانیترین زیر رشتهٔ صعودی که به [x[k ختم می‌شود را ذخیره می‌کند.

به علاوه الگوریتم در متغیر L، طول بزرگترین زیر رشتهٔ صعودی را که تا هر مرحله توسط الگوریتم یافت می‌شود ذخیره می‌کند.

ذکر این نکته ضروریست که در هر مرحله از الگوریتم رشته ی:

[[X[M[۱]]، X[M[۲]]، …، X[M[L

غیر نزولی است چرا که اگر زیر رشتهٔ نزولی در آن وجود داشته باشد که مثلاً به [[X[M[i ختم شود در این صورت وجود دارد زیر رشتهٔ صعودی در آرایه اصلی که عنصر انتهایی ان از [[X[M[i-1 کوچکتر است که با فرض الگوریتم در مورد آرایهٔ M در تضاد است. پس نتیجه می‌شود می‌توان در این آرایه از جستجوی دودویی استفاده کرد.

الگوریتم:

 L = 0
 for i= 1, 2, ... n:
 binary search for the largest positive j ≤ L such that X[M[ j]]  <X[ i ] (or set j = 0 if no such value exists)
     P[ i ] = M[ j]
      if  j == L or X[ i ] <X[M[ j+1]]:
        M[ j+1 ] = i
        L = max(L, j+1)

نتیجه الگوریتم بالا پیدا کردن طول طولانی‌ترین زیر رشتهٔ صعودی است و خود زیر رشته از روی آرایهٔ P به‌طور بازگشتی قابل دست یابی است. به این صورت که:

می‌دانیم که آخرین عضو زیر رشته عنصر [[X[M[L است؛ و با توجه به تعریف آرایهٔ P دومین عنصر از انتهای زیر رشته عنصر [[[X[P[M[L است؛ و بدین شکل زیر رشته به فورم زیر بدست می‌آید.

...، [[X[P[P[M[L]]]], X[P[M[L]]], X[M[L.

و همچنین برای تحلیل الگوریتم می‌توان گفت که چون الگوریتم برای هر عنصر از رشتهٔ اصلی تنها یک جستجوی دودویی استفاده می‌کند از (O(n log nاست.

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

در اینجا شبه کد یک الگوریتم داینامیک کندتر از الگوریتم بالا ولی ساده‌تر آورده شده‌است.

function lis_length( a )
    n := a.length
    q := new Array(n)
    for k from 1 to n:
        max := 0;
        for j from 1 to k-1, if a[k]> a[j]:
            if q[j]> max, then set max = q[j].
        q[k] := max + 1;
    max := 0
    for i from 1 to n:
        if q[i]> max, then set max = q[i].
    return max;

منابع

• Aldous D.J. and Diaconis, P. (1999). Longest Increasing Subsequences: From

Patience Sorting to the Baik-Deift-Johansson Theorem. Bul letin Amer. Math. Society, Vol. ۳۶، ۴۱۳–۴۳۲.

• Baik, J. ، Deift, P.A. and Johansson, K. (1999). On the Distribution of the

Length of the Longest Increasing Subsequence of Random Permutations. Tech- nical Report math.Co/۹۹۸۱۰۱۰۵.

• Bruss F. T. and F. Delbaen (2004) A central limit theorem for the optimal selection process for monotone subsequences of maximum expected length. Stochastic Processes and their Applications, Volume 114, Issue ۲، ۲۸۷–۳۱۳.
• Samuels, S.M. and J.M. Steele (1981). Optimal Sequential Selection of a

Monotone Sequence from a Random Sample. Ann. Probab. ۹، ۹۳۷–۹۴۷.

• Algorithmist's Longest Increasing Subsequence

لینک‌های پیشنهادی

• Erdős–Szekeres theorem، اثبات می‌کند هر رشته به طول n^۲+۱ از عناصر متمایز دارای یک زیر رشته نزولی و هم چنین یک زیر رشتهٔ صعودی به طول n+۱ است.
• Patience sorting، یک الگوریتم کارامد دیگر برای یافتن بزرگترین زیر رشتهٔ صعودی.
• Plactic monoid
• Algorithmist's Longest Increasing Subsequence