Wybór Aktywności

Wstęp

Wiele wydarzeń jednego dnia, wszystkie ciekawe i nie wiadomo na ile się zdąży? Wtedy przydatny jest algorytm Wyboru Aktywności, który podpowie, które wydarzenia wybrać, aby odwiedzić jak najwięcej wydarzeń.

Analiza problemu

Istnieje wiele różnych metod wybierania kolejnych wydarzeń z pewnego planu. Niestety nie każdy z nich znajduje prawie optymalne rozwiązanie, a często wybiera po prostu pewne wydarzenia z listy. Rozpatrzmy nastepujący plan:

Przyjmijmy, że każde wydarzenie jest równie interesujące, więc chcemy wybrać ich tak dużo jak to możliwe. Wyraźnie można zauważyć, że jest to możliwe tylko wybierając kolejno zdarzenia: A, B, C oraz D. Jednak nie każdy algorytm zwróci ten wynik. Poniżej zostało przedstawione porównanie.

Najbliższe wydarzenie

Mogłoby się wydawać, że należy wybierać każde kolejne wydarzenie, które najszybciej następuje po poprzednim. Faktycznie w ten sposób minimalizuje się czas oczekiwania na następne wydarzenie, ale nie zostaje znalezione optymalne rozwiązanie tak jak to zostało przedstawione poniżej:

Na początku zostało wybrane wydarzenie A, a potem E. Okazuje się to nienajlepszym pomysłem, ponieważ zdarzenie to wyklucza uczestniczenie w wydarzeniach B i C. Dalej wybierane jest zdarzenie F, ale nawet w przypadku jego pominięcia i wybrania D algorytm wybrał tylko trzy wydarzenia. Jest to dowód, że algorytm nie znalazł optymalnego rozwiązania.

Najkrótsze wydarzenie

Innym pomysł polega na wybieraniu najkrótszego wydarzenia. W teorii idea jest dobra, ponieważ im krótsze wydarzenia tym więcej można takich wydarzeń odwiedzić. Spróbujmy jednak zastosować to rozumowanie do podanego wcześniej przykładu:

Kolejno zostały wybrane zdarzenia: A, B oraz F. Okazuje się, że zdarzenie F eliminuje możliwość uczestniczenia w wydarzeniach C i D. Jak można zauważyć najkrótsze zdarzenie może nachodzić na dwa inne tym samym uniemożliwiając uczestniczenie w nich mimo, że jest to najlepsze rozwiązanie.

Zachłanne wybieranie

W celu rozwiązanie optymalnego rozwiązania należy posortować dane według czasu końcowego, a następnie wybierać kolejno te zdarzenia, które nie kolidują z poprzednimi. Wtedy zostaje odnalezione rozwiązanie wskazane na początku.

W celu przypatrzenia się tej metodzie wypiszmy w tabelce wydarzenia posortowane po czasie ich zakończenia:

Początkowo zostaje wybrane zdarzenie A oraz B. Kolejne zdarzenie na liście E nie jest brane pod uwagę, ponieważ koliduje ono z zdarzeniem B, które zostało już wybrane. Wydarzenie C zaczyna się zaraz po zdarzeniu B, więc zostaje ono dodane na listę w przeciwieństwie do zdarzenia F. Na sam koniec D też zostaje dodane na listę. Ostatecznie wybrane zostało 4 wydarzenia z 6 i zostało znalezione optymalne rozwiązanie.

Implementacja

Zadanie

Napisz program, który dla podanej listy wydarzeń wypisze najbardziej optymalne rozwiązanie przy pomocy algorytmu zachłannego. Należy przetestować działanie programu. Wydarzenie zostaje podane jako cztery liczby. Dwie pierwsze to godzina i minuta rozpoczęcia, a dwie kolejne to czas zakończenia. Przykładowo wydarzenie trwające od 10:00 do 11:30 zostanie wpisane jako:

1. 10 0 11 30

Rozwiązanie

Do przetrzymywania danych o wydarzeniu zostaje utworzona specjalna struktura, która może przechowywać czas rozpoczęcia oraz zakończenia:

1. struct wydarzenie {
2.   int start;
3.   int koniec;
4. };

Obydwa czasy są przetrzymywane jako ilość minut, która upłyneła od północy danego dnia. Z tego powodu została napisana funkcja naMinuty(), która konwertuje czas dany w postaci dwóch liczb tj. godziny oraz minuty na ilość minut.

1. int naMinuty() {
2.   int t1, t2;
3.   cin >> t1 >> t2;
4.   return t1 * 60 + t2;
5. }

Teraz można przejść do właściwej funkcji wybierzNajwiecej(). Akceptuje ona listę wydarzeń, a jej wynikiem są wszystkie wybrane wydarzenia przez algorytm.

1. vector<wydarzenie> wybierzNajwiecej(vector<wydarzenie> lista) {
2.   sort(lista.begin(), lista.end(), porownaj);
3.   int teraz = 0;
4.   vector<wydarzenie> wybrane;
5.   for (int i = 0; i < lista.size(); i++) {
6.     if (lista[i].start >= teraz) {
7.       teraz = lista[i].koniec;
8.       wybrane.push_back(lista[i]);
9.     }
10.   }
11.   return wybrane;
12. }

Na początku (2.) dane są sortowane i (3.) zostaje określone, że startujemy od początku danego dnia. (5.) Dla każdego zdarzenia: (6.) sprawdzamy czy może zostać wybrany tj. czy nie rozpoczyna się przed aktualnym teraz. Jeśli nie to (7.) wykonujemy zdarzenie i (8.) wydarzenie umieszczamy na liście.

Do sortowania listy została używa wbudowana funkcja do sortowania z własnym komparatorem. Oto jego definicja:

1. bool porownaj(const wydarzenie &l, const wydarzenie &r) {
2.   return l.koniec < r.koniec;
3. }

Testowanie funkcji

Oto kod, który wczyta od użytkownika ile jest wydarzeń, a następnie je wczyta. Jako wynik zostaną wypisane czasy wydarzeń wybranych przez program.

1. int main () {
2.   int n;
3.   cout << "Ile wydarzen?\n n = ";
4.   cin >> n;
5.   vector<wydarzenie> lista;
6.   for (int i = 0; i < n; i++) {
7.     wydarzenie wydarzenie;
8.     wydarzenie.start = naMinuty();
9.     wydarzenie.koniec = naMinuty();
10.     lista.push_back(wydarzenie);
11.   }
12.   vector<wydarzenie> wybrane = wybierzNajwiecej(lista);
13.   cout << "\nWybrano nastepujace wydarzenia:" << endl;
14.   for (int i = 0; i < wybrane.size(); i++) {
15.     naH(wybrane[i].start); cout << "\t";
16.     naH(wybrane[i].koniec); cout << endl;
17.   }
18.   system("pause");
19.   return 0;
20. }

Ze względu na to, że czas w strukturze to w rzeczywistości scalona godzina z minutami to funkcja naH() pozwala rozbić to na czytelny czas.

1. void naH(int v) {
2.   cout << (v / 60) << ":" << (v % 60);
3. }

Przykładowo dla danych:

1. 6
2. 8 0 9 0
3. 9 30 10 30
4. 10 30 12 30
5. 12 30 15 0
6. 9 0 11 30
7. 11 30 13 0

program wypisze na ekran:

1. 8:0     9:0
2. 9:30    10:30
3. 10:30   12:30
4. 12:30   15:0

• Kod źródłowy Implementacja