BB_DP.pdf

(346 KB) Pobierz
Optymalizacja. Algorytmy dokładne
dr in». Maciej Komosi«ski
InstytutInformatyki
PolitechnikaPozna«ska
' MaciejKomosi«ski,MaciejHapke
929936147.004.png 929936147.005.png 929936147.006.png
Definicje
Algorytmy
Problem optymalizacji kombinatorycznej
Problem optymalizacji kombinatorycznej jest problemem
minimalizacji b¡d¹ maksymalizacji i charakteryzuje si¦
zbiorem instancji
Instancja jest par¡ ( S ; f )
S oznacza sko«czony zbiór wszystkich mo»liwych rozwi¡za«
f jest odwzorowaniem definiowanym jako
f : S ! R
Maciej Komosi«ski
Optymalizacja. Algorytmy dokładne
929936147.007.png
Definicje
Algorytmy
Minimalizacja
W przypadku minimalizacji nale»y znale¹¢ takie rozwi¡zanie
i opt 2 S które spełnia
f ( i opt ) f ( i ) dla wszystkich i 2 S
Maciej Komosi«ski
Optymalizacja. Algorytmy dokładne
929936147.001.png
Definicje
Algorytmy
Maksymalizacja
W przypadku maksymalizacji nale»y znale¹¢ takie rozwi¡zanie
i opt 2 S które spełnia
f ( i opt ) f ( i ) dla wszystkich i 2 S
Takie rozwi¡zanie i opt jest globalnie optymalne (minimalne lub
maksymalne)
Maciej Komosi«ski
Optymalizacja. Algorytmy dokładne
929936147.002.png
Definicje
Algorytmy
Klasyfikacja Algorytmów
algorytmy optymalizacyjne dokładne
przeszukiwanie wyczerpuj¡ce (exhaustive)
programowanie matematyczne
podziału i ogranicze« (B&B)
programowanie dynamiczne
algorytmy heurystyczne
specjalizowane
losowego przeszukiwania (random search)
lokalnego przeszukiwania i odmiany
symulowanewy»arzanie
przeszukiwanietabu
ewolucyjne
hybrydy
Maciej Komosi«ski
Optymalizacja. Algorytmy dokładne
929936147.003.png

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin