SET COVER PROBLEM

Set cover problem is an example of a mathematic optimization problem.

(More about the problem: en.wikipedia.org/wiki/Set_cover_problem)

The program allows to solve this problem using one of these three methods:

1. Exact algorithm
2. Naive heuristics
3. Greedy heuristics

Some detailed information about the program in Polish can be found below.

POKRYCIE ZBIORU

Pokrycie zbioru to przykład problemu optymalizacyjnego.

(Więcej na temat pokrycia zbioru: pl.wikipedia.org/wiki/Pokrycie_zbioru)

Program umożliwa rozwiązanie tego problemu trzema sposobami:

1. Poprzez algorytm dokładny
2. Poprzez heurystykę naiwną
3. Poprzez heurystykę zachłanną.

OPIS PROGRAMU

Pokrycie zbioru to przykład problemu optymalizacyjnego.

Instancją problemu jest zbiór Z i rodzina zbiorów R, numerowanych kolejnymi liczbami całkowitymi od 1.

Rozwiązaniem problemu jest pokrycie zbioru Z rodziną R, czyli wybór z rodziny R jak najmniejszej liczby zbiorów tak, by ich suma teoriomnogościowa była nadzbiorem zbioru Z.

Reprezentacją rozwiązania jest, uporządkowany rosnąco, ciąg numerów wybranych zbiorów.

Algorytm dokladny

Znalezienie rozwiązania optymalnego, czyli takiego, którego reprezentacja jest najkrótsza, wymaga zastosowania kosztownego algorytmu siłowego, opartego na metodzie prób i błędów.

Algorytm daje to spośród rozwiązań optymalnych, którego reprezentacja jest pierwsza w porządku leksykograficznym .

Heurystyka naiwna

Rozważa zbiory rodziny R w kolejności rosnących numerów. Wybiera aktualny zbiór jeśli należy do niego jakiś element zbioru Z, który nie należy do żadnego z dotąd wybranych zbiorów.

Heurystyka zachłanna

W kolejnych krokach wybiera z rodziny R zbiór, w którym jest największa liczba elementów zbioru Z nie należących do żadnego z dotąd wybranych zbiorów. Jeśli warunek ten spełnia wiele zbiorów, to wybierany jest spośród nich zbiór o najmniejszym numerze.

##Dane Na standardowym wejściu programu jest ciąg wierszy ze spacjami i liczbami całkowitymi zapisanymi dziesiętnie.

Spacje i końce wiersza nie są znaczące. Dane programu to ciąg liczb całkowitych.

Składnię danych określa poniższa gramatyka bezkontekstowa, w rozszerzonej notacji BNF , z symbolem początkowym Dane:

Dane ::= { Zbiór | Zapytanie }
Zbiór ::= { Składnik } 0
Składnik ::= Element | Nieskończony | Skończony
Element ::= d
Nieskończony ::= d u
Skończony ::= d u u
Zapytanie ::= u d

W gramatyce nawiasy klamrowe oznaczają powtórzenie zero lub więcej razy a kreska pionowa oznacza alternatywę.

d reprezentuje dodatnią, czyli większą od zera, liczbę całkowitą.

u reprezentuje ujemną liczbę całkowitą.

d po prawej stronie produkcji symbolu Zapytanie reprezentował liczbę 1, 2 lub 3.

Ciąg liczb wyprowadzalny z symbolu Zbiór określa element rodziny zbiorów R.

Zbiory rodziny R są numerowane w kolejności wystąpienia w danych.

Zawartość zbioru jest sumą składników w jednej z poniższych postaci:

a

jedynym elementem składnika jest liczba a,

a b

składnik zawiera wszystkie wyrazy nieskończonego ciągu arytmetycznego, zaczynającego się od a, w którym każdy kolejny wyraz jest większy od poprzedniego o -b,

a b c

składnik zawiera wszystkie, nie przekraczające -c, wyrazy ciągu arytmetycznego, zaczynającego się od a, w którym każdy kolejny wyraz jest większy od poprzedniego o -b.

Para liczb a b, wyprowadzalna z symbolu Zapytanie, określa instancję problemu pokrycia zbioru i sposób rozwiązania.

Instancją problemu jest zbiór Z zawierający wszystkie liczby całkowite od 1 do -a i rodzina R wszystkich zbiorów, wyprowadzalnych z symbolu Zbiór, które wystąpiły w danych przed tym zapytaniem.

Liczba b wskazuje sposób rozwiązania problemu:

3 heurystyka naiwna,

2 heurystyka zachłanna,

1 algorytm dokładny.

##Wynik Program pisze na standardowe wyjście wynik w postaci ciągu wierszy, po jednym dla każdego zapytania.

W wierszu wyniku są spacje oraz zapisane dziesiętnie liczby całkowite.

Między każdą parą liczb sąsiadujących w wierszu jest dokładnie jedna spacja.

Nie ma spacji ani na początku ani na końcu wiersza.

Każdy wiersz jest zakończony reprezentacją końca wiersza.

Jeśli problem, którego dotyczy zapytanie, ma rozwiązanie, to w wierszu jest reprezentacja rozwiązania, w przeciwnym przypadku jest tam liczba 0.

###Przykład Dla danych z pliku przykład.in :

2 0

   1      0 1

0 -3
1
0
2 3 2 0
-3 3
-3 2
-3 1
4 -1 -5 1000000000 0
2 -2 0
-6 3
-6 2
-6 1
1 6 0
-6 3
-6 2
-6 1

wynikiem jest zawartość pliku przykład.out :

0
1 2 5
2 5
2 5
1 2 5 6 7
2 5 6 7
2 5 6 7
1 2 5 6 7
2 5 6 7
5 6 8

##Uwagi Zakładamy, że dane są poprawne.

Zakładamy, że wszystkie dane liczby mieszczą się w zakresie typu int.