A leghosszabb közös rész

Az elméleti számítástechnikában a két szekvenciának vagy két karakterláncnak a leghosszabb részszekvenciája az a szekvencia, amely a két szekvencia részszekvenciája és maximális méretű. A probléma megoldása dinamikus programozással érhető el .

A tetszőleges számú szekvenciára való általánosítás NP-nehéz probléma . Az algoritmus végrehajtási ideje exponenciális a szekvenciák számában.

Példa

A következő két karaktersorozat esetében:

"a B C D E",
"Ceij",

a leghosszabb közös alszakasz "ez".

Ebben a problémában elengedhetetlen, hogy a közös elemek azonos sorrendben legyenek a különböző szekvenciákban, de nem feltétlenül egymást követőek: az „e” nem következik a „c” -vel az első szekvenciában.

Nyers erő algoritmus

Megszámlálva látható, hogy vannak hosszúságú húr szekvenciái . Ha mindet nyers erővel megpróbáljuk megtalálni a leghosszabbat, amely egy másik húr folytatása, ezért exponenciális összetettséggel bír , ami a gyakorlatban nem kívánatos. $2 ^ {n}$ $nem$

Két szekvencia polinomiális időfelbontása

Ilyen részsorrendet egy dinamikus programozási algoritmussal nyerhetünk, amelynek végrehajtási ideje arányos a két szekvencia hosszának szorzatával.

A megoldás felépítése

A következő tételnek (ahol a szekvencia első karakterét jelöli) köszönhetően csökkenteni lehet azt a problémát, hogy két adott karakterlánc között megtalálja a leghosszabb közös szekvenciát (PLSC) két megadott húr között . ${\ displaystyle X_ {l}}$ $l$ $x$

Tétel - Legyen és legyen két szekvencia, és vagy a leghosszabb közös folytatása és . Ezután: ${\ displaystyle X = [x_ {1}, \ pontok, x_ {m}]}$ ${\ displaystyle Y = [y_ {1}, \ pontok, y_ {n}]}$ ${\ displaystyle Z = [z_ {1}, \ pontok, z_ {k}]}$ $x$ $Y$

Ha akkor és több PLSC értéke és ; ${\ displaystyle x_ {m} = y_ {n}}$ ${\ displaystyle z_ {k} = x_ {m} = y_ {n}}$ ${\ displaystyle Z_ {k-1}}$ ${\ displaystyle X_ {m-1}}$ ${\ displaystyle Y_ {n-1}}$
Ha akkor, ha van , ami egy PLSC a és ; ${\ displaystyle x_ {m} \ neq y_ {n}}$ ${\ displaystyle z_ {k} \ neq x_ {m}}$ $Z$ ${\ displaystyle X_ {m-1}}$ $Y$
Ha akkor, ha van , ami egy PLSC a és . ${\ displaystyle x_ {m} \ neq y_ {n}}$ ${\ displaystyle z_ {k} \ neq y_ {n}}$ $Z$ $x$ ${\ displaystyle Y_ {n-1}}$

A három eset , és a teljes, amely lehetővé teszi számunkra, hogy csökkentsék magunkat probléma kisebb méretű. ${\ displaystyle \ left \ langle x_ {m} = y_ {n} \ right \ rangle}$ ${\ displaystyle \ left \ langle x_ {m} \ neq y_ {n} ~ {\ mathsf {ET}} ~ z_ {k} \ neq x_ {m} \ right \ rangle}$ ${\ displaystyle \ left \ langle x_ {m} \ neq y_ {n} ~ {\ mathsf {ET}} ~ z_ {k} \ neq y_ {n} \ right \ rangle}$

A leghosszabb közös alszakaszok hossza

Létrehozunk egy kétdimenziós tömböt , amelyben az egyes celláknak tartalmazniuk kell a és közötti PLSC-k hosszát . Ezután lépésről lépésre kiszámíthatjuk az egyes indexpárokat és . Az előző tételből következik a képlet: ${\ displaystyle c [1 \ cdot \ cdot m] [1 \ cdot \ cdot n]}$ ${\ displaystyle c [i] [j]}$ $X_ {i}$ $Y_ {j}$ ${\ displaystyle c [i] [j]}$ $én$ $j$

