PROBLÉM SOUČTU PODMNOŽIN
ALGORITMUS ŘEŠENÍ "NA HRUBO"

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
Algoritmus řešení "na hrubo" (Greedy algorithm) zkoumá prvky vstupního pole a každý, který se ještě "vejde do batohu" je uznán jako prvek hledané podmnožiny. To je samozřejmě rychlé, časová složitost je O(N*lgN) vzhledem k doporučení vstupní hodnoty nejprve utřídit na nerostoucí posloupnost, a samozřejmě nepřesné. Martello a Toth pro vyjádření přesnosti přibližného řešení aloritmem A. definují číslo R.A takto: Nechť A. je aproximační algoritmus pro daný (maximalizační) problém. Pro konkrétní instanci I tohoto problému označme OPT.I optimální hodnotu řešení a A.I hodnotu nalezenou algoritmem A.; pak číslo R.A pro daný algoritmus A. je definováno jako největší reálné číslo R.A takové, že platí

(A.I/OPT.I)>=R.A pro všechny instance I

Číslo R pro algoritmus řešení "na hrubo" je rovno 1/2.

IMPLEMENTACE
Jednotka: vnitřní podprogram
 
Globální proměnné: pole A.1,...,A.N přirozených čísel, výstupní pole X.
 
Parametry: přirozené číslo N, přirozené číslo T
 
Vazby: D_QUICKSORT - třídění do nerostoucí posloupnosti
 
Výsledek: výstupní pole X., pro každé J=1,...,N platí: X.J=1, jestliže prvek A.J patří do hledané podmnožiny, X.J=0 jinak
 

GS: procedure expose A. X.
parse arg N, T
call D_QUICKSORT N
X. = 1
do J = 1 to N
  if A.J > T then X.J = 0; else T = T - A.J
end
return

 

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ě. 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
Martello S., Toth P. Knapsack Problems: Algorithms nad Computer Implementations
Chichester, John Wiley & sons 1990


Obálka Obsah Index Hlavní stránka

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