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
