Cea mai mare succesiune comună
Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 7 iulie 2022; verificările necesită 15 modificări .Sarcina de a găsi cea mai lungă subsecvență comună ( de exemplu, cea mai lungă subsecvență comună , LCS) este sarcina de a găsi o secvență care este o subsecvență a mai multor secvențe (de obicei două). Adesea, problema este definită ca găsirea celor mai mari subsecvențe. Aceasta este o problemă clasică de informatică , care are aplicații, în special, în problema de comparare a fișierelor text ( utilitatea diff ), precum și în bioinformatică .
O subsecvență poate fi obținută dintr-o secvență finită dacă o mulțime de elemente (eventual goale) este îndepărtată din aceasta din urmă. De exemplu, BCDB este o subsecvență a secvenței ABCDBAB. Spunem că o secvență Z este o subsecvență comună a secvențelor X și Y dacă Z este o subsecvență a ambelor X și Y. Este necesar ca două secvențe X și Y să găsească o subsecvență comună de cea mai mare lungime. Rețineți că pot exista mai multe NOP.
Notă! O subsecvență este diferită de un subșir . De exemplu, dacă există o secvență sursă „ABCDEF”, atunci „ACE” va fi o subsecvență, dar nu un subșir, iar „ABC” va fi atât o subsecvență, cât și un subșir.
Rezolvarea problemei
Să comparăm două metode de soluție: căutarea prin forță brută și programarea dinamică .
Enumerarea completă
Există diferite abordări pentru a rezolva această problemă cu o enumerare completă - puteți sorta opțiunile de subsecvență, opțiunile de ștergere din aceste secvențe etc. Cu toate acestea, în orice caz, timpul de rulare a programului va fi un polinom în lungimile șirurilor.
Metoda de programare dinamică
| A | B | C | D | ||
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | |
| D | 0 | ← 0 | ← 0 | ← 0 | ↖ 1 |
| C | 0 | ← 0 | ← 0 | ↖ 1 | ← 1 |
| D | 0 | ← 0 | ← 0 | ↑ 1 | ↖ 2 |
| A | 0 | ↖ 1 | ← 1 | ← 1 | ↑ 2 |
Mai întâi, găsiți lungimea celei mai mari secvențe. Să presupunem că căutăm o soluție pentru cazul (n 1 , n 2 ), unde n 1 , n 2 sunt lungimile primului și celui de-al doilea șir. Fie că există deja soluții pentru toate subproblemele (m 1 , m 2 ) mai mici decât cea dată. Apoi sarcina (n 1 , n 2 ) este redusă la subsarcini mai mici, după cum urmează:
![{\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_{1}[n_{1}]=s_{2}[n_{2}]\\max(f(n_{1}-1, n_{2}),f(n_{1},n_{2}-1)),&s_{1}[n_{1}]\neq s_{2}[n_{2}]\end{array}} \dreapta.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/247fee8787b87a38bc364638e91965c11181338a)
Acum să revenim la problema construcției unei subsecvențe. Pentru a face acest lucru, adăugăm algoritmului existent o memorie pentru fiecare sarcină a subsarcinii prin care se rezolvă. Următoarea acțiune, pornind de la ultimul element, urcăm până la început pe direcțiile date de primul algoritm, și scriem caracterele în fiecare poziție. Acesta va fi răspunsul la această problemă.
Timpul de rulare al algoritmului va fi .
Vezi și
- Algoritmi pe șiruri
- Cel mai mare subșir comun
Link -uri
- Găsirea celei mai mari subsecvențe comune . algolist.ru. Preluat: 15 august 2013.
- Algoritm pentru găsirea lungimii celei mai mari subsecvențe comune . codificatori.ask-ru.net.
| Siruri de caractere | |
|---|---|
| Măsuri de similitudine a șirurilor | |
| Căutare subșir | |
| palindromuri | |
| Alinierea secvenței | |
| Structuri de sufix | |
| Alte | |