= {a, b, c} |
S_{1} = bcb |
S_{2} = baab |
S_{3} = babc |
Dynamic programming | Requires too much memory unless the number of input-sequences are very small. |
Branch and bound | Requires too much time unless the alphabet is very small. |
Majority merge | The best known heuristic when the number of sequences is large compared to the alphabet size. [1] |
Greedy | (take two sequences and replace them by their optimal shortest common supersequence until a single string is left) Worse than majority merge. [1] |
Genetic algorithms | Indications that it might be better than majority merge. [1] |
WHILE there are non-empty input sequences s <- The most frequent symbol at the start of non-empty input-sequences. Add s to the end of S. Remove s from the beginning of each input sequence that starts with s. END WHILEMajority merge performs very well when the number of sequences is large compared to the alphabet size.
T = {} FOR i = 0 TO S_{l} found = FALSE FOR j = 0 TO |L| IF first symbol in L(j) = the symbol x_{i} maps to THEN Remove first symbol from L(j) found = TRUE END IF END FOR IF found = TRUE THEN Add the symbol x_{i} maps to to the end of T END IF END FOR
Interleaved, Initial | Just the length/time value for interleaved initial solution. |
Concatenated, Initial | Just the length/time value for concatenated initial solution. |
Interleaved, One | The length of the solution/time when a local change is defined as only one exchange and the initial solution is interleaved. |
Interleaved, All | The length of the solution/time when a local change is defined as one exchange for each input-sequence and the initial solution is interleaved. |
Concatenated One | The length of the solution/time when a local change is defined as only one exchange and the initial solution is concatenated. |
Concatenated, All | The length of the solution/time when a local change is defined as one exchange for each input-sequence and the initial solution is concatenated.. |