instrukcja i opis algorytmów, algorytm losowy:


INSTRUKCJA OBSŁUGI

  1. Program będzie działał na każdej platformie sprzętowej posiadającej możliwość zainstalowania maszyny wirtualnej Javy.

  2. Do uruchomienia potrzebne jest oprogramowanie Java Runtime Environment w wersji 1.6.0 lub nowszej. Można je pobrać m.in. pod tym adresem: http://www.java.com/pl/download/index.jsp

  3. Uruchomić program „Uruchom.bat” znajdujący się w katalogu głównym programu.

  4. W oknie głównym programu klikając myszką na kolejne przyciski można wygenerować nowy plik wejściowy (przycisk „generuj wejście”) oraz rozwiązać zadanie przy pomocy jednego z trzech algorytmów:

  5. Plik wejściowy można samodzielnie modyfikować. Plik znaleźć można się w katalogu /bin pod nazwą „input.txt”.

  6. Aby zakończyć pracę z programem wystarczy zamknąć główne okno programu bądź okno konsoli

OPIS ALGORYTMÓW

algorytm losowy:

Algorytm ten na początku każdemu samochodowi wybiera jednego z dwóch pracowników posiadających do tego samochodu kluczyki jako kierowcę. Samochód zapamiętuje numer identyfikacyjny aktywnego kierowcy. Następnie algorytm wchodzi w pętle, wewnątrz której wykonuje następujące operacje:

- wybranie losowo jednego samochodu

- zmiana kierowcy tego samochodu na drugiego pracownika posiadającego do niego kluczyki

- zliczenie wszystkich kierowców potrzebnych w obecnym układzie do uruchomienia wszystkich samochodów.

- jeżeli po zmianie potrzeba mniej kierowców, zmiany zostają zachowane. Jeżeli tyle samo lub więcej, zostaje przywrócony stan sprzed zamiany.

Algorytm kończy swoje działanie po wykonaniu zadanej liczby iteracji.

algorytm zachłanny:

Algorytm zachłanny operuje na liście wszystkich pracowników firmy. W pojedynczej iteracji wyszukuje wśród nich osobę, która posiada najwięcej kluczy do jeszcze nie uruchomionych samochodów. Pracownik ten zostaje dodany do listy zawierającej wszystkich wykorzystanych w danym rozwiązaniu pracowników. Kluczyki będące w jego posiadaniu zostaną dołączone do znalezionych w poprzednich iteracjach kluczyków. Algorytm kończy swoje działanie, gdy uzyskany zostanie dostęp do wszystkich samochodów.

algorytm wychładzania:

Zaimplementowany przeze mnie algorytm wychładzania działa do etapu tak samo jak algorytm losowy. W pojedynczej iteracji zamieniamy w losowym samochodzie kierowcę i liczymy ogólną liczbę pracowników potrzebną do uruchomienia wszystkich samochodów. Algorytm losowy porównywał tą liczbę ze stanem sprzed zmiany, i jeśli nowa liczba kierowców była taka sama lub większa - cofał zmiany. Do tego momentu algorytm losowy i wychładzania są identyczne. Jednak algorytm wychładzania może w pewnym przypadku zatwierdzić zmianę nawet wtedy, gdy liczba kierowców po zmianie jest większa od liczby kierowców sprzed zmiany. Szansa zaistnienia takiego przypadku jest obliczana z pewnym prawdopodobieństwem, które maleje (liniowo) wraz z czasem wykonywania algorytmu. Prawdopodobieństwo to jest zależne od czynnika zwanego temperaturą. Czynnik ten zmniejsza się o pewną wartość w każdej iteracji algorytmu. Dzięki temu algorytm nie blokuje się na maksimach lokalnych.

UWAGI

Jeśli algorytm losowy i wychładzania nie daje pożądanych wyników (bardzo różnią się od algorytmu zachłannego), należy:

- w algorytmie losowym zwiększyć ilość iteracji pętli.

- w algorytmie wychładzania eksperymentować z początkową wartością temperatury i wartością o jaką się zmniejsza



Wyszukiwarka