BB_DP.pdf
(
346 KB
)
Pobierz
Optymalizacja. Algorytmy dokładne
dr in». Maciej Komosi«ski
InstytutInformatyki
PolitechnikaPozna«ska
www.cs.put.poznan.pl/mkomosinski
'
MaciejKomosi«ski,MaciejHapke
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
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
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
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
Plik z chomika:
comp.prog1
Inne pliki z tego folderu:
BB_DP.pdf
(346 KB)
algo_wyk8.pdf
(300 KB)
BranchAndBound.ppt
(217 KB)
mow10.pdf
(198 KB)
sprawozdanie.doc
(159 KB)
Inne foldery tego chomika:
Zgłoś jeśli
naruszono regulamin