Projektowanie efektywnych algorytmów

Laboratorium

IMPLEMENTACJA

TEMAT: Schematy aproksymacyjne

PROBLEM: P₂ || C_max

Data oddania

15.01.2013

Ocena

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

Autor:	Piotr Ornat
Nr indeksu:	184724
Rok i kierunek studiów:	III INF
Nazwa grupy i jej skład:	„Cichy lichy”
Termin laboratorium	wt, TN 11.15

1. Implementacja

Program zawiera główną klasę o nazwie P2CMaxProblem, zawierającą metody realizujące algorytm oraz klasę Program, pełniącą tylko funkcję interfejsu użytkownika. Użytym językiem programowania jest C#.

Pola wchodzące w skład klasy P2CMaxProblem:

• private List<int> zadania – lista przechowująca czasy wykonywania zadań badanej instancji problemu

• int ilosc_zad ­– ilość zadań w instancji

• int czas_max – suma czasów wszystkich zadań – najwyższy możliwy wynik algorytmu

• List<int> uporządkowanie – lista przechowująca zera lub jedynki w zależności od procesora przypisanego każdemu zadaniu

• int czas_wynikowyPD – zmienna przechowująca wynik pracy tylko algorytmu programowania dynamicznego

• int czas_wynikowyFPTAS – zmienna przechowująca wynik pracy algorytmu aproksymacyjnego

• int TProc1=0, Tproc2=0 – zmienne przechowujące stan zajętości czasu procesorów przez zadania im przypisane. Inicjalizowane zerami, jest to stan bez przypisanych zadań.

• double epsilon = 0.35­ – zmienna epsilon określająca maksymalny błąd algorytmu aproksymacyjnego

• List<int> tempinstancja – lista przechowująca instancję badanego problemu zmodyfikowaną przez wyliczony w algorymie FPTAS parametr k.

Metody wchodzące w skład klasy P2CMaxProblem:

• P2CMaxProblem(int wielkosc) – konstruktor klasy, którego argumentem jest ilość zadań w instancji. Tworzy on obiekt z wygenerowaną losowo instancją o podanej wielkości

• void GenerujInstancje(int wielkosc); - funkcja generująca nową instancje problemu do już istniejącego obiektu klasy, o rozmiarze zadanym w parametrze.

• 5 metod Get.. – udostępniają niektóre zmienne klasie Program

• void Backtracking(bool [,] tabela, int ogr_czas, List <int> inst); - Metoda, która identyfikuje rozwiązanie powstałe w tabeli Programowania Dynamicznego i uzupełnia odpowiednio listę „uporządkowanie”. Wykonuje się rekurencyjnie.

• Int LiczCzasWynik() – Oblicza rozwiązanie w postaci czasu CMax na podstawie wypełnionej listy „uporządkowanie”.

• Int PDynamiczneP2CMax(List<int> instancja) – Metoda wykonująca część algorytmu FPTAS realizowaną za pomocą Programowania Dynamicznego.

• Void FPTAS() – Główna metoda algorytmu FPTAS

Każda instancja problemu składa się z wektora czasów wykonywania zadań

P = [p₁, p₂,  …,p_n], losowanych z przedziału <10;50>.

.

Przykładowe działanie programu dla jednej instancji wielkości n =20:

Użytkownik zadaje ilość zadań n. Na tej podstawie konstruktor klasy P2CMaxProblem dla obiektu instancja uruchamia generuje losową instancję dwudziestoelementową. Jak widać na powyższym rysunku, jest ona wypisywana na ekran oraz uruchamia się algorytm. Widać to w wypisanym pomiarze czasu wykonanym za pomocą obiektu klasy System.Diagnostics.Stopwatch w metodzie main klasy Program. Ponadto wypisuje się wynik przetwarzania w postaci wartości otrzymanego Cmax.

Opis najważniejszych funkcji programu:

P2CMaxProblem(int wielkosc)

{

System.Random rand = new System.Random();

for (int i = 0; i < wielkosc; i++)

zadania.Add(rand.Next(10, 50));

ilosc_zad = wielkosc;

}

Konstruktor jednoargumentowy, korzystając z obiektów klasy System.Random, dodaje kolejne długości wykonywania zadań do listy „zadania” losując liczbę całkowitą z zakresu <10,50>

