Задача о кратчайшей суперструне | Комплект 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.