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

Question

У меня есть набор I ={P1, P2, ..., Pm} и n конечных подмножеств I, обозначаемых через R1,R2,...,Rn следующим образом:

R1 = {P1, P2}

R2 = {P2, P4}

R3 = {P2, P3, P4}

R4 = {P1, P2, P4}

....

где Pi обозначает целое число.

Для каждого Ri я хочу вычислить произведение всех его элементов. Моя цель - как можно меньше использовать умножения и деления, разделяя некоторые общие части между Ri (i=1,2,...,n).

Например, если я могу сначала вычислить P2*P4, то этот результат можно использовать при вычислении произведения всех элементов для R3 и R4.

Обратите внимание, что разделение также допускается. Например, я могу сначала вычислить A=P1*P2*P3*P4, а затем использовать A/P1 для вычисления произведения всех элементов для R3 и использовать A/P3 для R4.

Если я хочу использовать минимальные умножения и деления для вычисления всех продуктов для каждого подмножества I, это проблема покрытия набора? NP-полный? Кстати, не могли бы вы дать линейную формулировку программы Integer, чтобы описать ее так же, как здесь.

Любые предложения будут высоко оценены!

Сообщество изменить: допущения дополнения:

• деления разрешены, такая же стоимость как умножения
• нет повторяющихся элементов в данном наборе. например R5 = {P1, P1, P1, P2} запрещено

Answer 1

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

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

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

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

Теперь, если вы используете только промежуточные результаты, вы можете использовать алгоритм Minimum Spanning Tree для решения этой проблемы. Я считаю, что алгоритмы 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 |)^2, может быть, в худшем случае, значительно увеличивая время, необходимое для поиска оптимального ответа.

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

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

Answer 2

Без делений это, по-видимому, эквивалентно проблеме АНСАМБЛЬНЫХ ВЫЧИСЛЕНИЙ, как описано в Gary & Johnson и, следовательно, NP-complete.

[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 соответствует A, каждый R_i соответствует элементу C, а умножение соответствует объединению множеств.

Answer 3

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

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

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

Например, если вы вычисляете 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

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

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