Vidi fonton por Plej longa komuna subvica problemo

{{polurinda}}
La '''plej longa komuna subvica problemo''' estas la serĉo por kompetenta maniero trovi la plej longan komunan [[subvico]]n (PLKS, LCS). Ĉi tiu [[komputiko|komputika]] problemo jam gajnis elstarecon danke al sia estado en la [[biokomputiko|biokomputika]] kampo.

La eroj de ''subvico'' ne nepre devas esti sinsekvaj eroj de la fonto vico, tiel ekzemple ''BCDB'' estas subvico de ''ABCBDAB''

Ĝi devas ne esti konfuzita kun la [[plej longa komuna subĉena problemo]].
La diferenco estas en tio ke en ''[[subĉeno]]'' la eroj nepre devas esti sinsekvaj eroj de la fonto vico, tiel ekzemple ''BCDB'' ne estas subĉeno de ''ABCBDAB''

Malnova maniero serĉi por subvicon estis per uzo de brutforta metodo:

Estu donita vico '''X''', difinu ĉiujn eblajn subvicojn de '''X''', kaj kontrolu ĉu ĉiu subvico estis subvico de '''Y''', konservante la plej longan trovitan subvicon. Ĉiu subvico de '''X''' respektivas al [[subaro]] de aro ''{1, 2, 3, 4, ...,k}''. Tiel estas ''2<sup>k</sup>'' subvicoj de '''X'''. Ĉi tio devus bezoni [[eksponenta tempo|eksponentan tempon]], farante ĉi tiu serĉon ege senefika por longaj vicoj, kiel fadeneroj de [[DNA]] de la [[homo]].

== Ĝenerala okazo ==

En ĝenerala okazo por ajna kvanto de enigaj vicoj la problemo estas [[NP-peza]].

Estu ''N'' vicoj de longoj <math>n_1, \dots, n_N</math>. Brutforta maniero estas provo de ĉiuj eblas subvicoj, kvanto de kiuj estas:

:<math>\sum_{L=0}^{\min_{i=1}^{N}{n_i}} \prod_{k=1}^{N}{n_k \choose L}</math>.

Se la kvanto de vicoj estas konstanto, la problemo estas solvebla en [[polinoma tempo]] per [[dinamika programado]] en tempo

:<math>\Theta\left(N \prod_{k=1}^{N} n_k\right)</math>

Por specialaj okazaj de la problemo estas pli rapidaj manieroj.

PLKS ne nepre estas sola, ekzemple tiu de "ABC" kaj "ACB" estas "AB" aŭ "AC". Problemo de trovo de ĉiuj PLKS estas pli malfacila, ĉar la kvanto de PLKS povas pligrandiĝi eksponente en la plej malbona okazo eĉ por du enigaj vicoj.

== Kvar ŝtupoj al problemo, [[polinoma tempo|polinoma tempa]] redakcio ==

1. ''Analizu PLKS-propraĵojn''

Multaj komputilaj sciencistoj estas skribintaj paperojn pri PLKS-propraĵojn, inkluzivantajn unu kie PLKS havas optimalan substruktura propraĵo.

La '''''optimala substrukturo de PLKS-Teoremo''''' estas

Lasu ke '''X''' = < x<sub>1</sub>,...,x<sub>m</sub> > kaj '''Y''' = < y<sub>1</sub>,...,y<sub>n</sub> > estu vicoj, kaj lasu '''Z''' = < z<sub>1</sub>,...,z<sub>k</sub> > estu iuj ajn PLKS de '''X''' kaj '''Y'''.

* Se x<sub>m</sub> = y<sub>n</sub>, tiam z<sub>k</sub> = x<sub>m</sub> = y<sub>n</sub> kaj Z<sub>k-1</sub> estas PLKS de X<sub>m-1</sub> kaj Y<sub>n-1</sub>.
* Se x<sub>m</sub> ≠ y<sub>n</sub>, tiam z<sub>k</sub> ≠ x<sub>m</sub>, implicas, ke Z estas PLKS de X<sub>m-1</sub> kaj Y.
* Se x<sub>m</sub> ≠ y<sub>n</sub>, tiam z<sub>k</sub> ≠ y<sub>n</sub> implicas, ke Z estas PLKS de X kaj Y<sub>n-1</sub>.

2. ''Verku rikuran solvon''

Komputilo-sciencistoj estas konsentintaj sur la formulo:

:<math> c[i,j] = \begin{cases} 0, & \mbox{ se } i = 0 \mbox{ aux } j = 0 \\ c[i-1,j-1]+1, & \mbox{ se } i>0, j>0\mbox{ kaj }x_i = y_j \\ max(c[i,j-1],c[i-1,j]) & \mbox{ se } i>0, j>0\mbox{ kaj } x_i \ne y_j \end{cases}</math>

La rekursia formulo baziĝas sur la [[optimala substruktura teoremo]] en parto 1. Ĝi engaĝas fundamentantan [[rikureco]]n por la optimala valoro. ''c[i, j]'' estas la longo de la PLKS en vicoj ''X<sub>i</sub>'' kaj ''Y<sub>j</sub>''. La unua parto de la formulo diras ke se ĉu unu el la vicoj havas longon 0, tiam povas esti neniu pozitiva subvico de nula vico. La aliaj du partoj rompas la PLKS-on aparte en pli malgrandan subproblemon ĝis kiam oni atingas la nulan vicon.

3. ''Komputu la PLKS-on''

* Estas kelkaj algoritmoj havebla al komputilo-sciencistoj; kelkaj engaĝas eksponentajn funkciajn tempajn funkciojn, aliaj estas en polinoma tempo. Unu tia polinoma funkcio estas la algoritmo ''ĝenerala PLKS delto''.

 PLKS-Delto(X,Y)
  m <- longo[X];
  n <- longo[Y];
  '''por''' i <- 1 '''al''' m, '''fari''' c[i,0] <-0;
   '''por''' j <- 0 '''al''' n, '''fari''' c[0,j] <-0;
    b <- c;
  '''por''' i <- 1 '''al''' m, '''fari''' {
   '''por''' j <- 1 '''al''' n '''fari''' {
    '''se''' (x<sub>i</sub> = y<sub>j</sub>) {
     c[mi,j] <- c[i-1,j-1]+1;
     b[mi,j] <- "SUPRO-MALDEKSTRO";
    }
    '''alie''' '''se''' (c[i-1,j] >= c[i,j-1]) {
     c[mi,j] <- c[i-1,j];
     b[mi,j] <- "SUPRO";
    }
    '''alie''' {
     c[mi,j] <- c[i,j-1];
     b[mi,j] <- "MALDEKSTRO";
    }
   }
  }
  '''redoni''' c kaj b

* PLKS delto estas algoritmo, kiu prenas du vicojn '''X''' kaj '''Y''' kiel enigojn. La algoritmo kreas tabelon ''c'' kaj kun la longoj de X kaj Y. La algoritmo ankaŭ havas tabelon ''b'', kiu estas kopio de ''c'', kiu estas uzata por stori la optiman solvaĵon de la PLKS. La cetero de la algoritmo uzas la formulon en paŝo 2 por komputi la PLKS, kaj plenigi la tabelon. La algoritmo rulas en tempo ''[[Granda O|O]](mn)'', kie ''m'' kaj ''n'' estas la longoj de '''X''' kaj '''Y''' respektive. Estas pli kompetentaj algoritmoj, nome PLKS Α kaj PLKS Β, sed ĉi tiu algoritmo estas la plej intuicia.

4. ''Konstrui la PLKS-on''

* La ''b''-tabelo redonita per la algoritmo estas uzata por konstrui la PLKS-on. La ''b''-baremo povas aspekti simile al:

:<math>\begin{bmatrix} ! & 0 & 0 & 0 & 0 & 0\\
 0 & SUPRO-MALDEKSTRO & MALDEKSTRO & 0 & 0 & 0 \\
 0 & 0 & 0 & SUPRO-MALDEKSTRO & 0 & 0\\
 0 & 0 & 0 & 0 & SUPRO-MALDEKSTRO & 0 \\
 0 & 0 & 0 & 0 & SUPRO & MALDEKSTRO \\
\end{bmatrix}
</math>

Startante de la pozicio ''(m, n)'', oni sekvas la direkton de la sagoj, ĝis oni atingos la finon de la PLKS, signifitan per !. La valoroj en ''c''-tabelo respektivaj al la pozicioj "SUPRO-MALDEKSTRO" en la ''b''-tabelo devus esti eroj de PLKS. La PLKS estas konstruita en dorsflanko ordo uzante ĉi tiun metodon. La konstruada paŝo prenas tempon ''O(m + n)'' por plenumiĝi, pro tia ĝi rulas en [[lineara tempo]].

Moderna PLKS-serĉo-metodoj estas liverintaj algoritmoj kiuj estas tranĉintaj suben la eksponentan funkcian tempon al polinoma tempo. La PLKS daŭras esti ekzamenata per komputilo-sciencistoj, provantaj trovi eĉ pli rapidan tempon, eble tiun en [[logaritmo-lineara tempo]].

== Trovi la liston de redaktoj (''Diff'' algoritmo) ==

Jena algoritmo donos la liston de redaktoj bezonataj por fari Y egala al X (la algoritmo de [[diff]]):

'''Notacio:''' [n,m] estas PLKS komponanto je X[n] kaj Y[n]

'''Premisoj:''' La PLKS kiel fundamenti per findLCS() estas lokita sur stako movanta de la suba-dekstra angulo kaj
sekvanta la direkto-sagojn por formi la LCS.

 malnovElem <---- [-1,-1]
 '''dum''' stako estas ne malplena
  elem <---- elstakigu datumon de stako
  // diff ne postulas LCS-komponantojn, 
  // sed adicii al listo ĉi tie laŭvole
  '''por''' i=malnovElem[n] al elem[n]
   adiciu "forviŝi X(mi) de listo de redaktoj"
  '''por''' i=malnovElem[m] al elem[m]
   adiciu "enigi Y(i) al listo de redaktoj"

'''Notu:''' Diff(1) traktos ĉiun "breĉon" inter PLKS-komponantoj kiel "peco"

== Referencoj ==

* A421: SR10, pg.228.

== Eksteraj ligiloj ==
* [http://nist.gov/dads/HTML/longestcommn.html Vortaro de algoritmoj kaj datum-strukturoj: plej longa komuna subvico]{{404|date=August 2021 |bot=InternetArchiveBot |fix-attempted=yes }}

[[Kategorio:Kombinatoriko]]
[[Kategorio:Formalaj lingvoj]]
[[Kategorio:Dinamika programado]]