Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel15}} ==!! Additív hibával közelítő algoritmus fogalma, példák. Relatív hibával közelítő algoritmusok, példák: minimá…”

2012-10-22T09:43:41Z

Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel15}} ==!! Additív hibával közelítő algoritmus fogalma, példák. Relatív hibával közelítő algoritmusok, példák: minimá…”

Új lap

{{GlobalTemplate|Infoszak|RopiTetel15}}

==!! Additív hibával közelítő algoritmus fogalma, példák. Relatív hibával közelítő algoritmusok, példák: minimális lefogó ponthalmaz, halmazfedés.==

__TOC__

===Additív hibával közelítő algoritmus===

*Def.*: egy algoritmus C additív hibával közelítve old meg egy minimalizálási problémát, ha minden I inputra polinomiális időben ad egy yI-t, amire
<math> f(y_I) \le \min\limits_{x \in X_I} f(x)+C </math>
vagy
<math> f(y_I) \ge \max\limits_{x \in X_I} f(x)-C </math>
maximalizálási probléma esetén.

*Példák*:
* Élkromatikus szám keresése. A Vizing-tétel szerint Δ(G)≤χe(G)≤Δ(G)+1, és a bizonyítás algoritmikus.
* Síkbarajzolható gráfok színezése. Polinom időben eldönthető, hogy színezhető-e 2 színnel. A színezés 3 színnel NP-teljes, 4 színnel nem ismert (a négyszíntétel bizonyítása nem algoritmikus). 5 színnel minden gráf színezhető polinomiális idő alatt <big>⇒</big> létezik 2 additív hibával közelítő algoritmus a problémára.

*Lemma*: van olyan probléma, ami nem közelíthető additív konstanssal.
*Biz*: leghosszabb kör keresése C hibával visszavezethető a Hamilton-kör keresésére úgy, hogy a G gráf minden élét C+1-felé bontjuk. A kapott G'-ben ha a közelítő algoritmus talál |V(C+1) hosszú kört, G-ben volt Hamilton-kör, különben nem.

===Multiplikatív hibával közelítő algoritmus===

*Def.*: egy algoritmus k-approximációs, ha egy minimalizálási probléma minden I inputjára polinom időben ad egy yI megoldást, amire
<math> f(y_I) \le k \min\limits_{x \in X_I} f(x) </math>

*Példa*: τ(G) minimális lefogó ponthalmaz keresése: egy nem bővíthető párosítás éleinek vesszük a végpontjait. τ(G)≥ν(G) és ≤2ν(G) méretű megoldást találtunk <big>⇒</big> az algoritmus 2-approximációs.

===Függvény hibával közelítő algoritmus===

*Példa*: halmazfedés. Adott U alaphalmaz, S1&sube;U, ..., Sn&sube;U részhalmazai és c:{Si}→R+ költségfüggvény. Keressük a minimális összköltségű fedést. 
*Algoritmus*:
* C&sube;U az U halmazból már lefedett elemek részhalmaza.
* while (C!=U) válasszuk azt az Si halmazt, amire c(Si)/|Si-C minimális.
*Lemma*: legyen p(e)=c(Si)/|Si-C||, ahol Si az a halmaz, ami az algoritmus során először fedte le e-t. e1, ..., em (m=||U) az elemek az algoritmus során kapott lefedési sorrendben. p(ek)≤OPT/(m-k+1). 
*Biz.*: ∑p(e) = fedés összköltsége. Mivel az algoritmus mindig a minimális c(Si)/|Si-C értékű halmazt választja, 
p(ek) = c(Si)/|Si-C|| ≤ OPT/||C = OPT/(m-k+1) 
*Köv.*: a fedés költsége ≤ OPT/1+OPT/2+...+OPT/m < OPT*ln(m).

-- [[PallosPeter|Peti]] - 2007.01.02.

[[Category:Infoszak]]

Rendszeroptimalizálás, 15. tétel - Laptörténet

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel15}} ==!! Additív hibával közelítő algoritmus fogalma, példák. Relatív hibával közelítő algoritmusok, példák: minimá…”