Suurin yhteinen osasarja
Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 7.7.2022 tarkistetusta versiosta . tarkastukset vaativat 15 muokkausta .Tehtävä löytää pisin yhteinen osasekvenssi ( eng. longest common subsequence , LCS) on löytää sekvenssi , joka on useiden sekvenssien (yleensä kahden) osasekvenssi. Usein ongelmaksi määritellään kaikkien suurimpien osasekvenssien löytäminen. Tämä on klassinen tietojenkäsittelytieteen ongelma , jolla on sovelluksia erityisesti tekstitiedostojen vertailuongelmassa ( diff -apuohjelma ) sekä bioinformatiikassa .
Osasekvenssi voidaan saada jostakin äärellisestä sekvenssistä, jos jokin sen elementtijoukko (mahdollisesti tyhjä) poistetaan jälkimmäisestä. Esimerkiksi BCDB on sekvenssin ABCDBAB osasekvenssi. Sanomme, että sekvenssi Z on sekvenssien X ja Y yhteinen osasekvenssi, jos Z on sekä X:n että Y:n osasekvenssi. Kahden sekvenssin X ja Y on löydettävä suurin pituinen yhteinen osasekvenssi. Huomaa, että NOP:ita voi olla useita.
Merkintä! Osasekvenssi on erilainen kuin osamerkkijono . Jos esimerkiksi on lähdesekvenssi "ABCDEF", "ACE" on osasekvenssi, mutta ei osamerkkijono, ja "ABC" on sekä osasekvenssi että osamerkkijono.
Ongelman ratkaisu
Verrataan kahta ratkaisumenetelmää: raakavoimahaku ja dynaaminen ohjelmointi .
Täysi luettelo
On olemassa erilaisia lähestymistapoja tämän ongelman ratkaisemiseen täydellisellä luettelolla - voit selvittää osasekvenssivaihtoehdot, poistovaihtoehdot näistä sarjoista jne. Kuitenkin ohjelman ajoaika on joka tapauksessa polynomi merkkijonojen pituuksissa.
Dynaaminen ohjelmointimenetelmä
| 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 |
Etsi ensin suurimman osajonon pituus. Oletetaan, että etsitään ratkaisua tapaukselle (n 1 , n 2 ), jossa n 1 , n 2 ovat ensimmäisen ja toisen merkkijonon pituudet. Olkoon ratkaisut jo olemassa kaikille annettua pienemmille osatehtäville (m 1 , m 2 ). Sitten tehtävä (n 1 , n 2 ) pelkistetään pienempiin osatehtäviin seuraavasti:
![{\displaystyle f(n_{1},n_{2})=\left\{{\begin{array}{ll}0,&n_{1}=0\tai 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}} \oikea.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/247fee8787b87a38bc364638e91965c11181338a)
Palataan nyt osasekvenssin rakentamisen ongelmaan. Tätä varten lisäämme olemassa olevaan algoritmiin muistin jokaiselle alitehtävän tehtävälle, jonka kautta se ratkaistaan. Seuraava toiminto, alkaen viimeisestä elementistä, siirrymme alkuun ensimmäisen algoritmin antamia ohjeita pitkin ja kirjoitamme merkit kuhunkin kohtaan. Tämä on vastaus tähän ongelmaan.
Algoritmin ajoaika on .
Katso myös
- Algoritmit merkkijonoilla
- Suurin yhteinen osamerkkijono
Linkit
- Suurimman yhteisen osasekvenssin löytäminen . algolist.ru. Haettu: 15. elokuuta 2013.
- Algoritmi suurimman yhteisen sekvenssin pituuden löytämiseksi . coders.ask-ru.net.
| jouset | |
|---|---|
| Merkkijonojen samankaltaisuusmitat | |
| Alimerkkijonohaku | |
| palindromit | |
| Jakson tasaus | |
| Suffiksirakenteet | |
| muu | |