Насколько это сложно с точки зрения вычислительной сложности? - PullRequest
Новая
       49

Насколько это сложно с точки зрения вычислительной сложности?

3 голосов
/ 15 мая 2011

Итак, у меня есть проблема, которая в основном такова: у меня есть куча строк, и я хочу построить DAG так, чтобы каждый путь соответствовал строке, и наоборот.Однако у меня есть свобода произвольно переставлять мои струны.Порядок символов не имеет значения.Сгенерированные мной группы доступности баз данных связаны с затратами.По сути, стоимость ветви в группе обеспечения доступности баз данных пропорциональна длине дочерних путей.

Например, допустим, у меня есть строки BAAA, CAAA, DAAA, и я создаю группу DAG, представляющую их без перестановки.их.Я получаю:

() -> (B, C, D) -> A -> A -> A

, где кортеж представляет ветвление.

Более дешевое представлениедля моих целей было бы:

() -> A -> A -> A -> (B, C, D)

Проблема заключается в следующем: учитывая n строк, переставлять строки, такиечто соответствующая группа обеспечения доступности баз данных имеет самую дешевую стоимость, где функция стоимости: если мы сначала проследим график от источника в глубину, слева направо, общее число посещаемых нами узлов с кратностью.

Итакстоимость первого примера - 12, потому что мы должны посетить A несколько раз при обходе.Стоимость второго примера - 6, потому что мы посещаем A только один раз, прежде чем имеем дело с ветвями.

У меня есть ощущение, что эта проблема - NP Hard.Это похоже на вопрос о формальных языках, и я не достаточно знаком с такими алгоритмами, чтобы понять, как я должен идти к сокращению.Мне не нужен полный ответ сам по себе, но если бы кто-то мог указать на класс хорошо известных проблем, которые кажутся связанными, я был бы очень признателен.

1 Ответ

2 голосов
/ 15 мая 2011

Перефразировать:

Заданные слова w 1 ,…, w n , вычислить перестановки x 1 из w 1,…, x n из w n , чтобы минимизировать размер хранилища дерева x 1 ,…, x n .

Предполагая алфавит неограниченного размера, эта проблема является NP-трудной через сокращение от покрытия вершины.(Я полагаю, что это может быть размер с фиксированным параметром в размере алфавита.) Сокращение легко: с учетом графа, пусть каждая вершина будет отдельной буквой и создайте двухбуквенное слово для каждого ребра.

На глубине ноль ровно один узел, а на глубине два столько же узлов, сколько имеется ребер.Возможные наборы узлов на первой глубине - это в точности наборы узлов, которые являются покрытиями вершин.

...