Учитывая некоторые строковые фрагменты, я хотел бы найти самую короткую возможную единственную строку («выходная строка»), которая содержит все фрагменты. Фрагменты могут перекрывать друг друга в выходной строке.
Пример:
Для фрагментов строки:
BCDA
AGF
ABC
Следующая выходная строка содержит все фрагменты и была сделана наивным добавлением:
BCDAAGFABC
Однако эта выходная строка лучше (короче), поскольку она использует перекрытия:
ABCDAGF
^
ABC
^
BCDA
^
AGF
Я ищу алгоритмы для этой проблемы. Не совсем важно найти строго самую короткую выходную строку, но чем короче, тем лучше. Я ищу алгоритм лучше, чем очевидный наивный, который попытался бы добавить все перестановки входных фрагментов и убрать перекрытия (которые выглядели бы как NP-Complete).
Я начал работу над решением, и оно оказалось довольно интересным; Я хотел бы посмотреть, что другие люди могут придумать. Я добавлю мою работу в этот вопрос через некоторое время.
источник
Ответы:
То, о чем вы спрашиваете, - это проблема Shortest Common Superstring, для которой не существует алгоритма, который бы работал во всех случаях. Но это общая проблема (при сжатии и секвенировании ДНК), и несколько приближенных алгоритмов хорошо известны.
«Жадные» алгоритмы, как правило, считаются наиболее эффективными (например, они имеют наихудший наихудший случай).
Прочтите статью Джонатана Тернера «Алгоритмы аппроксимации для самой короткой общей проблемы суперструн», чтобы получить больше информации.
источник