ZADANIE 4 (zadanie nr 2 dla studiów zaocznych).
Celem ćwiczenia jest przybliżenie pojęcia algorytmu dokładnego i przybliżonego, zapoznanie się ze sposobem przeprowadzania eksperymentalnej oceny dokładności algorytmu przybliżonego oraz eksperymentalnej analizy efektywności algorytmów.
Należy:
•
Napisać i uruchomić program realizujący rozwiązywanie zagadnienia plecakowego za pomocą 3
algorytmów: zachłannego (AZ), programowania dynamicznego (APD) i generującego wszystkie podzbiory zbioru n-elementowego (AP).
•
Porównać wyniki (wartości maksymalnego zysku) uzyskane za pomocą poszczególnych algorytmów (dla danych zamieszczonych w tabeli).
•
Wyznaczyć względne odchylenie od wartości optymalnych rozwiązań uzyskanych za pomocą algorytmu zachłannego (AZ).
•
Porównać czasy wykonywania obliczeń przez poszczególne algorytmy.
•
Wyprowadzić wnioski.
Uwaga: obliczenia przeprowadzić dla wartości i generowanych z przedziału [1,10].
Dla chętnych: uzupełnić podane implementacje o możliwość wyświetlania zbioru projektów wybranego do realizacji.
Tabela 1. Wartości maksymalnego zysku uzyskiwane przez poszczególne algorytmy n
b
AZ
APD
AP
5
5
10
10
15
15
20
20
25
25
30
30
100
100
100
5000
1000
1000
1000
50000
10000
10000
10000
50000
Tabela 2. Względne odchylenie od optimum, , dla AZ
n
b
[%]
n
b
[%]
5
5
100
100
10
10
100
500
15
15
1000
1000
20
20
1000
5000
25
25
10000
10000
30
30
10000
50000
średnio:
średnio:
Tabela 3. Czasy wykonywania obliczeń przez poszczególne algorytmy w sekundach n
b
AZ
APD
AP
5
5
10
10
15
15
20
20
25
25
30
30
100
100
100
500
1000
1000
1000
5000
10000
10000
10000
50000
Wnioski: