مسئلهٔ طولانی ترین زیر رشته صعودی ( به انگلیسی: Longest increasing subsequence ) یا LIS این است که در یک رشتهٔ داده شده طولانی ترین زیر رشته ای را بیابیم که عناصر آن زیر رشته از کوچک به بزرگ مرتب شده باشند. اعضای زیر رشتهٔ انتخاب شده لزومی ندارد متوالی باشد.
مسئلهٔ طولانی ترین زیر رشتهٔ صعودی در زمان ( O ( n log n قابل حل است البته الگوریتم های ساده تری با زمان n 2 نیز دارد. با فرض این که n طول رشتهٔ اصلی باشد که می خواهیم در ان مسئله را حل کنیم.
برای مثال به رشته زیر توجه کنید.
یک طولانی ترین زیر رشتهٔ صعودی از رشتهٔ داده شده برابر رشتهٔ زیر است.
زیر رشتهٔ بالا طولی برابر ۶ دارد و در رشته اصلی داده شده هیچ زیر رشتهٔ صعودی به طول۷ وجود ندارد. طولانی ترین زیر رشتهٔ صعودی یکتا نیست برای مثال در رشتهٔ داده شده یک زیر رشتهٔ صعودی دیگر به طول ۶ در زیر آورده شده است.
مسئلهٔ طولانی ترین زیر رشتهٔ صعودی رابطهٔ نزدیکی با مسئلهٔ طولانی ترین زیر رشتهٔ مشترک میان ۲ رشته Longest common subsequence problem دارد. به این صورت که طولانی ترین زیر رشتهٔ صعودی در یک رشته داده شده برابر طولانی ترین زیر رشتهٔ مشترک میان رشته داده شده و رشته دیگری ( که برابر مرتب شدهٔ رشتهٔ اولیه است ) است.
بزرگترین خوشه در گراف جایگشت، تعریف می شود طولانی ترین زیر رشته نزولی در جایگشتی که گراف از آن ساخته شده است. با منفی کردن تمامی اعداد می توان این مسئله را با مسئلهٔ طولانی ترین زیر رشتهٔ صعودی حل کرد و در حقیقت نیز برای یافتن بزرگترین خوشه در گراف جایگشت از مسئله طولانی ترین زیر رشتهٔ مشترک استفاده می کنند.
الگوریتمی که بزودی شرح می دهیم می تواند مسئلهٔ ما را در زمان ( O ( n log n حل کند؛ و تنها از آرایه ها و جستجوی دودویی استفاده می کند.
برای اولین بار این الگوریتم در سال ۱۹۷۵ توسط M. L. Fredman طراحی شد.
شرح الگوریتم بدین صورت است که فرض کنید که رشتهٔ اصلی ما در آرایه X ذخیره شده باشد و طول آن n است. الگوریتم داده ها را در ۲ آرایهٔ دیگر ذخیره خواهد کرد.
به علاوه الگوریتم در متغیر L، طول بزرگترین زیر رشتهٔ صعودی را که تا هر مرحله توسط الگوریتم یافت می شود ذخیره می کند.
ذکر این نکته ضروریست که در هر مرحله از الگوریتم رشته ی:
غیر نزولی است چرا که اگر زیر رشتهٔ نزولی در آن وجود داشته باشد که مثلاً به [[X[M[i ختم شود در این صورت وجود دارد زیر رشتهٔ صعودی در آرایه اصلی که عنصر انتهایی ان از [[X[M[i - 1 کوچکتر است که با فرض الگوریتم در مورد آرایهٔ M در تضاد است. پس نتیجه می شود می توان در این آرایه از جستجوی دودویی استفاده کرد.
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفمسئلهٔ طولانی ترین زیر رشتهٔ صعودی در زمان ( O ( n log n قابل حل است البته الگوریتم های ساده تری با زمان n 2 نیز دارد. با فرض این که n طول رشتهٔ اصلی باشد که می خواهیم در ان مسئله را حل کنیم.
برای مثال به رشته زیر توجه کنید.
یک طولانی ترین زیر رشتهٔ صعودی از رشتهٔ داده شده برابر رشتهٔ زیر است.
زیر رشتهٔ بالا طولی برابر ۶ دارد و در رشته اصلی داده شده هیچ زیر رشتهٔ صعودی به طول۷ وجود ندارد. طولانی ترین زیر رشتهٔ صعودی یکتا نیست برای مثال در رشتهٔ داده شده یک زیر رشتهٔ صعودی دیگر به طول ۶ در زیر آورده شده است.
مسئلهٔ طولانی ترین زیر رشتهٔ صعودی رابطهٔ نزدیکی با مسئلهٔ طولانی ترین زیر رشتهٔ مشترک میان ۲ رشته Longest common subsequence problem دارد. به این صورت که طولانی ترین زیر رشتهٔ صعودی در یک رشته داده شده برابر طولانی ترین زیر رشتهٔ مشترک میان رشته داده شده و رشته دیگری ( که برابر مرتب شدهٔ رشتهٔ اولیه است ) است.
بزرگترین خوشه در گراف جایگشت، تعریف می شود طولانی ترین زیر رشته نزولی در جایگشتی که گراف از آن ساخته شده است. با منفی کردن تمامی اعداد می توان این مسئله را با مسئلهٔ طولانی ترین زیر رشتهٔ صعودی حل کرد و در حقیقت نیز برای یافتن بزرگترین خوشه در گراف جایگشت از مسئله طولانی ترین زیر رشتهٔ مشترک استفاده می کنند.
الگوریتمی که بزودی شرح می دهیم می تواند مسئلهٔ ما را در زمان ( O ( n log n حل کند؛ و تنها از آرایه ها و جستجوی دودویی استفاده می کند.
برای اولین بار این الگوریتم در سال ۱۹۷۵ توسط M. L. Fredman طراحی شد.
شرح الگوریتم بدین صورت است که فرض کنید که رشتهٔ اصلی ما در آرایه X ذخیره شده باشد و طول آن n است. الگوریتم داده ها را در ۲ آرایهٔ دیگر ذخیره خواهد کرد.
به علاوه الگوریتم در متغیر L، طول بزرگترین زیر رشتهٔ صعودی را که تا هر مرحله توسط الگوریتم یافت می شود ذخیره می کند.
ذکر این نکته ضروریست که در هر مرحله از الگوریتم رشته ی:
غیر نزولی است چرا که اگر زیر رشتهٔ نزولی در آن وجود داشته باشد که مثلاً به [[X[M[i ختم شود در این صورت وجود دارد زیر رشتهٔ صعودی در آرایه اصلی که عنصر انتهایی ان از [[X[M[i - 1 کوچکتر است که با فرض الگوریتم در مورد آرایهٔ M در تضاد است. پس نتیجه می شود می توان در این آرایه از جستجوی دودویی استفاده کرد.
