Algorytm zachłanny, programowanie dynamiczne (Materiały pomocnicze) PDF

Preview

Summary

Krzysztof Ostrowski...

Description

Algorytmy zachłanne i programowanie dynamiczne Algorytm zachłanny – algorytm, który na każdym etapie działania dokonuje wyboru lokalnie optymalnego w celu uzyskania globalnie najlepszego rozwiązania. Mają one zastosowania w wielu różnych problemach. Ich zaletą jest zwykle prostota i niska złożoność czasowa. Ich implementacja często wymaga zastosowania sortowania lub kolejek priorytetowych. Istnieje wiele znanych algorytmów opartych o strategię zachłanną (np. algorytm Dijkstry, algorytm Kruskala, kodowanie Huffmana). Jednak algorytmy zachłanne znajdują globalnie optymalne rozwiązanie tylko dla niektórych problemów (posiadających własność wyboru zachłannego). W przypadku innych lepiej użyć innej techniki (jak np. programowanie dynamiczne).

Problem maksymalnego wypełnienia przyczepy Mamy daną przyczepę o maksymalnej ładowności w kilogramów oraz n przedmiotów o całkowitych masach m1, m2, m3, ..., mn kilogramów. Należy tak wybrać przedmioty, by załadować przyczepę możliwie najpełniej (ale bez przekraczania limitu w kilogramów), a przy tym użyć jak najmniej przedmiotów. W tym klasycznym problemie optymalizacyjnym mamy do czynienia z dużą przestrzenią rozwiązań – liczba podzbiorów rośnie wykładniczo od liczby przedmiotów. W związku z tym podejście siłowe (brute-force) przeszukujące wszystkie możliwe rozwiązania będzie bardzo niewydajne już przy kilkudziesięciu przedmiotach. Zależnie od wariantu można rozwiązać ten problem w inny sposób. Wariant 1 – masy przedmiotów są potęgami dwójki Przykład: w=13 //ładowność wynosi 13 kg n=7 //mamy 7 przedmiotów M={16, 4, 8, 1, 4, 2, 2} //masy kolejnych przedmiotów Gdy przedmioty są potęgami dwójki można zastosować szybki i prosty algorytm zachłanny, który tutaj zawsze daje optymalne rozwiązanie. Najpierw należy posortować przedmioty po ich masach: 16, 8, 4, 4, 2, 2, 1

//do załadowania 13 kg

A następnie poczynając od najcięższego przedmiotu po kolei sprawdzać, który przedmiot się zmieści w przyczepie. Pierwszym takim przedmiotem jest ten o wadze 8 kg. Ładujemy go do przyczepy i zostaje nam jeszcze 5 kg do załadowania: 16, 8, 4, 4, 2, 2, 1

//do załadowania zostało 5 kg

Idziemy dalej po coraz mniejszych przedmiotach i analogicznie stwierdzamy, że możemy jeszcze zmieścić przedmiot o wadze 4 kg. Jest on ładowany do przyczepy i zostaje jeszcze wolny kilogram: 16, 8, 4, 4, 2, 2, 1

//do załadowania został 1 kg

Na koniec przeszukujemy najlżejsze przedmioty i znajdujemy jeszcze jeden, który można załadować (ten o masie kilograma). Przyczepa jest więc pełna przy użyciu tylko 3 przedmiotów (o masach 8, 4 i 1 kg). Zauważmy, że nie zawsze da się załadować przyczepę do pełna: w=13 //ładowność wynosi 13 kg n=7 //mamy 7 przedmiotów M={16, 4, 8, 4, 2, 2, 4} //masy kolejnych przedmiotów W tym przypadku rozwiązanie optymalne to załadowanie 12 kg za pomocą 2 przedmiotów (8+4).

Wariant 2 – masy przedmiotów są dowolnymi liczbami całkowitymi Przykład: w=12 n=7 M={4, 7, 11, 2, 3, 5, 6} W tym przypadku zastosowanie algorytmu zachłannego prowadzi do załadowania 11 kg (tylko 1 przedmiotem). Tymczasem da się tak wybrać przedmioty, by załadować przyczepę do pełna (czyli 12 kg) - można to nawet zrobić na kilka sposobów, ale tylko jeden będzie optymalny (ten wymagający najmniejszej liczby przedmiotów). Które to przedmioty? W tej sytuacji lepiej jest zastosować programowanie dynamiczne. Programowanie dynamiczne – metoda rozwiązywania złożonych problemów optymalizacyjnych. Polega ona na dzieleniu większego problemu na mniejsze podproblemy (analogia do „dziel i zwyciężaj”), które w tym przypadku mogą się powtarzać. Liczba podproblemów może być bardzo duża (może rosnąć np. wykładniczo) – aby uniknąć ich wielokrotnego liczenia przechowujemy ich rozwiązania w pamięci komputera. Aby uniknąć rekurencji możemy rozwiązywać podproblemy od najmniejszych do coraz większych – wówczas przy rozwiązywaniu podproblemów większych korzystamy z obliczonych wcześniej i zapamiętanych rozwiązań mniejszych podproblemów. Ta technika może dawać optymalne wyniki w rozsądnym czasie nawet dla problemów trudnych obliczeniowo – dzięki niej ze złożoności wykładniczej można zejść do pseudowielomianowej. Istnieje sporo algorytmów opartych o technikę programowania dynamicznego (np. algorytm Floyda-Warshalla czy algorytm znajdywania najdłuższego wspólnego podciągu dwóch ciągów). Często największą trudnością przy konstruowaniu rozwiązań opartych o programowanie dynamiczne jest znalezienie rekurencyjnej formuły podziału problemu na podproblemy. Najprostszym przykładem użycia programowania dynamicznego jest algorytm znalezienia n-tej liczby Fibonacciego: F(0)=0 F(1)=1 F(n)=F(n-1)+F(n-2) Prosta metoda rekurencyjna jest niewydajna, gdyż liczy te same podproblemy wiele razy: F(6) F(5) F(4)

F(3) F(3) F(2) F(2) F(1) F(2) F(1) F(1) F(0) F(1) F(0) F(1) F(0)

F(4) F(3) F(2) F(2) F(1) F(1) F(0) F(1) F(0)

Liczba węzłów w drzewie wywołań rekurencyjnych rośnie wykładniczo, a więc jest to rozwiązanie bardzo niewydajne. Zamiast tego można obliczać kolejne wyrazy Fibonacciego od najmniejszych i zapamiętywać w tablicy kolejne wyniki: F[0]=0;F[1]=1; for(int i=2;i1 i mn>w Jeżeli nasz n-ty przedmiot jest za ciężki dla przyczepy, to go nie bierzemy i sprowadzamy problem do pozostałych przedmiotów. 4) P(w, n)=P(w, n-1) lub P(w, n)=P(w-mn, n-1)+1 jeżeli n>1 i mn...