Projektowanie efektywnych algorytmów

Laboratorium

TEMAT:

Algorytm programowania dynamicznego

PROBLEM:

Problem Komiwojażera

Data oddania

…..........................................

Ocena

…..........................................

Autor:

Michał Kaczara

Nr indeksu:

181132

Rok i kierunek

studiów:

Informatyka I st. inż., rok 3, sem. 5

Grupa ćwiczeniowa:

PN/TN 9:15-11:00

Prowadzący:

Mgr inż. Agata Rusoń

2

1.

Opis słowny i matematyczny problemu. Kryterium optymalizacji

1.1 Opis problemu

Problem Komiwojażera(ang. TSP – Travelling Salesman Problem) definiuje

sytuację, w której komiwojażer ma odwiedzić wszystkie N miast tylko raz i wrócić do

miasta początkowego, przy czym trasa jego podroży powinna być jak najkrótsza.

Droga pomiędzy każdą parą miast ma parametr – koszt jej przebycia, długość lub np.

czas podróży. W rozpatrywanym przypadku parametrem jest koszt przebycia drogi.

Pod względem matematycznym, problem ma swoje odzwierciedlenie w teorii

grafów. Każde z N miast jest wierzchołkiem grafu zupełnego, ważonego – każda

krawędź łącząca dwa wierzchołki(V

i

, V

j

) ma wagę, odpowiadającą kosztowi

przebycia drogi z V

i

do V

j

. Znalezienie takiej drogi, aby każdy z N wierzchołków

występował na niej tylko raz sprowadza się do znalezienia w grafie tzw. cyklu

Hamiltona. Problem Komiwojażera jest problemem NP-trudnym.

1.2

Dane wejściowe problemu

Dane wejściowe problemu stanowi N-wierzchołkowy graf pełny, ważony,

przedstawiony w postaci macierzy kosztów o rozmiarach NxN, zapisanej w pliku

tekstowym. Każda wartość macierzy należy do przedziału <0;100> i jest oddzielona

od pozostałych za pomocą tabulatora(\t). Ponieważ z miasta N

i

do miasta N

i

drogi nie

ma, diagonala macierzy zawiera wartości reprezentujące nieskończoność.

Dla ułatwienia implementacji za nieskończoność przyjęta została liczba 9999.

Listing 1. Przykładowe dane wejściowe problemu
9999

9

93

13

42

9999 88

16

17

88

9999 36

33

7

21

9999

1.3

Rozwiązanie problemu

Rozwiązanie problemu składa się z czterech linii. W pierwszej znajduje się

całkowity koszt optymalnej trasy; w drugiej: wektor indeksów N miast, które kolejno

występują na trasie(z uwzględnieniem powrotu do początkowego, długość wektora –

N+1). Kolejne indeksy są oddzielone przecinkiem i znakiem spacji; w trzeciej: czas

wykonania algorytmu podany w milisekundach; Wartość czwartej linii jest ściśle

zależna od implementacji i zawiera liczbę będącą wartością licznika użyć danych

zapisanych poprzednio w pamięci.

Listing 2. Przykładowe rozwiązanie problemu
63
[ 0, 1, 3, 2, 0 ]
15
0

3

1.4

Kryterium optymalizacji

Za kryterium optymalizacji została przyjęta minimalizacja kosztu cyklu Hamiltona

w grafie wejściowym, co jest równoważne znalezieniu najkrótszej drogi przejścia

przez graf.

2.

Opis działania algorytmu

2.1 Algorytm przeglądu zupełnego

Metoda przeglądu zupełnego zastosowana w przypadku problemu komiwojażera

polega na znalezieniu wszystkich możliwych cykli Hamiltona w zadanym grafie,

a następnie wybranie spośród nich takiego, którego obliczony koszt jest najmniejszy.

Krótka analiza złożoności obliczeniowej tego algorytmu:

Weźmy graf o N=9 wierzchołkach i policzmy ile ma cykli Hamiltona. Z pierwszego

wierzchołka możemy wybrać 8 krawędzi, z drugiego 7, z trzeciego 6, …,

