25.01.2011

Projektowanie efektywnych algorytmów

Laboratorium

Prow.: dr inż. Andrzej Kozik

Elżbieta Tchorowska, 171067

Spis treści:

1. Wstęp 3

2. Estymacje 3

2.1 Estymacja zerem 4

2.1.1 Wykres funkcji czasowej od ilości miast w instancji 4

2.1.2 Wykres funkcji ilości odciętych gałęzi od liczby miast w instancji 5

2.1.3 Wykres funkcji ilości odwiedzonych wierzchołków od liczby miast w instancji 5

2.1.4 Jak podziała zwiększenie kryterium na czas estymacji? 6

2.2 Estymacja jedynką 6

2.2.1 Wykres funkcji czasowej od ilości miast w instancji 6

2.2.2 Wykres funkcji ilości odciętych gałęzi od liczby miast w instancji 7

2.2.3 Wykres funkcji ilości odwiedzonych wierzchołków od liczby miast w instancji 7

2.2.4 Jak podziała zwiększenie kryterium na czas estymacji? 8

2.3 Estymacja dwójką 8

2.3.1 Wykres funkcji czasowej od ilości miast w instancji 9

2.3.2 Wykres funkcji ilości odciętych gałęzi od liczby miast w instancji 9

2.3.3 Wykres funkcji ilości odwiedzonych wierzchołków od liczby miast w instancji 10

2.3.4 Jak podziała zwiększenie kryterium na czas estymacji? 10

3. Minimalne drzewo rozpinające 11

3.1 Wykres czasu od ilości miast 11

3.2 Wykres odciętych gałęzi od ilości miast 11

3.3 Wykres odwiedzonych wierzchołków od listy miast 12

4. Histogram wyników 12

4.1 Według rozwiązań 12

4.2 Według czasu 13

5. Wnioski 14

5.1 Estymacja zerem 14

5.2 Estymacja jedynką 14

5.3 Estymacja dwójką 15

5.4 Minimalne Drzewo Rozpinające 15

5.5 Histogram wyników 15

Wstęp

Celem projektu było zbadanie efektywności algorytmów rozwiązujących problem komiwojażera. W projekcie zawarto opracowania wyników dla trzech estymacji odcięć gałęzi drzewa, minimalnego drzewa rozpinającego i algorytmu symulowanego wyżarzania.

Problem przedstawiono jako strukturę listy dwukierunkowej z wartownikiem. Wielkości badanych instancji należały do przedziału liczb całkowitych <8,…,16>. By wyeliminować błędy dla każdego przypadku przebadano 50 różnych instancji tego samego typu i wyciągnięto z wyników średnią arytmetyczną. Dla każdej instancji sprawdzono metodą przeglądu zupełnego najlepszą drogę komiwojażera.

Wybranym językiem programowania był C++, środowisko DevC++. Sprzęt, który obsłużył program to Intel Core Duo 1,86GHz, 1 GB pamięci RAM.

Estymacje

Pod hasłem estymacje rozumiemy trzy metody odcinania krawędzi w grafie tak, by odciąć najdłuższe rozwiązania i nie musieć ich już później przeglądać. Uwzględniliśmy trzy estymacje: E0, E1 i E2, gdzie każda różni się od poprzedniej większą możliwą liczbą odcięć gałęzi. Naszym zadaniem jest takie dobranie kryteriów tych estymacji, by liczba odcięć była jak największa, ale żebyśmy nigdy nie odcięli gałęzi, której odcinać nie powinniśmy. Program zwraca nam kilka wartości: ilość odcięć gałęzi, ilość odwiedzonych wierzchołków w drzewie, czas działania algorytmu. Po każdym przebiegu sprawdzane jest, czy rozwiązanie otrzymane mieści się w kryterium rozwiązania bliskiego optymalnemu.

Estymacja zerem

Wykresy zostały narysowane dla jednego kryterium 200+80, które daje dobre rezultaty rozwiązania.

Wykres funkcji czasowej od ilości miast w instancji

Wykres funkcji ilości odciętych gałęzi od liczby miast w instancji

Wykres funkcji ilości odwiedzonych wierzchołków od liczby miast w instancji

Jak podziała zwiększenie kryterium na czas estymacji?

Estymacja jedynką

Wykresy zostały narysowane dla jednego kryterium 200+80, które daje dobre rozwiązania.

1. Wykres funkcji czasowej od ilości miast w instancji

2. Wykres funkcji ilości odciętych gałęzi od liczby miast w instancji

Wykres funkcji ilości odwiedzonych wierzchołków od liczby miast w instancji

Jak podziała zwiększenie kryterium na czas estymacji?

Estymacja dwójką

Wykresy zostały narysowane dla jednego kryterium 200+80, które daje dobre rozwiązania.

Wykres funkcji czasowej od ilości miast w instancji

Wykres funkcji ilości odciętych gałęzi od liczby miast w instancji

Wykres funkcji ilości odwiedzonych wierzchołków od liczby miast w instancji

Jak podziała zwiększenie kryterium na czas estymacji?

1. Minimalne drzewo rozpinające

   1. Wykres czasu od ilości miast

1. Wykres odciętych gałęzi od ilości miast

2. Wykres odwiedzonych wierzchołków od listy miast

1. Histogram wyników

   1. Według rozwiązań

   2. Według czasu

1. Wnioski

   1. Estymacja zerem

