Что известно о точной сложности самой короткой проблемы суперструн? Может ли это быть решено быстрее, чем ? Существуют ли известные алгоритмы, которые решают кратчайшую суперструну без сокращения до TSP?
UPD: подавляет полиномиальные факторы.
Самая короткая проблема суперструн - это проблема, ответом которой является самая короткая строка, которая содержит каждую строку из заданного набора строк. Речь идет о расширении оптимизации известной NP-сложной задачи Shortest Superstring (Garey and Johnson, p.228).
cc.complexity-theory
ds.algorithms
graph-theory
tsp
exp-time-algorithms
Алекс Головнев
источник
источник
Ответы:
Предполагая, что строки имеют полином длины от , тогда да, по крайней мере, 2 n - Ω ( √n время решения. Причина - хорошо известное сокращение от самой короткой общей проблемы суперструн до ATSP с целочисленными весами полиномиального размера, которую вы, в свою очередь, можете решить с помощью полиномиальной интерполяции, если вы можете считать гамильтоновы циклы в ориентированном мультиграфе. Последняя проблема имеет2n-Ω( √2n−Ω(n/logn√) время решения.
Бьорклунд 20122n−Ω(n/logn√)
Переход от ATSP с весами для каждой пары вершин u , v к гамильтонову циклу происходит следующим образом:wuv u,v
Для , где w sum - верхняя граница для всех сумм n весовых коэффициентов в экземпляре ATSP, построим один граф G r, где вы заменяете каждый весовой коэффициент w u v на r w u v дуг из у к v .r=1,2,⋯,wsum wsum n Gr wuv rwuv u v
Решая подсчет гамильтонов цикл для каждого , можно с помощью полиномиальной интерполяции построить многочлен Х ш суммы л = 0 л г л с в л равна числу TSP туров в первоначальном графике веса л . Следовательно, поиск наименьшего l такого, что a l отличен от нуля, решает проблему.Gr ∑wsuml=0alrl al l l al
источник
Я изучил проблему и нашел некоторые результаты. Кратчайшая общая суперструна (SCS) может быть решена за время с использованием только полиномиального пространства ( Кон, Готтлиб, Кон ; Карп ; Бакс, Франклин ).2n
Самое известное приближение (Палуч).21130
Самое известное приближение сжатия составляет (Палуч).34
Если SCS может быть аппроксимирован фактором по двоичному алфавиту, то он может быть аппроксимирован фактором α по любому алфавиту ( Василевская-Уильямс ).α α
SCS не может быть аппроксимирована с отношением лучше, чем если P = NP ( Karpinski, Schmied ).1.0029
Максимальное сжатие не может быть аппроксимировано с коэффициентом, превышающим если P = NP ( Karpinski, Schmied ).1.0048
Буду благодарен за любые дополнения и предложения.
источник
Вот кратчайшая проблема суперструн: вам дано строк s 1 , … , s n над некоторым алфавитом Σ, и вы хотите найти самую короткую строку над Σ, которая содержит каждый s i как подпоследовательность последовательных символов, то есть подстроку.n s1,…,sn Σ Σ si
Когда мы говорим о точных алгоритмах для задачи, нахождение длины самой короткой суперструны эквивалентно нахождению максимального сжатия C, которое является суммой всех последовательных перекрытий строк в конечной суперструне, то есть C = ∑ i | с я | - L .L C C=∑i|si|−L
Насколько я знаю, самый быстрый точный алгоритм для самой короткой суперструны работает в ( 2 n ), где n - количество строк. Это простой алгоритм динамического программирования, аналогичный алгоритму динамического программирования для самого длинного пути (и других задач):O∗ 2n n
Для каждого подмножества строк и строки v в S мы вычисляем максимальное сжатие по всем суперструнам по S, где v - первая строка, появляющаяся в суперструне, сохраняя ее как C (( v , S )). Мы делаем это, сначала обрабатывая все подмножества только с одним элементом, а затем собирая значения C (( v , S )) для подмножеств S в k строках из тех, что в k - 1 строках. В частности:S v S S v v,S v,S S k k−1
Для каждой строки мы рассматриваем все подмножества S ′ на k - 1 строках, которые не включают в себя u, и устанавливаем значение для ( u , u ∪ S ′ ) максимального значения над строками v в S ′ суммы максимума перекрытие U с V с C (( Vu S′ k−1 u u,u∪S′ v S′ u v )).v,S′
Конечное время выполнения не более O (n22n+n2l ), где - максимальная длина строки.l
Есть лучшие алгоритмы, если вы предполагаете, что мало, или попарные наложения малы, размер алфавита маленький и т. Д., Но я не знаю ни одного алгоритма, который быстрее, чем 2 n .l 2n
источник