Задача знаходжання найбольшай агульнай падпаслядоўнасці (, LCS) — задача пошуку паслядоўнасці, якая з'яўляецца падпаслядоўнасцю некалькіх паслядоўнасцей (звычайна дзвюх). Часта задача вызначаецца як пошук усіх найбольшых падпаслядоўнасцей. Гэта класічная задача інфарматыкі, якая мае ўжыванне, у прыватнасці, у задачы параўнання тэкставых файлаў (утыліта diff), а таксама ў біяінфарматыцы.
Падпаслядоўнасць можна атрымаць з некаторай канечнай паслядоўнасці, калі выдаліць з апошняй некаторае мноства яе элементаў (магчыма пустое). Напрыклад, BCDB з'яўляецца падпаслядоўнасцю з ABCDBAB. Будзем лічыць, што паслядоўнасць Z з'яўляецца агульнай падпаслядоўнасцю паслядоўнасцей X і Y, калі Z з'яўляецца падпаслядоўнасцю як X, так і Y. Патрабуецца для дзвюх паслядоўнасцей X і Y знайсці агульную падпаслядоўнасць найбольшай даўжыні. Заўважым, што НАП можа быць некалькі.
Рашэнне задачы Параўнаем два метады рашэння: поўны перабор і дынамічнае праграмаванне.
Поўны перабор Існуюць розныя падыходы рашэння дадзенай задачы пры поўным пераборы — можна перабіраць варыянты падпаслядоўнасці, варыянты выкрэслівання з дадзеных паслядоўнасцей і г. д. Аднак у любым выпадку, час працы праграмы будзе экспанентай ад даўжыні радка.
Метад дынамічнага праграмавання A B C B 0 0 0 0 0 D 0 ← 0 ← 0 ← 0 ← 0 C 0 ← 0← 0↖ 1 ← 1 B 0 ← 0 ↖ 1 ← 1 ↖ 2 A 0 ↖ 1 ← 1 ← 1 ↑ 2
Спачатку знойдзем даўжыню найбольшай падпаслядоўнасці. Дапусцім, мы шукаем рашэнне для выпадку (n1, n2), дзе n1, n2 — даўжыні першага і другога радка. Хай ужо існуюць рашэнні для усіх падзадач (m1, m2), меншых зададзенай. Тады задача (n1, n2) зводзіцца да меншых падзадач наступным чынам:
Зараз вернемся да задачы будавання падпаслядоўнасці. Для гэтага ў існуючы алгарытм дададзім запамінанне для кожнай задачы той падзадачы, праз якую яна вырашаецца. Наступным дзеяннем, пачынаючы з апошняга элемента, падымаемся да пачатку па напрамках, зададзеных першым алгарытмам, і запісваем сімвалы ў кожнай пазіцыі. Гэта і будзе адказам у дадзенай задачы.
Час працы алгарытму будзе .
Катэгорыя:Радковыя алгарытмы