Funkcja czasu od liczby miast rośnie eksponencjalnie, co oznacza, że dla małej ilości miast algorytm działa szybko dając prawdopodobnie całkiem dobre rezultaty, ale jak można zauważyć na wykresie przy jedenastu miastach funkcja zaczyna powoli rosnąć, by przy dwunastu urosnąć kilkukrotnie.

Czas oczekiwania 30.000 milisekund nie jest stosunkowo duży, ale przy powiększeniu instancji o jeszcze jedno miasto otrzymujemy 10-krotny czas poprzedniej estymacji. Można założyć, że przy jeszcze jednym mieście czas znów wzrośnie wykładniczo, co da nam długi efekt oczekiwania.

Podobnie dla wykresu ilości odwiedzonych wierzchołków od wielkości instancji, jakoże czas wykonywania algorytmu zależy właśnie od przejrzenia konkretnej liczby wierzchołków.

Wykres liczby odciętych wierzchołków od wielkości instancji również rośnie w tempie eksponencjalnym. Wynika to z faktu, że ilość permutacji rośnie tylu krotnie, ile wynosi indeks dostawianego miasta, przez co wzrasta ilość „gorszych” dróg do wyboru i pojawia się opcja odcięcia większej ilości gałęzi.

W przypadku zwiększenia kryterium poszukiwań o 20%, czas rośnie dalej wykładniczo, ale zaczyna rosnąć dopiero w okolicach trzynastu miast, pierwsze dwanaście pozostaje na podobnym, liniowym poziomie.

Złożoność O(n²) zapewnia nam właśnie wykresy wykładnicze, a ponieważ odcinamy stosunkowo niewiele gałęzi nie można mówić o dużym poprawieniu czasu działania algorytmu.

Podsumowanie: dla 11 miast -> czas = 300.000 milisekund,

Odcięte gałęzie = 5 milionów

Odwiedzone wierzchołki = 40 milionów.

Estymacja jedynką

Sytuacja wygląda podobnie jak w estymacji zerem, wszystkie wykresy są eksponencjalne. Istotną zmianą jest to, że funkcja rośnie łagodniej i zaczyna rosnąć w okolicach dziesiątego miasta. Nastąpił również wyraźny spadek czasu pracy algorytmu oraz ilości odwiedzonych wierzchołków. Liczba odciętych gałęzi natomiast spadła, co znaczy, że gałęzie były odcinane prawie u samego korzenia, co również spowodowało spadek czasu oczekiwania na efekt.

Zwiększenie kryterium ponownie przesuwa miejsce skoku funkcji o 2 miasta i powoduje wykładniczy wzrost czasu.

Podsumowanie: dla 11 miast -> czas= 40 tysięcy milisekund

Odcięte gałęzie = 2 tysięce

Odwiedzone wierzchołki = 15 milionów

Estymacja dwójką

Wykresy podobne jak w poprzednich estymacjach. Jednak robiąc wykresy należało zwrócić uwagę, że rozrzut z wynikami był bardzo duży. Czas wahał się od 0,5 milisekundy do 500 milisekund dla tej samej instancji. Długość czasu wykonywania algorytmu waży na jakości wyników, które w takich przypadkach są albo kiepskie, albo nie ma ich wcale.

Dlatego, mimo, iż może się wydawać, że algorytm działa szybko nie daje dobrych wyników, z powodu zbyt szybkiego odcinania gałęzi. Często zdarza się, że algorytm ucina drzewo już na samym korzeniu, stąd rozrzut w wynikach też jest duży. Na potrzeby wykresów i histogramów usunięto przypadki, kiedy algorytm nie zwracał wyniku, a z reszty wyciągnięto średnią arytmetyczną, która mimo wszystko nie jest zbyt obiektywnym punktem oparcia.

Podsumowanie: dla 11 miast -> czas=100 milisekund

Odcięte gałęzie=10 tysięcy

Odwiedzone wierzchołki = 250 tysięcy.

Minimalne Drzewo Rozpinające

Wykresy identyczne jak przy estymacjach, zależności wykładnicze.

MST dla przypadków instancji poniżej 13 miast działa podobnie do estymacji, na wykresie nie do końca widać zależność, z powodu bardzo dużej skali. Funkcja zaczyna gwałtownie rosnąć właśnie punkcie 13 miast. Wyniki dla 14 miast mogą porazić - 17 milionów milisekund, a wyniki obliczeń też zbliżone do estymacji

Histogram wyników

Dla każdej badanej instancji sprawdzono przeglądem zupełnym rozwiązanie optymalne. Wyniki porównania między rozwiązaniem optymalnym, a uzyskanym przez estymacje przedstawiono na wykresie. Estymacja zerem, która jest podobna do przeglądu zupełnego za każdym razem znalazła optymalne rozwiązanie, czemu trudno się dziwić. Estymacja jedynką była albo bliska rozwiązaniu, albo znalazła rozwiązanie optymalne. Niestety najgorzej wypadła ostatnia estymacja, która była daleka od rozwiązania.

Jeśli chodzi o wykresy czasowe, oczywiste, że najlepiej spisała się estymacja dwójką i to nawet w momentach, gdy znajdowała rozwiązanie. Co zaskakujące estymacja jedynką miała gorsze wyniki niż estymacja zerem, pewnie przez dodatkowe operacje w algorytmie.

Stąd wniosek, że jeśli stawiamy na dokładniejsze rozwiązanie, należy wybrać estymację zerem, jeśli na czas to estymację dwójką.