z dziewiątego – 1 krawędź. W efekcie liczba cykli Hamiltona jest równa:

H = 8 * 7 * 6 * 5 * … * 1 = 8! =

40 320

Zatem dla N wierzchołków liczba cykli wyniesie H = (N-1)!. Wynik ten należy do

wykładniczej klasy złożoności obliczeniowej O(n!).

2.2

Algorytm programowania dynamicznego

Algorytm programowania dynamicznego został zaimplementowany przeze mnie

wg zasady dziel i zwyciężaj(ang. divide & conquer), polegającej na rekurencyjnym

podziale głównego problemu na podproblemy, tak aby rozwiązywać najprostsze

instancje problemów, których rozwiązania są potem scalane. Rozwiązania (koszt

i ścieżka) uzyskane w każdym z kroków są zapisywane do struktur umożliwiających

ich przechowywanie i identyfikację – dzięki temu algorytm może wykonywać się

szybciej, bo przed rozwiązaniem podproblemu sprawdza, czy nie został on już

wcześniej rozwiązany i jeśli tak, to zwraca to rozwiązanie(pomija zbędne obliczenia).

Do przechowywania rozwiązań pośrednich wykorzystałem specyficzne struktury

dostępne w języku Java(więcej w pkt. 4). Podproblemy, które mogą być rozwiązane

w ramach danego problemu nadrzędnego określa tablica o rozmiarze N z wpisanymi

pod odpowiednie indeksy wartościami logicznymi TRUE lub FALSE. Jeśli wpis na

i-tej pozycji tablicy to TRUE, algorytm będzie kontynuował działanie bez

wywoływania rekurencji dla tego podroblemu, w przeciwnym wypadku rekurencja

zostanie wywołana. W przypadku, w którym wszystkie elementy tablicy mają

wartości TRUE, jako ścieżka zapisywane jest miasto początkowe, a jako koszt –

wartość na pozycji [aktualne miasto][miasto początkowe] w macierzy kosztów

4

instancji problemu. Scalanie wyników podproblemów zostało przeze mnie

zrealizowane w dwóch krokach:



wyznaczenie minimum z kosztów dla każdego z podproblemów i zapisanie

numeru podproblemu, dla którego koszt był minimalny,



po rozwiązaniu wszystkich możliwych podproblemów: stworzenie tablicy

zawierającej ścieżkę, składającą się z numeru podproblemu, dla którego

koszt był minimalny i ścieżki uzyskanej w wyniku rozwiązywania tego

podproblemu.

Aby algorytm działał poprawnie, konieczne było wprowadzenie odpowiedniego

sterowania wartościami tablicy użytych miast(rozwiązanych podproblemów).

Przed każdym wywołaniem rekurencji na pozycji danego podproblemu w tablicy

ustawiana jest wartość TRUE. Po wykonaniu się rekurencji, wartość ustawiana jest

z powrotem na FALSE.

2.2.1 Pseudokod algorytmu

Poniżej zamieszczam pseudokod zaimplementowanego algorytmu programowania

dynamicznego. Listing przedstawia treść funkcji rekurencyjnej liczKoszt, przy

założeniu, że instancja problemu została wczytana poprawnie, zostało wybrane

miasto początkowe miastoStart, np. 0, została stworzona tablica miast użytych

miastaUzyte

i wpisana wartość TRUE na pozycji miastoStart, została

stworzona tablica listaWynik, w której przechowywana będzie lista wierzchołków

znajdujących się na optymalnej ścieżce oraz struktury koszty i sciezki, w których

przechowywane będą wyniki uzyskane dla kolejnych podproblemów.

Listing 3. Pseudokod algorytmu DP dla TSP

procedure liczKoszt(tablica, listaWynik, aktualneMiasto, miastoStart, uzyteMiasta)
begin

wynik

← stworzTablice(pobierzRozmiar(uzyteMiasta)

aktualneID

← aktualneMiasto + toString(uzyteMiasta)

if wszystkieUzyte(uzyteMiasta) then

begin

dopisz(listaWynik, miastoStart)

dopisz(koszty, aktualneID, tablica[aktualneMiasto][miastoStart])

return tablica[aktualneMiasto][miastoStart]

end

else

begin

if pobierz(koszty, aktualneID) != null then

begin

dopisz(listaWynik, pobierz(sciezki, aktualneID))

licznik ← licznik + 1

return pobierz(koszty, aktualneID)

end

5

for i ← pobierzRozmiar(uzteMiasta) step -1 until 0 do

begin

if uzyteMiasta[i] continue

uzyteMiasta[i] ← TRUE

k ← liczKoszt(tablica,wynik[i],i,miastoStart,uzyteMiasta)

uzyteMiasta[i] ← FALSE

k ← k + tablica[aktualneMiasto][i]

if k < min then

begin

Min ← k

wynikIdx ← i

end

end

dopisz(temp, wynikIdx)
dopisz(temp, wynik[wynikIdx])

dopisz(listaWynik, temp)
dopisz(koszty, aktualneID, min)
dopisz(sciezki, aktualneID, temp)

end

end

3.

Przykładowe rozwiązania dla wybranej instancji

Poniżej zamieszczam przykładowe rozwiązanie algorytmu dla instancji

przedstawionej na listingu 1.(str 2.). Macierz kosztów jest macierzą kwadratową

i asymetryczną o rozmiarach 4x4, rozważam więc asymetryczny problem komiwojażera

dla N=4 miast.

[

9999

9

93

13

42

9999

88

16

17

88

9999

36

33

7

21

9999

]

3.1 Wywołanie funkcji liczKoszt()

uzyteMiasta = T, F, F, F

Nie wszystkie miasta są odwiedzone i nie ma odpowiedniego wpisu w mapie

kosztów – przechodzimy do pętli i wywołujemy odpowiednie rekurencje

i = 3

3.1.1 Rekurencja, miasto: 3, listaWynik: wynik[3]

uzyteMiasta = T, F, F, T

Nie wszystkie miasta są odwiedzone i nie ma odpowiedniego wpisu

w mapie kosztów – przechodzimy do pętli i wywołujemy odpowiednie

rekurencje

i = 3 uzyteMiasta[3] == T, więc kontynuujemy

i = 2

6

3.1.1.1 Rekurencja, miasto: 2, listaWynik: wynik[2]

uzyteMiasta = T, F, T, T

Nie wszystkie miasta są odwiedzone i nie ma odpowiedniego wpisu

w mapie kosztów – przechodzimy do pętli i wywołujemy

odpowiednie rekurencje

i = 3 uzyteMiasta[3] == T, więc kontynuujemy

i = 2 uzyteMiasta[2] == T więc kontynuujemy

i = 1

3.1.1.1.1 Rekurencja, miasto: 1, listaWynik: wynik[1]

uzyteMiasta = T, T, T, T

Wszystkie miasta odwiedzone – zapis wyników

listaWynik = 0;

koszty += (1 [T, T, T, T]; tablica[1,0] = 42)

koszt = 42 + tablica[2][1] = 130

min = 130

wynikIdx = 1

i = 0 uzyteMiasta[0] == T, więc kontynuujemy

listaWynik = 1,0

koszty += (1 [T, F, T, T]); 130)

sciezki += (1 [T, F, T, T); 1,0)

koszt = 130 + tablica[3][2] = 151

min = 151

wynikIdx = 2

i = 1

3.1.1.2 Rekurencja, miasto: 1, listaWynik: wynik[1]

uzyteMiasta = T, T, F, T

Nie wszystkie miasta są odwiedzone i nie ma odpowiedniego wpisu

w mapie kosztów – przechodzimy do pętli i wywołujemy

odpowiednie rekurencje

i = 3 uzyteMiasta[3] == T, więc kontynuujemy

i = 2

3.1.1.2.1 Rekurencja, miasto: 2, listaWynik: wynik[2]

uzyteMiasta = T, T, T, T

Wszystkie miasta odwiedzone – zapis wyników

