Problem maksimalne pokrivenosti

С Википедије, слободне енциклопедије

Problem maksimalne pokrivenosti je dobro poznat problem u polju informatike, teorije kompleksnosti i operacionom istraživanju. Kod ovog problema kao ulaz nam je dato nekoliko skupova i broj k. Skupovi mogu imati neke zajedničke elemente. Treba odabrati najviše k tih skupova, tako da je maksimalan broj elemenata pokriven, tj unija odabranih skupova ima maksimalnu veličinu.

Formalna, (beztežinska verzija)problema maksimalne pokrivenost je:

Ulaz: Broj k i kolekcija skupova S = S1, S2, ..., Sm.
Izlaz: Pronađen je podskup od skupova, takav da i da je broj pokrivenih elemenata maksimalan.

Problem maksimalne pokrivenosti je NP-težak, i ne može biti aproksimiran sa pod standardnim pretpostavkama. Ovaj rezultat u suštini odgovara složenosti dobijenoj pomoću generičkog pohlepnog algoritma.[1]

Formulacija ILP(енгл. integer linear problem)[уреди | уреди извор]

Problem maksimalne pokrivenosti može biti formulisan kao sledeći linearni program sa celim brojevima:

. (maksimalna suma pokrivenih elemenata).

 ; (ne više od k skupova je odabrano).

; (ako je onda je bar jedan skup je označen).

; (ako je onda je pokriven)

(ako je onda je odabran za prekrivenost).

Pohlepni algoritam[уреди | уреди извор]

Pohlepni algoritam za maksimalnu pokrivenost bira skupove vodeći se jednim pravilom: u svakom koraku, biramo skup sa najviše nepokrivenih elemenata. Može se pokazati da ovaj algoritam dostiže složenost od [2]. Rezultati pokazuju da je pohlepni algoritam, najbolji mogući algoritam, polinomijalne vremenske složenosti za problem maksimalne pokrivenosti[3].

Verzija sa težinama[уреди | уреди извор]

U verziji sa težinama svaki element ima težinu . Zadatak je naći maksimalnu pokrivenost koja ima i maksimalnu težinu. Specijalan slučaj je slučaj kad su sve težine 1.

. (maksimalna suma sa težinama pokrivenih elemenata).

; (ne više od k skupova je odabrano).

; (ako je onda je bar jedan skup odabran).

; (ako je onda je pokriven)

(ako je onda odabran za prekrivenost).

Pohlepni algoritam u verziji sa težinama pri problemu maksimalne pokrivenosti u svakom koraku bira skup koj sadrži maksimalnu težinu nepokrivenih elemenata. Ovaj algoritam postiže složenost .[1].

Maksimalna pokrivenost sa ograničenjem[уреди | уреди извор]

U maksimalnoj pokrivenosti sa ograničenjem, svaki element ima težinu , ali i svaki skup ima cenu . Umesto koje označava ograničenje broja skupova u pokrivenosti budžet je dat. Ovaj budžet ograničava težinu prekrivenosti koja može biti odabrana.

. (maksimalna suma sa težinama pokrivenih elemenata).

 ; (cena odabranih skupova koja ne može preći ).

; (ako je onda je bar jedan skup obabran).

; (ako je onda je pokriven)

(ako je onda je odabran za pokrivenost).

Pohlepan algoritam nam neće više dostavljati rešenje sa garantovanom dobrom preformansom. U najgorem mogućem slučaju izvođenje ovog algoritma može biti daleko od optimalnog rešenja. Algoritam aproksimacije proširujemo na sledeći način: Prvo, posle pronalaska rešenja koristeći pohlepni algoritam, vraća se najbolje od rešenja pohlepnog algoritma i skup najveće težine. Ovo možemo nazvati modifikovani pohlepni algoritam. Drugo, počev od svih mogućih familija skupova sa veličinama od 1 do bar 3, povećati rešenja uz pomoć modifikovanog pohlepnog algoritma. Treće, vrati najbolji od svih povećanih rešenja. Ovaj algoritam dostiže složenost . Ovo je najbolji moguća složenost, osim ako ().[4]

Generalizovana maksimalna pokrivenost[уреди | уреди извор]

U uopštenoj verziji problema maksimalne pokrivenosti svaki skup ima cenu , a element ima drukčiju težinu i cenu koja zavisi od skupa koj je pokriva. Ako je pokriven skupom težina je i njena cena je . Budžet je dat za cenu celokupnog rešenja.

. (maksimalna suma sa težinama pokrivenih elemenata u skupovima u kojima su pokriveni).

; (cena odabranih skupova ne može da pređe ).

; (element moži biti pokriven samo jednim skupom).

 ; (ako je onda je bar jedan skup odabran).

 ; (ako je onda je pokriven skupom )

(ako je onda je odabran za prekrivenost).

Algoritam[уреди | уреди извор]

Algoritam koristi koncept ostatka cene/težine. Ostatak cene/težine je meren sa privremenim rešenjem i to je razlika cene/težine od cene/težine dobijene u privremenom rešenju.

Algoritam ima nekoliko koraka. Prvo, pronaći rešenje korišćenjem pohlepnog algoritma. U svakoj iteraciji pohlepnog algoritma privremeno rešenje je dodato skupu koji sadrži maksimum ostatak težina elemenata, podeljenog sa ostatkom cena ovih elemenata, zajedno sa ostatkom cene skupa. Drugo, porediti rešenja dobijena u prvom koraku tako da se dobije najbolje rešenje od njih koje koristi mali broj skupova. Treće, vrati najbolji od proverenih rešenja. Ovaj algoritam dostiže složenost od .[5]

Povezani problemi[уреди | уреди извор]

Reference[уреди | уреди извор]

  1. ^ а б G. L. Nemhauser, L. A. Wolsey and M. L. Fisher. An analysis of approximations for maximizing submodular set functions I, Mathematical Programming 14 (1978), 265–294
  2. ^ Hochbaum, D. S. (1997), "Approximating covering and packing problems: Set cover, vertex cover, independent set, and related problems", in Approximation algorithms for NP-hard problems, PWS Publishing Company, Boston, 94-143.
  3. ^ Feige, U., "A threshold of ln n for approximating set cover", J. ACM 45, 634-652.
  4. ^ Khuller, S., Moss, A., and Naor, J. 1999. The budgeted maximum coverage problem. Inf. Process. Lett. 70, 1 (Apr. 1999), 39-45.
  5. ^ Cohen, R. and Katzir, L. 2008. The Generalized Maximum Coverage Problem. Inf. Process. Lett. 108, 1 (Sep. 2008), 15-22.