To tylko jedna z 4 stron tej notatki. Zaloguj się aby zobaczyć ten dokument.
Zobacz
całą notatkę
Optymalizacja:
1. złożone problemy mają bardzo dużą liczbę rozwiązań
2. żeby dojść do rozwiązania musimy często posługiwać się uproszczonym modelem,
który może uniemożliwiać rozwiązanie właściwego problemu
3. warunki problemu zmieniają się w czasie
4. rzeczywiste problemy często mają ograniczenia, które wymagają specjalnych operacji
Metody klasyczne:
algorytmy, które oceniają tylko pełne rozwiązania
algorytmy, które wymagają oceny częściowo skonstruowanych rozwiązań lub
przybliżonych
Algorytmy oceniające rozwiązania pełne:
przeszukiwanie wyczerpujące, przeszukiwanie lokalne oraz metody z zakresu
programowania matematyki.
Zaletą działania na pełnych rozwiązaniach jest fakt, że w przypadku przerwania
algorytmu otrzymuje się jakiekolwiek potencjalne rozwiązanie sformułowanego
problemu
Przeszukiwanie wyczerpujące:
1. Sprawdzanie każdego rozwiązania w przestrzeni rozwiązań
2. Wybór globalnie najlepszego rozwiązania, nie jest ważna kolejność generowania
rozwiązań
3. Całkowita przestrzeń rozwiązań jest olbrzymia
4. Duża pracochłonność poszukiwań
Przeszukiwanie lokalne:
1. Przeszukiwanie części przestrzeni rozwiązań
2. Mniejsza czasochłonność poszukiwań
3. Istotny wpływ na kierunek poszukiwań ma postać przekształcenia bieżącego
rozwiązania
4. Pułapka „lokalnego optimum”
Metody optymalizacji dla rozwiązań częściowych:
1. Algorytmy zachłanne
2. Dziel i rządź
3. Programowanie dynamiczne
4. Metoda podziału i ograniczeń
5. Algorytm A*
Ad1. Algorytm tworzy pełne rozwiązania za pomocą ciągu kroków
- prostota – należy przypisywać wartość wszystkim zmiennym problemu podejmując
najlepszą decyzję
- podejmowanie najlepszej decyzji w każdym z poszczególnych kroków nie zawsze prowadzi
do optymalnego rozwiązania
Ad2. Dziel i rządz – polega na podziale problemu na mniejsze części i ich rozwiązaniu
- podejście jest efektywne, jeśli czas i wysiłek potrzebny na wykonie podziału, obliczeń i
założenie odpowiedzi jest mniejszy niż rozwiązanie pierwotnej postaci modelu
- nie zawsze jest możliwie założenie pełnego rozwiązanie po dokonaniu podziału na mniejsze
części
Ad.3. Prognozowanie dynamiczne – algorytm znajduje pełne rozwiązanie na podstawie
pośredniego punktu pomiędzy punktem bieżącym a celem
- algorytm znajduje rozwiązanie problemów, dla których zawodzą algorytmy zachłanne
- często duża złożoność obliczeniowa, algorytmy niekiedy trudne do zrozumienia, bowiem ich
konstrukcja zależy od specyfiki problemu
Ad4. Metoda podziału i ograniczeń – algorytm korzysta z określonej koncepcji dzielenia
przestrzeni przeszukiwania
- szybkość algorytmu uzyskuje się dzięki odpowiednio wprowadzonym ograniczeniom
- konieczność określenia dolnego lub górnego ograniczenia poszczególnych rozwiązań
- przegląd przestrzeni rozwiązań należy odpowiednio ukierunkować
Ad5. Algorytm A* - działa na grafach o różnej strukturze, główna koncepcja – najpierw
najlepszy
- algorytm korzysta z dwóch list wierzchołków otwartych i zamkniętych, przeszukiwanie bada
najbardziej obiecujący wierzchołek
... zobacz całą notatkę
Komentarze użytkowników (0)