To tylko jedna z 3 stron tej notatki. Zaloguj się aby zobaczyć ten dokument.
Zobacz
całą notatkę
ALGORYTMY PRZYBLIŻONE
Analiza
Analiza eksperymentalna - wygenerowanie pewnego zbioru X instancji badanego problemu Π oraz rozwiązanie wszystkich tych instancji badanym algorytmem A
Ocena jakości algorytmu - Średnia odległość od optimum, maksymalna odległość od optimum Analiza probabilistyczna
Analiza najgorszego przypadku
Współczynnik osiągalności aproksymacyjnej - współczynnik najgorszego przypadku dla problemu Π opisany wzorem: Schematy aproksymacyjne
PTAS - wielomianowe schematy aproksymacyjne
FPTAS - w pełni wielomianowe schematy aproksymacyjne
Zakres stosowalności
... zobacz całą notatkę
Komentarze użytkowników (0)