Geek asks and answers

Minimal multiplication compared to cover typing issue

I have the set i = {P1, P2, ..., Pm} and n finite subsets of I, denoted by R1, R2, ..., Rn as follows:

R1 = {P1, P2}

R2 = {P2, P4}

R3 = {P2, P3, P4}

R4 = {P1, P2, P4}

....

where Pi is an integer.

For each Ri, we need to calculate the product of all its elements. My goal is to use multicases and divisions as little as possible, sharing some common parts between Ri (i = 1,2, ..., n).

For example, if I can first calculate P2 * P4, then this result can be used to calculate the product of all the elements for R3 and R4.

Please note that sharing is also allowed. For example, I can first calculate A = P1 * P2 * P3 * P4, then use A / P1 to calculate the product of all the elements for R3 and use A / P3 for R4.

If I want to use minimal multiplications and divisions to calculate all the products for each subset I, is this a coverage set problem? NP-complete? By the way, could you give the wording of the linear Integer program to describe it as here .

Any suggestions would be much appreciated!

community change: suggestions to add:

  • Allowed, same costs, such as multiplication
  • There are no duplicate elements in the given set. for example R5 = {P1, P1, P1, P2}prohibited
+5
source share
3

R i, . :

  • R a → R b, R b/R a.

, R 1 → R 3, R 1/R 3= P3 * P4/P1

, R | 2.

, , , . , MST ( , log(log(log(...log(n)...)))); , . http://www.akira.ruc.dk/~keld/teaching/algoritmedesign_f04/Artikler/07/Karger95.pdf , | R | 2.

, , "" , , . , :

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 .

, ​​ ? node, MST. , E , P p (, p = 2 , , P1 * P4^2 / P3, - P2^3), . ( .) , , . , MST, , , (| R | + #newedges) 2= (| R | ^ | P |) 2 , , .

, NP-hard, ; , - , . . , "" R " Ps", -, Ps. "/ Ps", R, MST, , . , .

(sidenote: , , .)

+1

-,

, .

, , , , , , .

, 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

.

, .

+1

ENSEMBLE COMPUTATION, Gary and Johnson , , NP-complete.

[PO9] ENSEMBLE COMPUTATION

INSTANCE: C A, J.

QUESTION: Is there a sequence S = (z_1 <-x_1 U y_1, z_2 <-x_2 U y_2, ..., z_j <-x_j U y_j) j <= J where each x_i and y_i or {a} for some a from A or z_k for some k <i such that x_i and y_i do not intersect, 1 <= i <= j and such that for any subset c in C there is some z_i, 1 <= i <= j, which is identical to C .

Your set i corresponds to A, each R_i corresponds to the element C, and multiplication corresponds to the union set.

+1
source

More articles:


All Articles