95921

c) Analiza najgorszego przypadku

Dodatkowo, definiuje się współczynnik

którego definicja jest taka sama jak dla R_A z tą różnicą, że oszacowaniu podlega nie cały zoiór instancji, ale podzoiór:

= {/€*>*: i-^ł(J)> M), gezie W jest pewną stałą.

Innymi słowy. D* jest zoiorem takich instancji problemu w, dla których wartość optymalna Jest większa niż pewna stała W > O W tej analizie oszacowaniu podlega cały zbiór instancji problemu jt. czyli D_w. W analizie tej. ze zbioru D-, wybiera się taką instancję I. dla której współczynnik

X_A(0 =

F\I)

r*U)

lub r_aW =

*»(/)

przyjmuje wartość maksymalną.

Ola tej instancji współczynnik ten oznacza się przez Ra i nazywa się współczynnikiem najgorszego przypadku algorytmu A.

Współczynnik nazywa się asymptotycznym współczynnikiem najgorszego przypadku algorytmu A.

d) Współczynnik osiągalności aproksymacyjnej - współczynnik najgorszego przypadku dla problemu fi opisany wzorem:

Możemy wyróżnić trzy typy problemów, ze względu na wartości współczynnika R_w:

1. R_n = l + e dla t -0, 2. R_m = 1 + « dla e .> 0, 3. R_m = oc.

Rn = min-{/*x : A rozwiązuje n w czasie wielomianowym}

Vj4

Najlepszą sytuacją jest 1. bo oznacza, że możemy rozwiązać problem z dowolnie małym błędem w wielomianowym czasie (oczywiście stopień tego wielomianu rośnie wraz ze zmniejszaniem sk; błędu c).

Sytuacja 2. mówi, że nie można w wiełorma nowym czasie osiągnąć rozwiązania gwarantującego błąd mniejszy niż e.

Sytuacja 3. Jest najgorsza, Do ockazuje. że nie możemy skonstruować algorytmu wlelomłanowego dającego Jakikolwiek błąd orzyDizenia.

2. Schematy aproksymacyjne

Schemat aproksymacyjny - rodzina algorytmów {4.-} taka, że dla każdego * > O algorytm 4_f dostarcza rozwiązania problemu z błędem nie większym nIZ r. czyli dla problemu ekstremaiizacji funkcji K (r). r t X. mamy

* <tK",

gdzie K~ jest wartością optymalną funkcji K. a K^A’ jest wartością funkcji K dla rozwiązania dostarczonego przez algorytm Ac.