void Backtracking(bool[,] tabela , int ogr_czas, List<int> inst)

{

int tempczas;

for (int j = ogr_czas; j >= 0; j--)

for (int i = 0; i <ilosc_zad; i++)

if (tabela[i, j] == true)

{

uporzadkowanie[i] = 1;

tempczas=ogr_czas - inst.ElementAt(i);

Backtracking(tabela, tempczas ,inst);

return;

}

}

Metoda realizująca Backtracking wykorzystuje parametry takie jak:

- tabela powstała w procesie PD

- ograniczenie czasowe wskazujące na którym etapie „skanowania” tabeli jest ta metoda

- lista zawierająca badaną instancję

Gdy metoda ta znajdzie odpowiednią komórkę(przeszukując od tyłu) zawierającą wartość logiczną „true”, rekurencyjnie uruchamia następną swoją instancję, która przeszukuje dalej, lecz „przeskakując” do miejsca oznaczonego zmienną „tempczas”.

int LiczCzasWynik()

{

for (int i = 0; i < ilosc_zad; i++)

if (uporzadkowanie.ElementAt(i) == 1)

{

Tproc2 += zadania.ElementAt(i);

}

TProc1 = czas_max - Tproc2;

if ((Tproc2 - TProc1) < 0) czas_wynikowy = TProc1;

else czas_wynikowy = Tproc2;

return czas_wynikowy;

}

Metoda LiczCzasWynik() zwraca obliczony czas Cmax („czas_wynikowy”), poszukując jedynek w liście „uporządkowanie” oraz sumując czasy wykonywania zadań przez nie wskazanych.

public int PDynamiczneP2CMax(List<int> instancja)

{

TProc1 = 0;

Tproc2 = 0;

int temp_suma,ogr_czas,czas_localmax=0, czas_maksymalny = zadania.ElementAt(0);

uporzadkowanie.Clear();

for (int i = 0; i < ilosc_zad; i++)

uporzadkowanie.Add(0);

for(int i = 0; i < ilosc_zad; i++)

{

czas_localmax += instancja.ElementAt(i);

if (czas_maksymalny < instancja.ElementAt(i))

czas_maksymalny = instancja.ElementAt(i);

}

temp_suma = czas_localmax / 2;

if (czas_maksymalny >= temp_suma)

{

ogr_czas = czas_maksymalny;

}

else

{

ogr_czas = temp_suma;

}

bool[,] tabela = new bool[1 + ilosc_zad, 1 + ogr_czas];

for (int i = 0; i < ilosc_zad + 1; i++)

for (int j = 0; j < ogr_czas + 1; j++)

tabela[i, j] = false;

for (int i = 0; i < 1 + ilosc_zad; i++)

tabela[i, 0] = true;

for (int i = 1; i < 1 + ilosc_zad; i++)

{

for (int j = 0; j < (1 + ogr_czas - instancja.ElementAt(i - 1)); j++)

{

if (tabela[i - 1, j] == true)

{

for (int k = i; k < 1 + ilosc_zad; k++)

tabela[k, j + instancja.ElementAt(i - 1)] = true;

}

if(tabela[ilosc_zad,ogr_czas] == true) break;

}

if(tabela[ilosc_zad,ogr_czas] == true) break;

}

Backtracking(tabela, ogr_czas,instancja);

int result = LiczCzasWynik();

return result;

}

Metoda PDynamiczneP2CMax zwraca wynik poszukiwania rozwiązania metodą PD dla instancji podanej jako parametr. W tym procesie zerowane są „czasy” procesorów oraz lista uporządkowanie. Algorytm Programowania Dynamicznego tworzy tabelę wartości boolowskich jednak nie jest on przewodnim tematem tego dokumentu więc przejdę do głównej metody:

void FPTAS()

{

double k;

for (int i=0; i < ilosc_zad; i++)

czas_max += zadania.ElementAt(i);

k = Math.Floor((epsilon * czas_max) / (2 * ilosc_zad));

for (int i = 0; i < ilosc_zad; i++)

tempinstancja.Add(Convert.ToInt32(Math.Floor(zadania.ElementAt(i) / k)));

czas_wynikowyFPTAS=PDynamiczneP2CMax(tempinstancja);

//czas_wynikowyPD = PDynamiczneP2CMax(zadania);

}

Metoda FPTAS jest nadrzędna do metody PDynamiczneP2CMax i zawiera operacje czyniące opracowany algorytm schematem aproksymacyjnym. Najpierw wyliczana jest suma zadań i zapisywana do zmiennej czas_max. Następnie wyznaczany jest współczynnik k, według wzoru $k = \left\lfloor \frac{\text{εS}}{2n} \right\rfloor$ i badana instancja jest zmieniana poprzez podzielenie każdego jej elementu przez k i zaokrągleniu w dół. Efekt tych obliczeń jest zapisywany do listy tempinstancja i służy jako obiekt pracy algorytmu PD. Dodatkowa linia zakryta komentarzem zawiera instrukcję wywołania metody Programowania Dynamicznego dla danych pierwotnych. Umożliwia ona poznanie rozwiązania optymalnego danej instancji, więc była podstawą badań jakościowych algorytmu FPTAS.

1. Badania

Przykładowe działanie aplikacji użytej do badań charakterystyk czasowych:

Po podaniu pożądanej wielkości instancji program wykonuje 100 iteracji, za każdym razem losując nową instancję o tej ilości zadań i badając ją algorytmem fptas. Zliczany jest czas średni poszczególnej iteracji.

Przeprowadzono w ten sposób badania algorytmu FPTAS dla zmiennej wielkości instancji n. Poniżej wykres przedstawia tą zależność.

n	Tfptas [ms]
10	4,74
20	15,74
30	26,72
50	131,79
100	806,85
150	2800,89
200	6970,56
250	15580,44
300	20588,30

Każdy pomiar był wykonywany dla 100 losowych instancji i uśredniany.

Podobne badania przeprowadzono dla algorytmu PD, ich wyniki przedstawia tabela:

n	TPD [ms]
10	15,05
20	32,34
30	113,20
50	459,42
100	4153,59
150	16184,66
200	37384,05
250	63376,30
300	115260,93

Porównanie wyników badań czasowych ilustruje wykres:

Ponieważ na dużym odcinku wykresy się pokrywają, różnicę w czasach wykonywania bardziej czytelnie widać przy logarytmicznej skali czasowej:

Na pierwszym wykresie nie widzimy większych różnic między algorytmami do około 100 zadań. Dla większych instancji czasy algorytmu PD zaczęły ostro rosnąć, zwiększając znacznie różnicę między nim a algorytmem aproksymacyjnym. Drugi wykres pokazuje stałą, wykładniczą różnicę pomiędzy algorytmami ­­– algorytm FPTAS zawsze działa szybciej.

Przykładowe działanie aplikacji użytej do badań charakterystyk jakościowych:

Po podaniu pożądanej wielkości instancji program generuje ją, a następnie oblicza wartość Cmax w przetwarzaniu algorytmem aproksymacyjnym F^A(I) i samym programowaniu dynamicznym, wyznaczając optimum F^opt(I).

Wyniki badań dla ε = 0, 2

n	F^opt(I)	F^A(I)	$$\eta\left( I \right) = \ \frac{F^{A}\left( I \right) - F^{\text{opt}}(I)}{F^{\text{opt}}(I)}$$	$$\eta\left( I \right) = \ \frac{F^{A}\left( I \right) - F^{\text{opt}}(I)}{F^{\text{opt}}(I)} \bullet 100\%$$
10	161	170	0,055901	5,59%
20	440	448	0,018182	1,82%
30	567	597	0,05291	5,29%
50	817	855	0,046512	4,65%
100	1865	1948	0,044504	4,45%
150	2681	2708	0,010071	1,01%
200	3736	3786	0,013383	1,34%
250	4353	4410	0,013094	1,31%
300	5452	5529	0,014123	1,41%
350	6163	6173	0,001623	0,16%
400	7323	7422	0,013519	1,35%
450	7853	7985	0,016809	1,68%
500	9056	9214	0,017447	1,74%
550	10110	10474	0,036004	3,60%
600	10536	10790	0,024108	2,41%
	$\overset{\overline{}}{\eta}\ $ 0,025213	$\overset{\overline{}}{\eta}$ (w procentach) 2,52%
	η^MAX 0,055901	η^MAX (w procentach) 5,59%