listaWynik = 0;

7

koszty += (1 [T, T, T, T]; tablica[2][0] = 17)

koszt = 17 + tablica[1][2] = 105

min = 105

wynikIdx = 2

i = 1 uzyteMiasta[1] == T, więc kontynuujemy

i = 0 uzyteMiasta[0] == T, więc kontynuujemy

listaWynik = 2,0

koszty += (1 [T, T, F, T]); 105)

sciezki += (1 [T, T, F, T); 2,0)

koszt = 105 + tablica [2][1] = 112

min = 112

wynikIdx = 1

i = 0 uzyteMiasta[0] == T, więc kontynuujemy

listaWynik = 1, 2, 0

koszty += (3 [T, F, F, T]); 112)

sciezki += (1 [T, F, F, T); 1,2,0)

koszt = 112 + tablica[0][3] = 125

min = 125;

wynikIdx = 3;

i = 2

Wykonujemy

operacje

analogiczne

do

przedstawionych

powyżej.

Wartość minimalna się nie zmieni.

i = 1

Wykonujemy operacje analogicznie do przedstawionych powyżej. Po ich

wykonaniu wartość minimum wyniesie 63, a ścieżka będzie kolejno przyjmować

wartości: 0; 2,0, następnie: 3,2,0. Indeks tablicy ścieżek będzie równy 1.

i = 0 uzyteMiasta[0] == T, więc kontynuujemy

listaWynik = 1,3, 2, 0

koszty += (0 [T, F, F, F]; 63)

sciezki += (0 [T, F, F, F]; 1,3,2,0)

3.2 Wyniki

63 – koszt przebycia drogi

[0, 1, 3, 2, 0] - droga

1500000 – czas wykonywania – 25 min, zajęło mi przeliczenie na kartkach

0 – licznik wykorzystań rozwiązań podproblemów

8

4.

Szczegóły implementacyjne

Algorytm został zaimplementowany w języku Java, w środowisku Eclipse.

Cały program jest reprezentowany przez jedną klasę KomiwojazerDP, w której

zdefiniowane są metody niezbędne do rozwiązania problemu oraz pomocnicze, np.

metoda odpowiedzialna za konwersję tablicy wartości typu boolean na łańcuch

tekstowy, w którym 1 oznaczają TRUE a 0 - FALSE. Program, do przechowywania

rozwiązań podproblemów, korzysta ze struktur HashMap dostępnych domyślnie

w języku Java. Wyniki są przechowywane na zasadzie klucz => wartość, gdzie klucz

to wartość zmiennej aktualneID(pkt. 2.2.1). Poniżej zamieszczam listing

najważniejszej funkcji – liczKoszt().

Listing 4. Metoda liczKoszt klasy KomiwojazerDP

