минимальное умножение против проблемы с набором покрытия

Рассмотрим граф ваших элементов R_i без ребер. Теперь мы позволяем себе добавлять ребра следующим образом:

• Добавьте направленное ребро между R_a→R_b, аннотированное частным R_b/R_a.

Например, мы можем нарисовать ребро R₁→R₃ со стоимостью умножения на R₁/R_{3< /sub> = P3*P4/P1}

Сделайте это для всех узлов, чтобы у вас было |R|² ребер.

Теперь, если вы только использовали промежуточные результаты, вы могли бы использовать алгоритм минимального связующего дерева для решения этой проблемы. Я считаю, что алгоритмы MST очень близки к линейным по количеству ребер (фактор обратного Аккермана растет медленнее, чем log(log(log(...log(n)...)))); могут быть даже рандомизированные алгоритмы линейного времени по количеству ребер, например. http://www.akira.ruc.dk/~keld/teaching/algoritmedesign_f04/Artikler/07/Karger95.pdf Таким образом, этот базовый алгоритм займет |R|² времени.

Однако вы лишите себя действительно оптимальных ответов, если будете использовать только промежуточные результаты, потому что можно использовать «импровизированные» выражения, которые мы извлекаем из воздуха для достижения лучшей производительности. Например, вы можете рассмотреть такой сценарий:

R1 = {P2, P3, P4, P5}
R2 = {P1, P3, P4, P5}
R3 = {P1, P2, P4, P5}
R4 = {P1, P2, P3, P5}
R5 = {P1, P2, P3, P4}

Оптимальное решение — вычислить P1*P2*P3*P4*P5, а затем разделить на P_i, в результате чего получится 9 операций. Принимая во внимание, что описанный выше метод будет делать что-то вроде R1=P2*P3*P4*P5, а затем выполнять умножение и деление каждый раз, чтобы перейти R1→R2, R2→R3, R3→R4, R4→R5, в результате чего получается 11 операций. (Если бы у нас не было деления, у нас было бы тоже 9 операций: b=P1*P2 c=b*P3 r5=c*P4 r4=c*P5, d=P4*P5, r3=b*d, e= P3*d, r1=e*P2, r2=e*P1.Хотя я думаю, что можно было бы создать ситуации, когда деление было бы необходимо, но, похоже, не могу найти его; если я не могу его найти, возможно, дело в том, что на самом деле это простая задача с полиномиальным временем.)

Этот метод я буду называть методом «экспромтного выражения». Если мы решим вычислить импровизированное выражение (одну невозвратную стоимость в начале), это уменьшит затраты на все будущие вычисления для прохождения ребра, если мы решим его использовать (поскольку может возникнуть выбор количества импровизированных выражений для использования).

Это подводит нас к очень незначительному побочному примечанию:

Theorem:
  You should have at least one intermediate expression of each 
  length up to the maximum size of any R.
Proof (induction):
  To build up a product of size N, you will need to do 
  have a product of size N-1.

Учитывая эту теорему, оказывается, что мы немного ошиблись выше. Оптимальным решением было запомнить P1*P2*P3 и P1*P2*P3*P4 в процессе вычисления P1*P2*P3*P4*P5. Тогда мы можем получить R5 бесплатно (и R4 всего одним умножением другим способом, к сожалению, по той же цене, что и раньше), уменьшив общую стоимость с 9 до 8. Это приводит нас к дикому предположению, что выполнение http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm с произвольным ребра также могут дать оптимальное решение после очень долгого времени.

В любом случае, как нам включить такую ​​систему в наше решение? Мы не можем добавить узел, потому что это испортит алгоритм MST. Для каждого ребра, где умножение или деление на импровизированное выражение E не приведет к тому, что некоторое P будет иметь мощность, превышающую p (например, для p = 2 мы разрешаем промежуточные импровизированные выражения, которые создают продукты, такие как P1 * P4^2 / P3, но запрещают что-то вроде P2^3), мы выполняем это умножение и разделение на краю, и создайте два новых края. (Мы можем сделать это несколько раз или в будущем.) Мы также делаем это для всех подмножеств ребра, которые мы запоминаем, как описано выше. Стоимость этого метода, если вы используете алгоритм MST, заключается в том, что количество ребер сильно увеличивается, поэтому, возможно, (|R| + #newedges)² = (|R|^|P|) ² может быть, в худшем случае, значительно увеличивая время, необходимое для поиска оптимального ответа.

Таким образом, кажется, что более общая проблема является NP-сложной, как предположение; отзовитесь кто-нибудь, если это не так. Однако вы, возможно, можете использовать эвристику для угадывания полезных импровизированных выражений. Например, если вы видите «большое» подмножество R с «высокой плотностью обычных P», вы можете сгенерировать «уловку», которая является произведением всех общих P. Если вы сделаете это для всех «больших/плотных скоплений обычных P», которые вы видите среди подмножеств ваших R, а затем запустите MST, вы можете получить несколько лучшие ответы без необходимости выполнять более общий поиск. Вы даже можете запустить алгоритм, помогающий обнаруживать такие сгустки, например, алгоритм иерархической кластеризации.

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

Без делений это похоже на задачу ВЫЧИСЛЕНИЕ АНСАМБЛА, как описано в Gary & Johnson и, следовательно, NP-полный.

[PO9] АНСАМБЕЛЬНЫЕ ВЫЧИСЛЕНИЯ

INSTANCE: Набор C подмножеств конечного множества A, положительное целое число J.

ВОПРОС: Существует ли последовательность S = (z_1 ‹- x_1 U y_1, z_2 ‹- x_2 U y_2, ..., z_j ‹- x_j U y_j) операций объединения j ‹= J, где каждый x_i и y_i либо { a} для некоторого a в A или z_k для некоторого k ‹ i, такого, что x_i и y_i не пересекаются, 1 ‹= i ‹= j, и такого, что для каждого подмножества c в C существует некоторое z_i, 1 ‹= i ‹ = j, что идентично C.

Ваш набор I соответствует A, каждый R_i соответствует элементу C, а умножение соответствует объединению множеств.

Во-первых, вам не нужно разделение

Деление здесь не нужно, это всегда будет лишний расчет.

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

Например, если вы вычисляете Pi*Pj*Pk путем деления Pi*Pj*Pk*Pn на Pn, это означает, что вы рассчитали Pi*Pj*Pk*Pn раньше и, следовательно, рассчитали Pi*Pj*Pk раньше.

(Я предполагаю, что все ваши числа являются простыми числами)

мое решение

У меня есть идея, которая не учитывает возможность деления.

Вы можете начать строить дерево суффиксов с помощью Ri .

Тогда число умножения будет числом ребер в дереве.

Пример:

Используя ваш пример, дерево суффиксов будет:

       P2
      / \
     P4 P1
    / \ 
   P3 P1

Вы получаете 4 умножения:

M1=P1*P2

M2=P2*P4

M3=M2*P1

M4=M2*P3

Нахождение минимального числа умножений эквивалентно построению суффиксного дерева с минимальным количеством ребер.

Надеюсь, это поможет.