Største fælles efterfølger
Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 7. juli 2022; checks kræver 15 redigeringer .Opgaven med at finde den længste fælles undersekvens ( eng. longest common subsequence , LCS) er opgaven med at finde en sekvens , der er en undersekvens af flere sekvenser (normalt to). Ofte er problemet defineret som at finde alle de største delsekvenser. Dette er et klassisk datalogisk problem , som især har applikationer i tekstfilsammenligningsproblemet ( diff -værktøjet ) såvel som i bioinformatik .
En undersekvens kan opnås fra en endelig rækkefølge, hvis et sæt af dens elementer (muligvis tomme) fjernes fra sidstnævnte. For eksempel er BCDB en undersekvens af sekvensen ABCDDBAB. Vi siger, at en sekvens Z er en fælles undersekvens af sekvenserne X og Y, hvis Z er en undersekvens af både X og Y. Det kræves for to sekvenser X og Y at finde en fælles undersekvens af den største længde. Bemærk, at der kan være flere NOP'er.
Bemærk! En undersekvens er forskellig fra en understreng . For eksempel, hvis der er en kildesekvens "ABCDEF", så vil "ACE" være en undersekvens, men ikke en understreng, og "ABC" vil være både en undersekvens og en understreng.
Løsning af problemet
Lad os sammenligne to løsningsmetoder: brute-force-søgning og dynamisk programmering .
Fuld opregning
Der er forskellige tilgange til at løse dette problem med en komplet opregning - du kan sortere efterfølgermuligheder, slettemuligheder fra disse sekvenser osv. Under alle omstændigheder vil programmets køretid være et polynomium i længderne af strengene.
Dynamisk programmeringsmetode
| EN | 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 |
| EN | 0 | ↖ 1 | ← 1 | ← 1 | ↑ 2 |
Find først længden af den største delsekvens. Antag, at vi leder efter en løsning på tilfældet (n 1 , n 2 ), hvor n 1 , n 2 er længden af den første og anden streng. Lad løsninger allerede eksistere for alle delproblemer (m 1 , m 2 ) mindre end den givne. Derefter reduceres opgaven (n 1 , n 2 ) til mindre delopgaver som følger:
![{\displaystyle f(n_{1},n_{2})=\venstre\{{\begin{array}{ll}0,&n_{1}=0\eller 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}} \ret.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/247fee8787b87a38bc364638e91965c11181338a)
Lad os nu vende tilbage til problemet med at konstruere en undersekvens. For at gøre dette tilføjer vi til den eksisterende algoritme en hukommelse for hver opgave i underopgaven, hvorigennem den løses. Den næste handling, startende fra det sidste element, går vi op til begyndelsen langs retningerne givet af den første algoritme, og skriver tegnene i hver position. Dette vil være svaret på dette problem.
Algorithmens køretid vil være .
Se også
- Algoritmer på strenge
- Største fælles understreng
Links
- At finde den største fælles følge . algolist.ru. Hentet: 15. august 2013.
- Algoritme til at finde længden af den største fælles sekvens . coders.ask-ru.net.
| Strenge | |
|---|---|
| String lighedsmål | |
| Understrengssøgning | |
| palindromer | |
| Sekvensjustering | |
| Suffiksstrukturer | |
| Andet | |