Subset Sum Problem


Subset sum problem ili problem sume podskupa definiše se nad skupom cijelih brojeva, iz kojeg je potrebno naći podskup čija suma elemenata iznosi određenu vrijednost.

Problem se može poopćiti na sljedeći jednostavan primjer:

Pretpostavimo da imamo skup S = \{{ 1,2,3,4,5,6 \}}. Potrebno je prebrojati koliko ima podskupava datog skupa čiji zbir elemenata iznosi npr. 7.

Prejednostavan problem, čak se i napamet se može izračunati, bez olovke i papira, a implementacija u nekom programskom jeziku je prejednostavna. Međutim, u koliko se radi o skupu koji ima veći broj elemenata, i ako se radi o vrijednosti sume takodjer velikom broju, tada nastupa problem, jer se klasično ne može riješiti. Problem je poznat po imenu Subset-Sum problem ili Problem Sume Podskupa. Ovo je pojednostavljena verzija Knapsack problema.

SUBSET-SUM = (S,t): postoji podskup S^{'} \subseteq S za koji vrijedi t = \sum_{S \in S^{'}}S

SUBSET-SUM problem: Pretpostavimo da imamo skup S = \{{ x_{1},x_{2},...,x_{N} \}}, od N članova koji predstavljaju cijele brojeve i t cijeli broj.

  1. Decision problem (problem odluke) postavlja pitanje da li postoji podskup S^{'} čija suma članova iznosi t.
  2. Optimization problem (optimizacijski problem) postavlja pitanje koliko ima podskupova S^{'} čija suma članova iznosi t.

Problem koji smo definisali tretira se kao NP problem. Više o NP može se pogledati na datom linku. Koliko je kompleksan ovaj problem zavisi od N i t, a shodno njima se i implementiraju algoritmi za rješavanje.

Matematička analiza problema

Kako je broj elemenata skupa S jednak broju N , to možemo zaključiti da ukupan broj svih podskupova S^{'} koji se mogu definisati iz datog skupa je sljedeći:

C_{N}^{1}+C_{N}^{2}+...+C_{N}^{N}

Vidimo da su podskupovi skupa S, kombinacije bez ponavljanja klasa 1 do N. Zbir ovih kombinacija iznosi:

\sum_{sk=0}^{N}\binom{N}{k}=(1+1)^{N}=2^{N}

Svaki podskup sadrži 0,1,2,3,....,3,2,1 elemenata shodno razvoju Binomnog obrazca iz gornjeg izraza.

Kompleksnost problema

Obični postupak rješavanja ovih problema je “brute-force”, koji generira sve kombinacije podskupova, kojih ima 2^{N}, a generirane podskupove sada je potrebno provjeriti da li zadovoljavaju (ne)jednakost, što čini još dodatnih N operacija. S toga ovaj problem ima kompleksnost odnosno vrijeme izvršavanje O(2^{N}N). Ovo spada u grupu eksponencijalnih vremena izvršavanja. Neki pristupi rješavanja svode kompleksnos na O(2^{N/2}N), djeleći skup na dva podskupa.

Algoritam

Za specifične vrijednosti N i t, problem je moguće svesti na pseudo-polinomalni, koji se rješava dinamičkim programiranjem.

Algoritam dinamičkog programiranja za problem odluke:

Pretpostavimo da imamo polje: x_{1} ,x_{2} ,..., x_{N}. Potrebno je provjeriti da li postoji nepazan podskup čija suma iznosi 0. Neka je N suma negativnih članova polja, a P suma pozitivnih članova polja. Definišimo boolovu funkciju Q(i,s) na način: “postoji neprazan podskup od  x_{1} ,x_{2} ,..., x_{i} čija suma elemenata iznosi s“.

Rješenje problema je vrijednost Q(n,0).

  1. Q(i,s)=false, ako je s<N \vee s>P, s toga ove vrijednosti netrebaju da budu čuvane tokom izvršavanja.
  2. Formirati polje za čuvanje vrijednosti Q(i,s) za 1\leq i\leq n \wedge N\leq s\leq P.
  3. Ova kolekcija se popunjava sljedećom rekurzijom
    1. Inicijalizirati N\leq s\leq P
    2. Postaviti početnu vrijednost funkcije Q(1,s)=(x1=s)
    3. Za i=2 ,...., n
    4. Postaviti Q(i,s)=Q(i-1,s) ili (x_{i}=s) ili Q(i-1,s-x_{i}), za N\leq s\leq P.

Za svaki Q(i,s) vrijednost na desnoj strani je poznata, jer je izračunata iz prethodnih iteracija ili zbog Q(i-1,s-x_{i})=false ako je s-x_{i}>P.

Algoritam optimizacijskog problema

Optimizacijski problem je sličan gore prezentiranom problemu, samo umjesto definisanja boolove funkcije Q(i,s), definišemo funkciju Q(i,s), koja vraća broj podskupova, čija suma elemenata iznosi s.

Rješenje optimizacijskog problema je vrijednost Q(n,0).

Primjena Subset Sum problema

U nekoliko narednih primjera biće demonstrirano korištenje prethodnih definicija i algoritma dinamičkog programiranja:

Problem 1. Koliko se može napraviti podskupova skupa S=\{{1,2,3,4,5,6\}}, čija je suma t=7.

Problem je vrlo jednostavan jer želimo vidjeti na koji način algoritam radi. Prvo, rješimo ovaj problem „pješice“ i pogledajmo koliko takvih posdkupova ima. To su:

S^{'}_{1}= \{{ 6,1 \}}, S^{'}_{2}= \{{ 5,2 \}}, S^{'}_{3}= \{{4,3 \}}, S^{'}_{4}= \{{1,2,4 \}}.

Vidimo da ukupno postoji 4 takva podskupa.Napišimo implementaciju ovog problema shodno gore prezentiranom algoritmu.

static void Main(string[] args)
{
    Console.Title = "Subset Sum Problem...";
    //Inicijalizacija skupa S i vrijednosti t
    int[] S = new int[6] { 1, 2, 3, 4, 5, 6 };
    int t = 7;

    //polje za čuvanje vrijednosti Q(s)
    int[] Q=new int[t+1];
    //Pocetna vrijednost
    Q[0]=1;
    //Iteracija od 0-N
    for (int i = 0; i < S.Length; i++)
    {
        int s=S[i];
        //Iteracija od t-si
        for (int j = t; j >= s; j--)
            Q[j] += Q[j - s];
    }
    Console.WriteLine("Postoji {1} podskupa čija je suma>={0}",t,Q.Sum()-1);
    Console.Read();
}

Izlaz na konzolu je sljedeći:

Linija 18 čini čaroliju kod ove implementacije. Važno je naglasiti da iteracija kod druge petlje mora ići u silaznom smijeru od t do s_{i} . U koliko bi išla u suprotnom smjeru tada bi ova implementacija imala sasvim drugi smisao kojem će biti riječi možda neki drugi put.
Gornjom implementacijom ne samo da smo prebrojali koliko postoji podskupova čija je suma 7, nego smo prebrojali i sve podskupove čija je suma manja ili jednaka 7. Kako smo kazali kroz definiciju algoritma da je vrijednost Q[n,t] broj podskupova čija je suma iznosi s, to znači da je Q(N,t-1) rješenje za problem t-1, i td. Sve do praznog skupa onosno 0. Ovim se želi kazati da algoritam rješava problem sume manje ili jednake od t.
U koliko bi, shodno prethodnom (nemjenjajući logiku gornje implementacije) željeli znati koliko ima podskupova čija je vrijednost manja ili jednaka 7, potrebno je samo promjeniti liniju 20, i to na sljedeći način:
Console.WriteLine("Postoji {1} podskupa čija je suma>={0}",t,Q.Sum()-1);

Od sume oduzimamo jedinicu jer želimo izbaciti prazan skup odnosno m[0].
Na jednostavnom problemu prikazan je Subset sum problem, koji je vrlo koristan kod rješavanja složenijih problema. Jedan od primjene ovog problema je u Euler Problem 249 i 250, koji se mogu riješiti primjenjujući upravo ovaj način implementacije. U nekom od narednih postova biće prikazana rješenja ovih problema.
References:

About Bahrudin Hrnjica

PhD in Mechanical Engineering, Microsoft MVP for .NET. Likes .NET, Math, Mechanical Engineering, Evolutionary Algorithms, Blogging.

Posted on 23/03/2010, in C#, Programiranje, Project Euler and tagged , . Bookmark the permalink. Leave a comment.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s