Wyniki badań dla ε = 0, 27

n	F^opt(I)	F^A(I)	$$\eta\left( I \right) = \ \frac{F^{A}\left( I \right) - F^{\text{opt}}(I)}{F^{\text{opt}}(I)}$$	$$\eta\left( I \right) = \ \frac{F^{A}\left( I \right) - F^{\text{opt}}(I)}{F^{\text{opt}}(I)} \bullet 100\%$$
10	151	160	0,059603	5,96%
20	400	421	0,0525	5,25%
30	548	564	0,029197	2,92%
50	881	939	0,065834	6,58%
100	1817	1953	0,074849	7,48%
150	2550	2665	0,045098	4,51%
200	3535	3610	0,021216	2,12%
250	4487	4551	0,014263	1,43%
300	5401	5459	0,010739	1,07%
350	6281	6353	0,011463	1,15%
400	7115	7199	0,011806	1,18%
450	7922	7923	0,000126	0,01%
500	8657	8772	0,013284	1,33%
550	9741	10243	0,051535	5,15%
600	10468	10644	0,016813	1,68%
	$\overset{\overline{}}{\eta}\ $ 0,031888	$\overset{\overline{}}{\eta}$ (w procentach) 3,19%
	η^MAX 0,074849	η^MAX (w procentach) 7,48%

Wyniki badań dla ε = 0, 35

n	F^opt(I)	F^A(I)	$$\eta\left( I \right) = \ \frac{F^{A}\left( I \right) - F^{\text{opt}}(I)}{F^{\text{opt}}(I)}$$	$$\eta\left( I \right) = \ \frac{F^{A}\left( I \right) - F^{\text{opt}}(I)}{F^{\text{opt}}(I)} \bullet 100\%$$
10	237	252	0,063291	6,33%
20	444	465	0,047297	4,73%
30	594	635	0,069024	6,90%
50	869	913	0,050633	5,06%
100	1783	1880	0,054403	5,44%
150	2541	2618	0,030303	3,03%
200	3558	3768	0,059022	5,90%
250	4567	4609	0,009196	0,92%
300	5484	5531	0,00857	0,86%
350	6343	6366	0,003626	0,36%
400	6807	7001	0,0285	2,85%
450	7927	8199	0,034313	3,43%
500	9259	9375	0,012528	1,25%
550	9751	9943	0,01969	1,97%
600	10743	10884	0,013125	1,31%
			$\overset{\overline{}}{\eta}\ $ 0,033568	$\overset{\overline{}}{\eta}$ (w procentach) 3,36%
			η^MAX 0,069024	η^MAX (w procentach) 6,90%

Otrzymane błędy średnie nie przekraczają 3,5% więc można uznać iż algorytm aproksymacyjny jest w miarę dokładny.

Zależność pomiędzy błędem procentowym, a wielkością instancji dla badanych wartości ε obrazuje wykres:

Powyższy wykres pozwala stwierdzić dokładniejsze działanie algorytmu aproksymacyjnego dla wraz ze wzrostem wielkości instancji.

1. Wnioski

Metoda schematu aproksymacyjnego pozwala badać znacznie większe instancje problemu szeregowania na dwóch procesorach, niż metoda programowania dynamicznego. Algorytm FPTAS w tej implementacji staje się również dokładniejszy wraz ze zwiększającym się n. Analiza jakościowa algorytmu dla trzech wartości epsilon wskazała niewysokie średnie błędy aproksymacji, sugerując jego skuteczność. Duża oszczędność czasowa w porównaniu do algorytmu PD oraz dokładność gwarantują wysoką przydatność algorytmu FPTAS przy rozwiązywaniu problemów NP.-trudnych.

Literatura:

1. ftp://sith.ict.pwr.wroc.pl/Informatyka/PEA/aprox_PTASy_FPTASy.pdf

2. Cormen Thomas H., Leiserson Charles E., Rivest Ronald L., Stein Clifford, Wprowadzenie do algorytmów, WNT