Rendszeroptimalizálás, 15. tétel

A VIK Wikiből
A lap korábbi változatát látod, amilyen (vitalap) 2012. október 22., 10:43-kor történt szerkesztése után volt. (Ú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á…”)
(eltér) ← Régebbi változat | Aktuális változat (eltér) | Újabb változat→ (eltér)
Ugrás a navigációhoz Ugrás a kereséshez

Ez az oldal a korábbi SCH wiki-ről lett áthozva. Az eredeti változata itt érhető el.

Ha úgy érzed, hogy bármilyen formázási vagy tartalmi probléma van vele, akkor kérlek javíts rajta egy rövid szerkesztéssel.

Ha nem tudod, hogyan indulj el, olvasd el a migrálási útmutatót


!! 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.

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 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 az algoritmus 2-approximációs.

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

  • Példa*: halmazfedés. Adott U alaphalmaz, S1⊆U, ..., Sn⊆U részhalmazai és c:{Si}→R+ költségfüggvény. Keressük a minimális összköltségű fedést.
  • Algoritmus*:
  • C⊆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).

-- Peti - 2007.01.02.