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

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

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

مسئلهٔ طولانی‌ترین زیر رشتهٔ صعودی در زمان (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-۱ کوچکتر است که با فرض الگوریتم در مورد آرایهٔ 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. (۱۹۹۹). 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. (۱۹۹۹). 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 (۲۰۰۴) A central limit theorem for the optimal selection process for monotone subsequences of maximum expected length. Stochastic Processes and their Applications، Volume ۱۱۴، Issue ۲، ۲۸۷-۳۱۳.
• Samuels، S.M. and J.M. Steele (۱۹۸۱). 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