{\ displaystyle c [i] [j] = {\ begin {esetben} 0 és {\ text {si}} i = 0 {\ text {or}} j = 0, \\ c [i-1] [j - 1] +1 és {\ text {si}} i, j> 0 {\ text {et}} x_ {i} = y_ {j}, \\ {\ mathsf {max}} (c [i] [ j- 1], c [i-1] [j]) és {\ text {si}} i, j> 0 {\ text {et}} x_ {i} \ neq y_ {j}. \ esetek vége }}}

A dobozok tartalmának kiszámítása bonyolultan elvégezhető , mivel az egyes dobozok tartalma kiszámítható az előző dobozokból . $vs.$ ${\ displaystyle {\ mathcal {O}} (mn)}$ ${\ displaystyle {\ mathcal {O}} (1)}$

Hosszabb közös utószerzés megszerzése

Az előző képlet lehetővé teszi a négyzetek lépésenkénti kiszámítását . Ennek köszönhetően helyreállíthatunk egy hosszabb közös részt. $vs.$

Ehhez egy útvonalat csinálunk a következő szabály szerint ${\ displaystyle c [m] [n]}$

Érték mezőből : ${\ displaystyle c [i] [j]}$ $\ alfa$

Ha , megyünk az érték mezőbe, és hozzáadjuk ezt a karaktert ( ) az épülő PLSC elején. ${\ displaystyle x_ {i} = y_ {j}}$ ${\ displaystyle c [i-1] [j-1]}$ ${\ displaystyle \ alfa -1}$ ${\ displaystyle x_ {i} = y_ {j}}$

Ha , xén≠yj{\ displaystyle x_ {i} \ neq y_ {j}} ${\ displaystyle x_ {i} \ neq y_ {j}}$
- Igen , közönyösen megyünk a dobozhoz ill . ${\ displaystyle c [i] [j-1] = c [i-1] [j] = \ alfa}$ ${\ displaystyle c [i-1] [j]}$ ${\ displaystyle c [i] [j-1]}$
- Ha megyünk a dobozhoz ${\ displaystyle c [i] [j-1] = \ alpha> c [i-1] [j]}$ ${\ displaystyle c [i] [j-1]}$
- Ha megyünk a dobozhoz ${\ displaystyle c [i-1] [j] = \ alpha> c [i] [j-1]}$ ${\ displaystyle c [i-1] [j]}$

Az útvonalra példát ad a következő táblázat, amelynek köszönhetően arra következtethetünk, hogy az MJAU az MZJAWXU és az XMJYAUZ közös hosszabb alszekvenciája :

		0	1	2	3	4	5.	6.	7
		Ø	M	Z	J	NÁL NÉL	W	x	U
0	Ø	0	0	0	0	0	0	0	0
1	x	0	0	0	0	0	0	1	1
2	M	0	1	1	1	1	1	1	1
3	J	0	1	1	2	2	2	2	2
4	Y	0	1	1	2	2	2	2	2
5.	NÁL NÉL	0	1	1	2	3	3	3	3
6.	U	0	1	1	2	3	3	3	4
7	Z	0	1	2	2	3	3	3	4

Az algoritmus összetettsége

Miután ismert, a PLSC megszerzése bonyolult . $vs.$ ${\ displaystyle {\ mathcal {O}} (m + n)}$

Megjegyzések és hivatkozások

Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest és Clifford Stein , Bevezetés az algoritmikába , Dunod ,2002[ a kiadás részlete ], 15.4. fejezet, Dinamikus programozás: a leghosszabb közös részsorozat .

Lásd is

A leghosszabb szigorúan növekvő utóhatás
A leghosszabb közös alsor (korlátozás abban az esetben, ha az egyes szekvenciákban kiválasztott elemek egymást követik)
Legközelebbi csatorna