Rendszeroptimalizálás, 17. tétel

A VIK Wikiből
(RopiTetel17 szócikkből átirányítva)

Polinomiális approximációs séma a RÉSZÖSSZEG problémára

Polinomiális approximációs séma

  • Def.*: egy probléma polinomiális approximációs sémával közelíthető, ha ∀ε>0-ra van rá (1+ε)-approximáció.

Ez nem mindig elég, mert ha a közelítő algoritmus lépésszáma 21/εn4, még mindig exponenciálisan hosszú ideig fut.

  • Def.*: egy probléma teljesen polinomiális approximációs sémával közelíthető, ha ∀ε>0-ra van rá (1+ε)-approximáció, ami 1/ε-ban is polinomiális.
  • Pl.*: a metrikus utazó ügynök problémára nincs P approximációs séma, de az euklideszi utazó ügynök problémára van teljesen P approximációs séma.

Részösszeg probléma

Adott _A_ = {a1, a2, ..., an} és _t_.
Kérdés: létezik-e BA úgy, hogy Σbi = _t_?
Speciális eset: partíció probléma, amikor _t_ = Σai/2, még ez is NP-teljes.

Részösszeg optimalizálási probléma

Adott _A_ = {a1, a2, ..., an} és _t_.
Keressük BA-t úgy, hogy Σbi maximális és Σbi ≤ _t_ legyen.
A feladat NP nehéz, mert a részösszeg probléma visszavezethető rá. Bizonyítás: ha találunk olyan a _B_ halmazt, amire Σbi = _t_, akkor igen a válasz a részösszeg problémára, különben nem.
A feladat nem NP-beli, mert nem eldöntési probléma, tehát nem is NP-teljes.

Közelítő algoritmus a részösszeg optimalizálási problémára

  • Tétel*: a probléma teljesen polinomiális sémával közelíthető.

A bizonyítás egy konkrét algoritmus lesz:

  1. Pontos megoldást adó algoritmus: Tegyük fel, hogy a1a2 ≤ ... ≤ an. Definiálunk két halmazsorozatot:
    • L0 = {0}
    • Li' = {l+ai | lLi}
    • Li+1 = LiLi'
    Röviden: Li+1 = Li ∪ (Li+ai+1) Például:
    • a1=3, a2=5, a3=7
    • L0 = {0}
    • L0' = {3}, L1 = {0,3}
    • L1' = {5,8}, L2 = {0,3,5,8}
    • L2' = {7,10,12,15}, L3 = {0,3,5,7,8,10,12,15}
    Az optimális részletösszeg max{l|lLn lt} lesz.
  2. Polinomiális közelítő algoritmus: Egyrészt vegyük észre, hogy az Li' halmazokból nincs szükségünk a t-nél nagyobb elemekre. Képezzük a halmazokat a következő módon: Li' = (Li+ai) ∩ [0..t]. Def.: δ-val ritkítás
    <i>L</i> növekvő sorrendbe rendezett halmaz.
    foreach (l'''∈L''') {
    	''m'' az ''l''-et megelőző, halmazban hagyott elem, vagy ha nincs ilyen, 0.
    	if (''l''lt;m(1+''δ'')) ''l''-et kidobjuk.
    }

    A ritkítás után bármely két szomszédos elem hányadosa legalább 1+δ. A ritkított halmaz mérete felülről becsülhető: |Lritkított ≤ log1+δt+2.

  3. *Tétel*: ha az algoritmus során a halmazok t-nél nagyobb elemeit minden lépésben levágjuk és az eredményt δ=ε/2n-vel ritkítjuk, (1+ε)-approximációt kapunk a problémára, és a lépésszám n-ben, log t-ben és 1/ε-ban is polinomiális lesz.
    • Biz.*: az algoritmus (1+ε)-approximációs. %P%
    • Biz.*: az algoritmus lépésszáma mindhárom mennyiség szerint polinomiális.
    Értelmezés sikertelen (formai hiba): {\displaystyle \forall i \: |L_i| \le \log_{1+\frac{\epsilon}{2n}}t+2 = \frac{\ln t}{\ln (1+\frac{\epsilon}{2n})}+2 = O(\log t) } Másrészt az x≥-1-re érvényes x/(1+x) ≤ ln(1+x) összefüggést kihasználva x=ε/2n helyettesítéssel: Értelmezés sikertelen (formai hiba): {\displaystyle \forall i \: |L_i| \le \frac{\ln t}{\ln (1+\frac{\epsilon}{2n})}+2 \le \frac{(1+\epsilon/2n) \ln t}{\epsilon/2n}+2 = \frac{(2n+\epsilon) \ln t}{\epsilon}+2 } Az algoritmus során n db lista összefésülést kell végezni, aminek a komplexitása O(∑|Li||) = O(n||Li||). A fenti becslések alapján látszik, hogy O(n||Li) n-ben négyzetes, log(t)-ben lineáris, tehát mindkettőben polinomiális. Az 1/ε szerinti becslést órán lenyeltük. %P%

-- Peti - 2006.12.18.