Le të kuptojmë fillimisht termin "Nën sekuencë".

Nënsekuenca :

Është një sekuencë që shfaqet në të njëjtin rend relativ, por jo domosdoshmërisht e ngjitur.

Në LCS, ne duhet të gjejmë nënsekuencat më të gjata të zakonshme që janë në të njëjtin rend relativ.

Nëse gjatësia e sekuencës është n atëherë 2^n nënsekuenca janë të mundshme.

Le të fillojmë me një shembull të thjeshtë që do të pastrojë konceptin e algoritmit LCS:

Pse mund të dëshirojmë të zgjidhim problemin LCS?

Biologjia molekulare: Sekuencat (gjenet) e ADN-së mund të përfaqësohen si sekuenca me katër shkronja ACGT, që korrespondojnë me katër nën-molekulat që formojnë ADN-në. Kur biologët gjejnë një sekuencë të re, ata zakonisht duan të dinë se me cilat sekuenca të tjera është më e ngjashme. Një mënyrë për të llogaritur se sa të ngjashme janë dy sekuenca është gjetja e gjatësisë së nënsekuencës së tyre më të gjatë të përbashkët.

Krahasimi i skedarëve:Në programin Unix "diff" përdoret për të krahasuar dy versione të ndryshme të të njëjtit skedar, për të përcaktuar se çfarë ndryshimesh janë bërë në skedar. Ai funksionon duke gjetur një nënrend të përbashkët më të gjatë të rreshtave të dy skedarëve; çdo rresht në vijim nuk është ndryshuar, kështu që ajo që shfaq është grupi i mbetur i rreshtave që kanë ndryshuar.

Rishfaqja e ekranit: Shumë redaktues teksti shfaqin një pjesë të një skedari në ekran, duke përditësuar imazhin e ekranit ndërsa skedari ndryshohet. Për terminalet e ngadaltë të telefonimit, këto programe duan t'i dërgojnë terminalit sa më pak karaktere të jetë e mundur për ta bërë atë të përditësojë saktë ekranin. Nënsekuenca e zakonshme ju tregon pjesët e ekranit që janë tashmë të sakta dhe nuk kanë nevojë të ndryshohen.

Si të zgjidhet?

Pse zgjedhim Programimin Dinamik për të zgjidhur këtë problem?

Metoda e Rekursionit për këtë problem është joefikase sepse e thërret veten në mënyrë të përsëritur për një numër të vogël nënproblemesh, gjë që kërkon më shumë kohë.

Në rekursion, të njëjtat nënprobleme zgjidhen shumë herë të ndryshme. ne duhet të kontrollojmë nëse e kemi bërë tashmë më parë. Nëse po, ne kërkojmë zgjidhjen në vend që ta rillogaritim atë. Për të reduktuar numrin e thirrjeve të përsëritura, përdoret qasja nga lart-poshtë, e cila njihet si Memoization.

Rekursioni kontrollon se çfarë renditje plotësojmë në vargje, por do të kishim marrë të njëjtat rezultate nëse i plotësonim në ndonjë renditje tjetër. Ne mund të përdorim diçka që viziton grupin në mënyrë sistematike. E vetmja gjë për të cilën duhet të shqetësohemi është se kur plotësojmë një qelizë L[i,j], duhet të dimë tashmë vlerat nga të cilat varet. Për këtë arsye ne do ta përshkojmë grupin mbrapa, nga rreshti i fundit duke punuar deri në të parën dhe nga kolona e fundit duke punuar deri në të parën. Kjo qasje nga poshtë-lart njihet si Programimi dinamik.

Programimi dinamik LCS

Hapat:

  1. Le të jenë sekuencat hyrëse A dhe B me gjatësi i dhe j respektivisht.

2. Le të jetë LCS(A[i],B[j]) gjatësia e LCS e dy sekuencave A dhe B.

3. Nëse karakteret e të dy sekuencave përputhen, atëherë shtoni 1 dhe kaloni te karakteret vijuese si në A ashtu edhe në B.

4. Nëse nuk përputhen, atëherë marrin maksimumin ose duke lëvizur karakteret në sekuencën e parë A ose në sekuencën e dytë B.

5. Ndiqni qasjen nga poshtë-lart dhe printoni LCS.

Algoritmi:

Shembull:

X=ABCDA Y=ACBDEA

Kohë kompleksiteti:

Nëse m dhe n janë gjatësia e dy sekuencave përkatësisht, atëherë kompleksiteti kohor i këtij algoritmi dinamik do të jetë O(mn).

Kompleksiteti i hapësirës:

Nëse m dhe n janë respektivisht madhësia e dy sekuencave, atëherë hapësira e kërkuar nga ky algoritëm do të jetë O(m+n).