Решите это сопоставление с экспоненциальным временем работы в режиме грубой силы.

Question

У меня есть вопрос о сопоставлении. Утверждается следующим образом.

У меня есть последовательность, состоящая из двух символов {l, h}.

1. Символ l может быть отображен на номер из {1,2,3}. (l обозначает низкий)
2. Символ h может быть отображен на номер из {4,5,6}. (Ч выступает за высокие)

Например, у меня есть последовательность (я называю это исходной последовательностью) с длиной = 6. Это [ч, л, ч, л, ч, л]. Эта последовательность может быть преобразована в подробную последовательность приведенными выше правилами сопоставления. Детальная последовательность может быть [6,1,5,2,4,3]. А для последовательности с длиной = 6 существует 6^3 подробных последовательностей.

Я получаю разностную последовательность из подробной последовательности, вычисляя попарные различия. Например, моя подробная последовательность [6,1,5,2,4,3], то соответствующая разностная последовательность равна [6-1,1-5,5-2,2-4,4-3] = [ 5, -4,3, -2,1]. Следовательно, наибольшее значение входа разностной последовательности составляет 5, что составляет 6 минус 1, а наименьшее значение этого показателя составляет -5 в результате 1 минус 6.

Теперь у меня база данных состоит из м разница последовательности с длиной = 5. моей последовательностью запроса является исходной последовательностью с длиной = 6. Я хочу, чтобы найти, что:

Среди м разностных последовательности , чем те, соответствующая исходная последовательность может быть моей последовательностью запросов. Если они не существуют, программа вернет нулевой набор. Если они существуют, программа вернет набор, состоящий из них.

Например, для последовательности разностей [5, -4,3, -2,1] соответствующая исходная последовательность может быть [h, l, h, l, h, l]. Следовательно, ff моя последовательность запросов [h, l, h, l, h, l], [5, -4,3, -2,1] будет в возвращенном наборе, если [5, -4,3, - 2,1] находится в базе данных.

Для моей реальной проблемы последовательность запросов имеет длину = n. База данных состоит из m разностных последовательностей с длиной = n-1.

Метод грубой силы может быть следующим: Для исходной последовательности ввода перечислены его 3^n подробные последовательности и получаются 3^n разностные последовательности. Для каждой из последовательностей разностей проверьте, существует ли она в базе данных.
Грубая сила примет O (3^n). Я знаю, что это экспоненциальное время работы не очень хорошо.

Я хочу иметь более быстрый алгоритм. Алгоритм аппроксимации также выглядит хорошо для меня.

Большое вам спасибо.

Answer 1

Каждая последовательность различий может быть создана не более четырех h-l последовательностей.

Итак, предварительно обработайте свою базу данных, чтобы построить индекс из h-l последовательностей в интересующие вас последовательности различий.

Например:

[1, -1, 0, 2, -1] 

Это должно исходить от одной из этих последовательностей:

[3 2 3 3 1 2] -> l l l l l l 
[4 3 4 4 2 3] -> h l h h l l 
[5 4 5 5 3 4] -> h h h h l h 
[6 5 6 6 4 5] -> h h h h h h 

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

Построение этого индекса является временем O (mn) и использует дополнительное пространство O (mn). После того, как вы его построили, вы можете эффективно запросить определенную последовательность h-l, используя индекс.