Задача о кратчайшей суперструне | Комплект 2 (с использованием крышки набора)

Для набора из n строк S найдите наименьшую строку, которая содержит каждую строку в данном наборе как подстроку. Мы можем предположить, что ни одна строка в arr [] не является подстрокой другой строки.

Примеры:

Ввод: S = {"001", "01101", "010"}
Выход: 0011010  

Ввод: S = {"компьютерщики", "викторина", "для"}
Вывод: geeksquizfor

Ввод: S = {"catg", "ctaagt", "gcta", "ttca", "atgcatc"}
Вывод: gctaagttcatgcatc

В предыдущем посте мы обсудили решение, которое оказалось 4 приблизительным (предполагалось как 2 приблизительного).
В этом посте обсуждается решение, которое может быть доказано как приблизительно _{2H n.} где H _n = 1 + 1/2 + 1/3 +… 1 / n. Идея состоит в том, чтобы преобразовать задачу кратчайшей суперструны в задачу множества покрытий (задаче множества покрытий заданы некоторые подмножества вселенной, и каждое заданное подмножество имеет связанную стоимость. Задача состоит в том, чтобы найти набор данных подмножеств с наименьшей стоимостью, чтобы все элементы вселенная покрыты). Для задачи Set Cover нам нужно иметь вселенную и подмножества вселенной с соответствующими затратами.

Ниже приведены шаги по преобразованию кратчайшей суперструны в набор обложек.

1) Пусть S - множество заданных строк.
   S = {s 1 , s 2 , ... s n }

2) Вселенная для задачи Set Cover - S (Нам нужно
   найти суперструну, в которой каждая строка
   как подстрока)

3) Давайте инициализируем подмножества, которые будут рассматриваться для вселенной, как
     Подмножества = {{s 1 }, {s 2 }, ... {s n }}
   Стоимость каждого подмножества - это длина строки в нем.

3) Для всех пар строк s i и s j в S,
     Если s i и s j перекрываются
      а) Постройте строку r ijk, где k -
         максимальное перекрытие между ними.
      б) Добавьте набор, представленный r ijk, в Подмножества,
           т.е. подмножества = подмножества U набор (r ijk )
         Набор, представленный r ijk, - это набор 
         всех строк, которые являются его подстрокой.
         Стоимость подмножества составляет длину r ijk .

4) Теперь задача преобразована в Set Cover, мы можем 
   запустите приблизительный алгоритм Greedy Set Cover, чтобы найти
   установить обложку S, используя подмножества. Стоимость каждого элемента в
   Подмножества - это длина строки в нем.

Пример:

S = {s1, s2, s3}.
s1 = "001"
s2 = "01101"
s3 = "010"

[Combination of s1 and s2 with 2 overlapping characters]
r122 = 001101 

[Combination of s1 and s3 with 2 overlapping characters]
r132 = 0010 

Similarly,
r232 = 011010
r311 = 01001
r321 = 0101101

Now set cover problem becomes as following:

Universe to cover is {s1, s2, s3}

Subsets of the universe and their costs :

{s1}, cost 3 (length of s1)
{s2}, cost 5 (length of s2)
{s3}, cost 5 (length of s3)

set(r122), cost 6 (length of r122)
The set r122 represents all strings which are
substrings of r122. 
Therefore set(r122) = {s1, s2}

set(r132), cost 3 (length of r132)
The subset r132 represents all strings which are
substrings of r132
Therefore set(r132) = {s1, s3}

Similarly there are more subsets for set(r232), 
set(r311), and set(r321).

So we have a set cover problem with universe and subsets
of universe with costs associated with every subset.

Мы обсуждали, что экземпляр задачи Shortest Superstring может быть преобразован в экземпляр задачи Set Cover за полиномиальное время.

Обратитесь к этому для доказательства того факта, что алгоритм, основанный на Set Cover, является приблизительным _{2H n.}

Ссылка:
http://www.cs.dartmouth.edu/~ac/Teach/CS105-Winter05/Notes/wan-ba-notes.pdf
http://fileadmin.cs.lth.se/cs/Personal/Andrzej_Lingas/superstring.pdf
http://math.mit.edu/~goemans/18434S06/superstring-lele.pdf

Эта статья предоставлена Дираджем Гуптой . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.