262080486

2.2. Wyznaczenie iloczynu kartezjańskiego wszystkich tablic minimalnych pokryć M w programie PROTON

Wyznaczenie wszystkich zestawień wierszy z tablic pokryć M to kolejny mocno złożony obliczeniowo problem. Dzieje się tak ponieważ tablice pokryć M potrafią mieć setki wierszy, a należy sprawdzić wszystkie zestawienia tych wierszy. W wyniku badań algorytmu i eksperymentów zauważyłem, że dużo wyników się powtarza albo ma większe pokrycie. Obserwacje te umożliwiły mi opracowanie następującego algorytmu:

W kroku pierwszym tworzymy tablicę wyników pośrednich gdzie zapisujemy iloczyn kartezjański pierwszej i drugiej tabeli minimalnych pokryć M, następnie wyniki pośrednie są sprawdzane pod kątem powtórzeń albo większego pokrycia. Ta operacja powoduje nawet usunięcie ponad 99% danych, które są nadmiarowe. W następnym kroku tworzymy kolejną tablicę wyników pośrednich, która jest wypełniana wszystkimi zestawieniami wierszy z poprzedniej tablicy pośredniej i z kolejnej tabeli pokryć M. W momencie kiedy wszystkie tabele pokryć M są przetworzone w tabeli pośredniej otrzymujemy interesujący nas wynik w postaci listy wszystkich minimalnych atrybutów.

19