INSTRUKCJA OBSŁUGI
Program będzie działał na każdej platformie sprzętowej posiadającej możliwość zainstalowania maszyny wirtualnej Javy.
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
Uruchomić program „Uruchom.bat” znajdujący się w katalogu głównym programu.
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:
Plik wejściowy można samodzielnie modyfikować. Plik znaleźć można się w katalogu /bin pod nazwą „input.txt”.
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