private static int liczKoszt(int [][]tablica, ArrayList<Integer> listaWynik, int
aktualneMiasto, int miastoStart, boolean[] uzyteMiasta){

//Tablica ze sciezka wynikowa

ArrayList<Integer> []wynik = new ArrayList[uzyteMiasta.length];

String aktualneID = "" + aktualneMiasto + arrayToString(uzyteMiasta);

System.out.println("Rekurencja (miasto "+aktualneMiasto+"):");

//Jezeli wszystkie miasta przebyte

if(wszystkieUzyte(uzyteMiasta)){

listaWynik.add(miastoStart);

int koszt = tablica[aktualneMiasto][miastoStart];

koszty.put(aktualneID, koszt);

System.out.println("\t> Wszystkie miasta odwiedzone");

return koszt;

}

//Jezeli nie

else {

int min = Integer.MAX_VALUE;

int wynikIdx = -1;

//Jezeli podproblem juz rozwiazany

if(koszty.get(aktualneID) != null){

listaWynik.addAll(sciezki.get(aktualneID));

licznik++;

System.out.println("\t> Wykorzystanie wartosci obliczonej

wczesniej");

return koszty.get(aktualneID);

}

//Jezeli nie to obliczenia
System.out.println("\t> Obliczenia");

for(int i = uzyteMiasta.length -1; i >= 0; i--){

if(uzyteMiasta[i]) continue;

//Rekurencja

uzyteMiasta[i] = true;

wynik[i] = new ArrayList<Integer>();

int koszt = liczKoszt(tablica, wynik[i], i, miastoStart,

uzyteMiasta);

uzyteMiasta[i] = false;

koszt += tablica[aktualneMiasto][i];

//Aktualizacja kosztu minimalnego

if(koszt < min){

min = koszt;

wynikIdx = i;

System.out.println("\t> Ustawienie minimum");

}

}

9

//Zapis wynikow

System.out.println("\t> Zapis wynikow");

ArrayList<Integer> temp = new ArrayList<Integer>();

temp.add(wynikIdx);

temp.addAll(wynik[wynikIdx]);

listaWynik.addAll(temp);

koszty.put(aktualneID, min);

sciezki.put(aktualneID, temp);

System.out.println("\t> Powrot poziom wyzej");

return min;

}

}

Pomiar czasu wykonywania algorytmu wykonany został z użyciem funkcji

System.nanoTime()

. Komputer, na którym testowany algorytm wyposażony był

w procesor Intel Core 2 Duo 2,2 GHz i 2 GB pamięci RAM. Program uruchamiany był

pod systemem Windows 7 Professional 32-bit.

5.

Przykład działania programu dla wybranej instancji

Poniżej zamieszony został listing zawierający przykład działania programu.

Jest to wyciąg z konsoli programu Eclipse. Program wyświetla kolejne rekurencje

i akcje, które w ramach nich podejmuje. Informuje m.in. o dokonywaniu obliczeń,

pomijaniu obliczeń, ustawianiu minimum i zapisie wyników.

Listing 5. Przykład działania programu

Program:

Algorytm Dynamic Programming dla problemu komiwojazera

Przedmiot:

Projektowanie Efektywnych Algorytmów

Autor:

Michal Kaczara

181132

> Wczytywanie danych z pliku data04.txt...

> Start!
Rekurencja (miasto 0):

> Obliczenia

Rekurencja (miasto 3):

> Obliczenia

Rekurencja (miasto 2):

> Obliczenia

Rekurencja (miasto 1):

> Wszystkie miasta odwiedzone

> Ustawienie minimum

> Zapis wynikow

> Powrot poziom wyzej

> Ustawienie minimum

Rekurencja (miasto 1):

> Obliczenia

Rekurencja (miasto 2):

> Wszystkie miasta odwiedzone

> Ustawienie minimum

> Zapis wynikow

> Powrot poziom wyzej

> Ustawienie minimum

> Zapis wynikow

> Powrot poziom wyzej

> Ustawienie minimum

Rekurencja (miasto 2):

> Obliczenia

10

Rekurencja (miasto 3):

> Obliczenia

Rekurencja (miasto 1):

> Wszystkie miasta odwiedzone

> Ustawienie minimum

> Zapis wynikow

> Powrot poziom wyzej

> Ustawienie minimum

Rekurencja (miasto 1):

> Obliczenia

Rekurencja (miasto 3):

> Wszystkie miasta odwiedzone

> Ustawienie minimum

> Zapis wynikow

> Powrot poziom wyzej

> Zapis wynikow

> Powrot poziom wyzej

Rekurencja (miasto 1):

> Obliczenia

Rekurencja (miasto 3):

> Obliczenia

Rekurencja (miasto 2):

> Wszystkie miasta odwiedzone

> Ustawienie minimum

> Zapis wynikow

> Powrot poziom wyzej

> Ustawienie minimum

Rekurencja (miasto 2):

> Obliczenia

Rekurencja (miasto 3):

> Wszystkie miasta odwiedzone

> Ustawienie minimum

> Zapis wynikow

> Powrot poziom wyzej

> Zapis wynikow

> Powrot poziom wyzej

> Ustawienie minimum

> Zapis wynikow

> Powrot poziom wyzej

> Stop!

63
[ 0, 1, 3, 2, 0 ]
3
0

6.

Badania eksperymentalne

Badania przeprowadziłem dla dziesięciu rozmiarów instancji problemu.

Dane wejściowej macierzy kosztów były generowane losowo. Każde pole macierzy

(oprócz tych leżących na diagonali), mogło przyjmować wartości z zakresu <1;100>.

Pomiary czasu wykonywania algorytmu zostały wykonane dla 100 instancji danego

rozmiaru i uśrednione(średnia arytmetyczna).

Tabela 1. Wyniki pomiarów czasu działania algorytmu w zależności od rozmiaru instancji.

Rozmiar instancji N

2

4

6

8

10

12

14

16

Średni czas [ms]

0,01

0,02

0,12

2,27

20,43

186,73

1271,21

6788,43

Pomiarów dla instancji o rozmiarze N=18 nie byłem w stanie wykonać, ze względu na

ograniczenie pamięciowe wirtualnej maszyny Java. Po zwiększeniu limitu pamięci z 256

11

na 512 MB program policzył rozwiązanie, jednak w czasie równym ok. 50 s. Przy N=20

i zwiększeniu limitu pamięci do 1 GB program nie potrafił policzyć rozwiązania, większa

ilość pamięci nie mogła zostać przydzielona ze względu na ograniczoną ilość pamięci

zainstalowanej w komputerze.

Wykres 1. Zależność czasu wykonywania algorytmu od rozmiaru instancji problemu.

7.

Wnioski

1.

Krzywa widoczna na wykresie 1. pokazuje, że zależność czasu rozwiązywania

problemu w zależności od rozmiaru instancji rośnie wykładniczo, czyli zgodnie

z przewidywaniami(algorytm programowania dynamicznego dla problemu

komiwojażera ma złożoność O(n

2

2

n

)).

2.

Największa badana instancja posiadała N=16 miast. Przy instancjach większych,

np. N=20 algorytm pracował nieprzerwanie przez dłuższy okres czasu.

Potwierdza to fakt, że algorytm programowania dynamicznego najlepiej stosować

do małych instancji problemów. Nie bez znaczenia mogło być w tym wypadku

losowe generowanie macierzy kosztów. Im większa instancja problemu tym

więcej pamięci operacyjnej potrzebował program. Do rozwiązania problemu

z N=16 miastami potrzebne było 265MB pamięci, z N=18 już 512MB, a przy N=20

więcej niż 1 GB. Duże użycie pamięci RAM to cecha algorytmów programowania

dynamicznego i zarazem duża wada tego rozwiązania.

3.

Zaimplementowany algorytm rozwiązuje problem komiwojażera sprawnie

i wystarczająco szybko dla N < 14 miast. Działa wolniej niż algorytm B&B.

0,01

0,02

0,12

2,27

20,43

186,73

1271,21

6788,43

0

1000

2000

3000

4000

5000

6000

7000

8000

2

4

6

8

10

12

14

16

Czas

[m

s]

Rozmiar instancji N

Czas [ms]

12

4.

Przyczyną dużej zajętości pamięci i dużego czasu rozwiązywania problemu już

przy instancjach zawierających N>15 miast, jest prawdopodobnie sposób

przechowywania pośrednich rozwiązań – są one indeksowane po kluczach

będących łańcuchami tekstowymi. Problemem jest też przeszukiwanie struktur,

które te rozwiązania przechowują.

13

8.

Bibliografia

[1] Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman, Projektowanie i analiza

algorytmów, Wyd. Helion, 2003, str. 41-47

[2] Politechnika Wrocławska, Programowanie dynamiczne (Dynamic Programming -

DP)

[online].

[Dostęp

17

grudnia

2011].

Dostępny

w

Internecie:

<ftp://sith.ict.pwr.wroc.pl/Informatyka/PEA/PD_wstep.pdf>

[3] Maria Jose Serna Iglesias, Dynamic Programming [online]. [Dostęp 17 grudnia

2011]. Dostępny w Internecie:

<http://www.lsi.upc.edu/~mjserna/docencia/algofib/P07/dynprog.pdf>