Найбольшая агульная падпаслядоўнасць
Задача знаходжання найбольшай агульнай падпаслядоўнасці (англ.: longest common subsequence, 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) зводзіцца да меншых падзадач наступным чынам:
f (
n
1
,
n
2
)
{
0 ,
n
1
= 0 ∨
n
2
= 0
f (
n
1
− 1 ,
n
2
− 1 ) + 1 ,
s [
n
1
]
s [
n
2
]
m a x ( f (
n
1
− 1 ,
n
2
) , f (
n
1
,
n
2
− 1 ) ) ,
s [
n
1
] ≠ s [
n
2
]
{\displaystyle f(n_{1},n_{2})=\left\{{\begin{array}{ll}0,&n_{1}=0\lor n_{2}=0\f(n_{1}-1,n_{2}-1)+1,&s[n_{1}]=s[n_{2}]\max(f(n_{1}-1,n_{2}),f(n_{1},n_{2}-1)),&s[n_{1}]\neq s[n_{2}]\end{array}}\right.}
![\{\displaystyle f(n_\{1\},n_\{2\})=\left\\{\{\begin\{array\}\{ll\}0,&n_\{1\}=0\lor n_\{2\}=0\\f(n_\{1\}-1,n_\{2\}-1)+1,&s[n_\{1\}]=s[n_\{2\}]\\max(f(n_\{1\}-1,n_\{2\}),f(n_\{1\},n_\{2\}-1)),&s[n_\{1\}]\neq s[n_\{2\}]\end\{array\}\}\right.\}](https://wikimedia.org/api/rest_v1/media/math/render/svg/75c57975c8aa6f17d110f1c07c9721c2deea7982)
Зараз вернемся да задачы будавання падпаслядоўнасці. Для гэтага ў існуючы алгарытм дададзім запамінанне для кожнай задачы той падзадачы, праз якую яна вырашаецца. Наступным дзеяннем, пачынаючы з апошняга элемента, падымаемся да пачатку па напрамках, зададзеных першым алгарытмам, і запісваем сімвалы ў кожнай пазіцыі. Гэта і будзе адказам у дадзенай задачы.
Час працы алгарытму будзе
O
(
n
1
⋅
n
2
)
{\displaystyle \mathrm {O} ,(n_{1}\cdot n_{2})}
Катэгорыя·Радковыя алгарытмы