Wrocław, 20.01.2011r.

Projektowanie efektywnych algorytmów

Sprawozdanie z laboratoriów

Wykonał:

Gwidon Jóźwiak, 171864

1.     Cel.

Celem przeprowadzanych ćwiczeń było porównanie różnych algorytmów rozwiązywania problemu zadanego podczas laboratorium. Kryterium minimalizacji był czas wykonywania zadań przez dwie fabryki przy zachowaniu ograniczeń, którymi są:

- maksymalna liczba wykonywanych zadań (dla naszej fabryki)

- budżet (dla fabryki zewnętrznej).

Każde z zadań ma określoną trudność wykonania, która ma bezpośredni wpływ na czas jego wykonywania. Każda z fabryk ma określone parametry funkcji czasu wykonywania zadań w zależności od trudności.

2.     Branch and bound.

Do zaimplementowania tego algorytmu wykorzystałem rekurencyjne generowanie permutacji. Pozwala to zaimplementować permutacje w formie drzewa i w łatwy sposób podejmować decyzje o podziale lub ograniczeniach. Przykładowe drzewo dla liczby zadań równej 4 i ograniczeniu dla naszej fabryki 2 można zaprezentować następująco:

Zadania oznaczone jako 1 są wykonywane w naszej fabryce, natomiast 0 w zewnętrznej.

W celu określenia kryterium podziału zastosowałem następujące zabiegi.

Na początku jako najlepsze rozwiązanie ustawiam permutację składającą się z samych zer. Następnie w każdym z kroków rekurencji sprawdzam kolejno wszystkie permutacje na danym poziomie (dla powyższego drzewa na początku porównuję z 0000 permutacje 1000, 0100, 0010, 0001) i dokonuję podziału tylko dla tych, które dają lepsze rozwiązanie. Po dokonaniu selekcji na danym poziomi wybieram najlepsze z rozwiązań i ustawiam je jako obecnie najlepsze w celu dalszych porównań.

Taka metoda ograniczeń nie daje rozwiązań optymalnych, ale znacznie obniża czas działania programu a wyniki są dość zbliżone do optimum.

3.     Przegląd zupełny.

Przegląd zupełny to algorytm, który sprawdza wszystkie możliwości. Wynika z tego, że znajduje on rozwiązanie optymalne za każdym razem, jednak ma to zasadniczą wadę. Czas wykonywania takiego algorytmu jest bardzo długi, ponieważ jego złożoność obliczeniowa jest ogromna.

W tym algorytmie również zastosowałem rekurencyjną generację permutacji jednak bez użycia jakiej kol wiek funkcji ograniczającej podziały. W wyniku tego algorytm dokonał wszystkich podziałów, a co za tym idzie wykonywał się znacznie dłużej. Ma to swoje wady i zalety. Do zalet zaliczymy znalezienie zawsze rozwiązania optymalnego, jednak wadą jest, że przy dużej liczbie zadań algorytm działał by zbyt długo i oczekiwanie na wyniki byłoby nieopłacalne, dlatego z pomocą przychodzi Branch & Bound, który ogranicza sprawdzanie permutacji i przyśpiesza czas działania.

Na podstawie powyższego opisu można wysnuć bardzo prosty wniosek. Dla bardzo małych liczby zadań warto stosować przegląd zupełny, jednak przy większych rozmiarach lepiej zastosować Branch & Bound. Faktem jest też to, że z pewnością można zastosować wiele bardziej efektywnych metod ograniczenia, co dałoby z pewnością lepsze wyniki, jednak nie miałem żadnego ciekawszego pomysłu.

4.     Heurystyka.

Jednym ze sposobów ograniczenia czasu wykonania algorytmu jest przewidywanie dla jakich permutacji rozwiązania będą najlepsze i sprawdzanie tylko tych rozwiązań. Oczywiście jak to bywa z przewidywaniem nie zawsze się sprawdza. Ja zastosowałem następującą technikę.

Zauważyłem, że kompletnie nieopłacalnym jest wykonywanie wszystkich zadań tylko w jednej z fabryk. Poza tym zauważyłem, iż lepiej by jak najwięcej trudnych zadań wykonywała fabryka, która działa szybciej (ma lepsze parametry funkcji czasu). W tym celu zastosowałem następujący algorytm.

Na początku sprawdzam, która fabryka działa szybciej. Do tego obliczam wartości obu funkcji czasu dla tej samej trudności. Fabryka szybsza będzie miała mniejszą wartość. Na podstawie tego podejmuję odpowiednie kroki.

Gdy szybszą jest nasza fabryka to szukam kolejnych najtrudniejszych zadań i dodaję je do naszej fabryki. Po każdym dodaniu sprawdzam czasy działanie. Powoduje to sprawdzenie tylko tylu permutacji ile wynosi liczba zadań możliwych do wykonania w naszej fabryce.

W przeciwnym razie najpierw dodaję do fabryki zewnętrznej kolejno najtrudniejsze zadania aż do osiągnięcia n-l (n to liczba zadań, a l to liczba zadań możliwych do wykonania przez naszą fabrykę), a pozostałe zadania przydzielam do naszej fabryki. Następnie sprawdzam czas wykonania i kolejno kontynuuję dodawanie zadań do fabryki zewnętrznej od najtrudniejszych za każdym razem sprawdzając czasy.

Zabieg ten z pewnością pomija rozwiązanie optymalne, ale na pewno bardzo przybliża rozwiązanie przy znacznym ograniczeniu czasu wykonania.

5.     Porównanie powyższych algorytmów.

W celu sprawdzenia który z algorytmów działa najlepiej dokonałem następującego eksperymentu. Dla tych samych danych wykonałem każdy z algorytmów. W poniższej tabeli znajdują się parametry programów.

W poniższej tabeli przedstawiam wyniki działanie programów.