Plej longa komuna subvica problemo

La **plej longa komuna subvica problemo** estas la serĉo por kompetenta maniero trovi la plej longan komunan subvicon (PLKS, LCS). Ĉi tiu komputika problemo jam gajnis elstarecon danke al sia estado en la 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 *2k* subvicoj de **X**. Ĉi tio devus bezoni 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 n_1, \dots, n_N. Brutforta maniero estas provo de ĉiuj eblas subvicoj, kvanto de kiuj estas:

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

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

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

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 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** = 1,...,xm > kaj **Y** = 1,...,yn > estu vicoj, kaj lasu **Z** = 1,...,zk > estu iuj ajn PLKS de **X** kaj **Y**.

* Se xm = yn, tiam zk = xm = yn kaj Zk-1 estas PLKS de Xm-1 kaj Yn-1.
* Se xm ≠ yn, tiam zk ≠ xm, implicas, ke Z estas PLKS de Xm-1 kaj Y.
* Se xm ≠ yn, tiam zk ≠ yn implicas, ke Z estas PLKS de X kaj Yn-1.

2. *Verku rikuran solvon*

Komputilo-sciencistoj estas konsentintaj sur la formulo:

: 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}

La rekursia formulo baziĝas sur la optimala substruktura teoremo en parto 1. Ĝi engaĝas fundamentantan rikurecon por la optimala valoro. *c[i, j]* estas la longo de la PLKS en vicoj *Xi* kaj *Yj*. 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 i = yj) {
     c[mi,j] = c[i,j-1]) {
     c[mi,j] \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}

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 
* Vortaro de algoritmoj kaj datum-strukturoj: plej longa komuna subvico

Kategorio:Kombinatoriko
Kategorio:Formalaj lingvoj
Kategorio:Dinamika programado