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 2^k 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 = < x₁,...,x_m > kaj Y = < y₁,...,y_n > estu vicoj, kaj lasu Z = < z₁,...,z_k > estu iuj ajn PLKS de X kaj Y.

• Se x_m = y_n, tiam z_k = x_m = y_n kaj Z_k-1 estas PLKS de X_m-1 kaj Y_n-1.
• Se x_m ≠ y_n, tiam z_k ≠ x_m, implicas, ke Z estas PLKS de X_m-1 kaj Y.
• Se x_m ≠ y_n, tiam z_k ≠ y_n implicas, ke Z estas PLKS de X kaj Y_n-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}\neq 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 X_i kaj Y_j. 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 (xi = yj) {
    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 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:

${\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