PROBLÉM SOUČTU PODMNOŽIN
APROXIMAČNÍ ALGORITMUS S POLYNOMIÁLNÍ ČASOVOU SLOŽITOSTÍ

PROBLÉM
Chceme najít podmnožinu množiny A.1,...,A.N, jejíž součet je největší možný, ale ne větší než T (T je tzv. velikost batohu).

ALGORITMUS
Je odvozen od Přesného řešení s exponenciální složitostí. Užijeme redukční parametr Delta, 0<Delta<1. Redukovat seznam L. pomocí Delta znamená vyjmout určité prvky z L. tak, že pro každý vyjmutý prvek Y existuje nějaký prvek Z<=Y v L. takový, že (Y-Z)/Y<=Delta. V redukovaném seznamu prvek Z reprezentuje chybějicí prvek Y. Podle Cormena, Leisersona a Rivesta jsou objeviteli funkce APPROX_SUBSET_SUM O. H. Ibarra a Ch. E. Kim.

IMPLEMENTACE
Jednotka: vnitřní funkce
 
Globální proměnné: pole A.1,...,A.N celých čísel, pole A. se nezmění
 
Parametry: přirozená čísla N a T, reálné číslo Epsilon (0<Epsilon<1)
 
Vrací: dobrou aproximaci největšího součtu <=T, označíme-li DA hodnotu aproximace, O hodnotu optimálního řešení, pak pro každou instanci problému součtu podmnožin platí (O-DA)/O<=Epsilon
 

APPROX_SUBSET_SUM: procedure expose A.
parse arg N, T, Epsilon
L.1 = 0; P = 1; Sentinel = 1E+100
do I = 1 to N while A.I <= T
  do J = 1 to P
    LP.J = L.J + A.I
    if LP.J > T then leave J
  end
  R = J - 1; K = 1; L = 1
  Pp1 = P + 1
  L.Pp1 = Sentinel
  LP.J = Sentinel
  do M = 1 to P + R
    if L.K < LP.L
      then do; M.M = L.K; K = K + 1; end
      else do; M.M = LP.L; L = L + 1; end
  end
  do J = 1 to P + R; L.J = M.J; end
  P = TRIM(P + R, Epsilon / N)
end
return L.P
 
TRIM: procedure expose M. L.
parse arg M, Delta
L.1 = M.1; Last = M.1; P = 1
do I = 2 to M
  if Last < (1 - Delta) * M.I
    then do
      P = P + 1; L.P = M.I; Last = M.I
    end
  end
return P

 

POROVNÁNÍ
Pro N=100;T=25557 a pole A. vytvořené příkazy:

Seed = RANDOM(1, 1, 481989)
do J = 1 to N
  A.J = RANDOM(1, 1000)
end

jsem porovnal algoritmy pro řešení problému součtu podmnožin a můj algoritmus DIOPHANT pro řešení Diofantovy rovnice.

Poznámky:
Provádění EXACT_SUBSET_SUM jsem násilně ukončil po půl hodině běhu. Pro běh APPROX_SUBSET_SUM jsem zvolil hodnotu Epsilon=0.5

 

Součet podmnožin - porovnání algoritmů
Algoritmus Suma prvků Sekund
GS 25554      0.05 
DPS 25557   240.24 
APPROX_SUBSET_SUM 25436    12.31 
DIOPHANT 25557      0.82 

 

SOUVISLOSTI

Literatura
Cormen T. H., Leiserson Ch. E., Rivest R. L. Introduction to Algorithms
The MIT Press, Cambridge, 1990


Obálka Obsah Index Hlavní stránka

změněno 8. srpna 2001
Copyright © 2000-2001 Vladimír Zábrodský, RNDr.