DSC00283 (6)

POKRYCIA MINIMALNE ZBIORU

Sformułowanie problemu:

Mąjąc pewien skończony zbiór W i ustalony zbiór podzbiorów W% tego zbioru (k ^m 1,2^..,K) spełniające warunek    Wu ^m W, należy wybrać

nąjmnfejszą liczbę tych podzbiorów w ten sposób, aby w sumie tworzyły one cały zbiór W,

Przykład:

Wybór nąjmniejszej liczby specjalistów o ustalonych zbiorach specjalizacji Wu do wykonania określonej pracy wymagającej w sumie zbioru W różnych specjalizacji.

Definicja pokrycia zbioru;

Mówimy, że pewien r - ty podzbiór {W_rJ    zbiorów Wk tworzy

pokrycie zbioru W wtedy l tylko wtedy, gdy    W

Pokrycia minimalne - gdy żaden podzbiór właściwy zbiorów pokrywających nie stanowi pokrycia.

Pokrycie najmniej liczne - pokrycie zawierające najmniejszą liczbę podzbiorów 0p

ALGORYTM WYZNACZANIA POKRYCIA MINIMALNEGO ZBIORU:

1.    Zapisujemy zbiór W i podzbiory Wk w postaci macierzy B

B-fbyJudc, J»* jFff* * " W A gdzie by ^m 1 gdy element w_t należy do Wt by^m0 w przeciwnym przypadku

2.    Wypisujemy formułę ftmkcji według wzoru:

* A

f(S) ^mJT% by Vj S-f

3.    Przekształcamy formułę ftmkcji f(v) do postaci mfa, nieredukowalnej sumy iloczynów boolowskich.

4.    Iloczyny mfa określają minimalne pokrycia tworzone przez podzbiory Wk odpowiadające zmiennym v* występującym w odnośnych iloczynach. Iloczyn o nąjmniejszej liczbie zmiennych określa pokrycie najmniej liczne.