Geek asks and answers

Algorithm / Data Structure for Finding Minimum Value Combinations Easily

I have a symmetric matrix as shown in the figure below.

Example matrix

I made up the designation AB , which represents the value at the grid point (A, B). In addition, writing ABC gives me the minimum value of the grid point: MIN ((A, B), (A, C), (B, C)).

As another example, ABD gives me MIN ((A, B), (A, D), (B, D)).

My goal is to find the minimum values ​​for ALL letter combinations (not repeating) for one line at a time, for example, for this example I need to find the minimum values ​​on line A, which are given by calculations:

AB = 6
AC = 8
AD = 4
ABC = MIN (6,8,6) = 6
ABD = MIN (6, 4, 4) = 4
ACD = MIN (8, 4, 2) = 2
ABCD = MIN (6 , 8, 4, 6, 4, 2) = 2

I understand that some calculations can be reused, which is becoming increasingly important as the size of the matrix increases, but the problem is finding the most efficient way to implement this reuse.

Can you point me in the right direction to find an efficient algorithm / data structure that I can use for this problem?

+3
source share
2 answers

, . , f (S), S 2 (.. - , , ), , T f (S) S 2, T. ( T, "A" , - .)

, , n , Omega (2 ^ n), . ( , , "A" , n + 1 , , big Omega.) , n, . n , , ; , , , , , , , .

, , , . " ", , ( ), , .. , S, f (S), f (T) T, S. , , S: t1 t2 - T, , ; S - T, , t1 t2. S1 S t1 S2 S + t2. , T, S1, S2, {t1, t2}. f (S1) f (S2) , f ({t1, t2}) f (T) = .

"A" t1 t2, , , f T, "A" . ( , , T .) ! - f (T). 2 ^ (n-1); , : "A" (n-1) , i- 1 , (i + 1) - ( 0010110, 2, 4 5, { "A" , "C", "D", "F" } "A" .. "H" - . 0 , "A" = 0). , , k- n-. ( , 0 1 , 2 , .)

+1

, , , , . :

  • let P - X1.X2. ... .Xn, Xi -

  • CS = [ (X1, X2), (X1, X3), ... (X1, Xn) ], X1 ; CS n-1 , O (n)

  • min (CS), .. , CS; O (n)

  • .

: , P, CS, P : (X1, Xi) (Xi, X1)

, P:

  • P = X1.X2.X3, , X1.X2.X3 -

  • , P' = X1.X2.X3.X7.X9.X10.X11, P' : , P' (Xi) , ,

  • P' , , , , : X1.X2.X3, X1.X7.X9.X10.X11, min ( P')

  • , P' ( , )

memoization.

+1

More articles:


All Articles