Warning
This page is located in archive. Go to the latest version of this course pages.

Nejkratší společná supersekvence

Kdybychom měli k úloze přistupovat jako k černé skříňce, neměli byste informace o dílčích sekvencích využívat nikde jinde než v ohodnocovací funkci. V této úloze ale je povoleno využívat či analyzovat konkrétní dílčí sekvence i jinde, např. v rekombinačních operátorech.

Popis problému

Je dána množina řetezců znaků dané abecedy. Cílem je nalézt takovou posloupnost znaků dané abecedy (supersekvenci), že všechny původní řetezce jsou v ní zcela obsažené. Řetězec r je obsažen v supersekvenci S právě tehdy, když všechny znaky řetězce r jsou přítomny v supersekvenci S a to v pořadí, v jakém se vyskytují v r.

  • Vstup:
    • Abeceda A, ze které jsou tvořeny řetězce.
    • N řetězců (ne nutně stejné délky).
  • Výstup: Supersekvence S splňující výše uvedenou vlastnost.

Možné reprezentace

  • Lineární řetězec znaků dané abecedy.
                   s1:  ca ag cca  cc ta    cat  c a
                   s2:  c gag ccat ccgtaaa g  tt  g
                   s3:   aga acc tgc  taaatgc t a ga
                        ----------------------------
      Supersequence S:  cagagaccatgccgtaaatgcattacga

Jednotná ohodnocovací funkce

Kvalita supersekvence S se počítá jako

<latex> $f(S) = C(S) + L(S)$, </latex>

kde <latex>$C(S)$</latex> je celkový počet znaků, které S pokrývá, a <latex>$L(S)$</latex> je příspěvek za délku supersekvence počítaný jako

<latex> $L(S) = \frac{SumL - Length(S)}{SumL}$, </latex>

kde <latex>$SumL$</latex> je součet všech znaků ve vstupních řetězcích. Tato funkce je maximalizována.

courses/a0m33eoa/semestralni_ulohy/supersekvence/start.txt · Last modified: 2018/11/19 14:25 by xposik