Problem kinomana

Igor Bodnar, Dominika Borecka oraz Igor Mariak3bp

KINOMANA

Problem

Wiele problemów rozwiązywanych metodami komputerowymi to problemy optymalizacji. Przykładem jest modelowanie jak najbardziej opływowego kształtu samochodu czy ustalanie jak najszybszej trasy przejazdu dla kuriera z przesyłkami. Z optymalizacją spotykasz się także w życiu codziennym, np. gdy w sklepie otrzymujesz resztę wydaną najmniejszą możliwą liczbą monet. Kasjer stosuje wtedy tzw. podejście zachłanne.

Podejście zachłanne w rozwiązywaniu problemów

Algorytm zachłanny

to algorytm, który w celu wyznaczenia rozwiązania w każdym kroku dokonuje zachłannego, tj. najlepiej rokującego w danym momencie wyboru rozwiązania częściowego. Innymi słowy algorytm zachłanny nie dokonuje oceny czy w kolejnych krokach jest sens wykonywać dane działanie, dokonuje decyzji lokalnie optymalnej, dokonuje on wyboru wydającego się w danej chwili najlepszym, kontynuując rozwiązanie podproblemu wynikającego z podjętej decyzji.

Wyobraź sobie, że jesteś na jednodniowym festiwalu filmowym. Posiadasz program festiwalu, w którym możesz znaleźć informacje takie jak: tytuł filmu, gatunek filmu, godzina rozpoczęcia seansu, czas projekcji, numer sali kinowej. Chce zobaczyć tyle filmów, ile tylko będzie możliwe - kochasz oglądać filmy. Oczywiście musisz zakłożyć, że nie możesz w tej samej godzinie zakończyć seansu jednego filmu i rozpocząć drugiego. Potrzebujesz czasu na przemieszczenie się, a filmy oglądasz w całości. Nasuwa się wtedy pytanie: "W jaki sposób powiniem postępować, aby obejrzeć ich jak najwięcej?"Tak sformułowany problem znany jest w literaturze jako problem kinomana.

Problem kinomana

Aby wybrać możliwie najwięcej filmów, możemy postępować według różnych kryteriów, np.;

• kryterium 1: filmy zaczynające się najwcześniej,
• kryterium 2: filmy najkrótsze,
• kryterium 3: filmy kończące się najwcześniej.

Harmonogram festiwalu można przedstawić graficznie. Filmy są reprezentowane przez prostokąty ułożone chronologicznie wzdłuż linii czasu. Długość prostokąta odpowiada długości trwania filmu. Dodatkowo każdy film ma identyfikator od F1 do F22.

Filmy zaczynające się najwcześniej

Rysunek przedstawia rozwiązanie z uwzględnieniem kryterium 1. W pierwszej kolejności wybieramy najwcześniej rozpoczynający się film (F1). Następnie szukamy filmu, który rozpocznie się najwcześniej po zakończeniu pierwszego seansu – będzie to film F7. Po jego zakończeniu najwcześniej rozpocznie się film F16, a ostatnim wybranym filmem jest F22.

Można Zauważyć, że zachłanny wybór najwcześniej kończących się filmów (kryterium 3) daje zawsze rozwiązanie optymalne.

KRYTERIUM 3

KRYTERIUM 2

filmy kończące się najwcześniej

filmy najkrótsze

Aby wyłonić listę filmów, korzystając z metody zachłannej, wystarczy posortować filmy według godziny ich zakończenia, a następnie wybrać pierwszy z tych filmów i wielokrotnie (w pętli) powtórzyć ten sam sposób wyboru dla listy filmów, które rozpoczynają się po zakończeniu poprzedniego filmu.

Dane: liczba naturalna N – liczba filmów; trzy tablice N-elementowe liczb całkowitych:P – z godzinami rozpoczęcia projekcji kolejnych filmów, K – z godzinami zakończenia projekcji kolejnych filmów, ID – z identyfikatorami kolejnych filmów. Wynik: identyfikatory i godziny rozpoczęcia filmów tworzącychoptymalne rozwiązanie.

Specyfikacja problemu

Lista kroków rozwiązania problemu kinomana

1 Wczytaj dane do tablic P, K oraz ID. 2 Uporządkuj tablicę K niemalejąco i dostosuj kolejność elementów w tablicach P oraz ID.3 Wypisz na ekranie ID[0], P[0] oraz K[0]. Wartość K[0] zapisz w zmiennej koniec_poprzedniego.4 Oznacz jako i zmienną wskazującą komórkę tablicy i ustaw ją na 1. 5 Dla wartości i równych kolejno 1, 2, …, N-1 powtarzaj kroki elementów w pozostałych tablicach 6 – 8 .6 Jeśli P[i]>koniec_poprzedniego, to wykonaj kroki 7 – 8 . 7 Wypisz na ekranie ID[i], P[i] oraz K[i]. 8 Zapisz wartość K[i] w zmiennej koniec_poprzedniego.

1. Kod źródłowy funckji Sortuj Choć warunek pętli while (linia13) odnosi się tylko do tablicy koniec, to równolegle modyfikowane są pozostałe tablice początek i id. Pierwszy warunek pętli while sprawdza, czy indeks jest liczbą mniejszą od rozmiaru tablicy, a drugi warunek sprawdza, czy w tablicy są jeszcze filmy do uporządkowania. Te same identyfikatory w trzech tablicach odnoszą się do tego samego filmu -tablice równoległe.

2. Kod źródłowy funckji Wypisz oraz Wybierz Funkcja Wypisz pozwala wypisać informacje: indentyfikator, godzina rozpoczęcia i zakończenia seansu. Kod funkcji Wybierz znajduje się w liniach 8-21. W lini 12 wypisujemy na ekranie dane filmu o indeksie 0. Następnie wybierane są filmy, które rozpoczną się bezpośrednio po aktualnie wybranym (linia 16) i mają najwcześniejszą godzinę zakończenia.

3. Kod źródłowy funckji głównej Dobra radaJeśli w pętli wykonywana jest tylko jedna instrukacja (np. instrukacja wywoływania funckji), to można pominąć nawiasy klamrowe. Należy pamiętać, by postawić średnik po instrukcji.

kod źródłowy

Problem kinomana

Dziękujemy za uwagę!