A legnagyobb közös sorozat

A leghosszabb közös alszekvencia ( eng.  longest common subsequence , LCS) megtalálásának feladata egy olyan szekvencia megtalálása , amely több szekvencia (általában kettő) részsorozata. A problémát gyakran úgy határozzák meg, hogy megtaláljuk az összes legnagyobb részsorozatot. Ez egy klasszikus számítástechnikai probléma , amelynek különösen a szövegfájl-összehasonlítási problémában (a diff segédprogramban ), valamint a bioinformatikában vannak alkalmazásai .

Valamelyik véges sorozatból egy részsorozatot kaphatunk, ha elemeinek (esetleg üres) halmazát eltávolítjuk az utóbbiból. Például a BCDB az ABCDBAB szekvencia alsorozata. Azt mondjuk, hogy egy Z sorozat az X és Y szekvenciák közös részsorozata, ha Z mind X, mind Y részsorozata. Két X és Y szekvenciának meg kell találnia a legnagyobb hosszúságú közös részsorozatot. Vegye figyelembe, hogy több NOP is lehet.

Jegyzet! Egy részsorozat különbözik a részkarakterlánctól . Például, ha van egy "ABCDEF" forrássorozat, akkor az "ACE" egy részsorozat lesz, de nem egy részkarakterlánc, és az "ABC" egy részsorozat és egy részkarakterlánc is.

A probléma megoldása

Hasonlítsunk össze két megoldási módot: a brute-force keresést és a dinamikus programozást .

Teljes felsorolás

Különböző megközelítések léteznek ennek a problémának a teljes felsorolással történő megoldására - kiválaszthatja a részsorozat opcióit, a törlési lehetőségeket ezekből a sorozatokból stb. Azonban a program futási ideje minden esetben polinom lesz a karakterláncok hosszában.

Dinamikus programozási módszer

Először keresse meg a legnagyobb részsorozat hosszát. Tegyük fel, hogy az (n 1 , n 2 ) esetre keresünk megoldást , ahol n 1 , n 2  az első és a második karakterlánc hossza. Legyenek már megoldások minden, az adottnál kisebb részfeladatra (m 1 , m 2 ). Ezután a feladat (n 1 , n 2 ) kisebb részfeladatokra redukálódik az alábbiak szerint:

Most térjünk vissza a részsorozat felépítésének problémájához. Ehhez hozzáadunk egy memóriát a meglévő algoritmushoz a részfeladat minden egyes feladatához, amelyen keresztül azt megoldják. A következő műveletben az utolsó elemtől kezdve az első algoritmus által megadott irányok mentén felmegyünk az elejére, és minden pozícióba írjuk a karaktereket. Ez lesz a válasz erre a problémára.

Az algoritmus futási ideje .

Lásd még

• Algoritmusok karakterláncokon
• Legnagyobb közös részkarakterlánc

Linkek

• A legnagyobb közös részsorozat megtalálása . algolist.ru. Letöltve: 2013. augusztus 15. (Orosz)

• Algoritmus a legnagyobb közös szekvencia hosszának meghatározásához . coders.ask-ru.net. (Orosz)