Rendszeroptimalizálás, 17. tétel

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

!! 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 2^1/εn⁴, 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_ = {a₁, a₂, ..., a_n} és _t_.
Kérdés: létezik-e B⊆A úgy, hogy Σb_i = _t_?
Speciális eset: partíció probléma, amikor _t_ = Σa_i/2, még ez is NP-teljes.

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

Adott _A_ = {a₁, a₂, ..., a_n} és _t_.
Keressük B⊆A-t úgy, hogy Σb_i maximális és Σb_i ≤ _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 Σb_i = _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 a₁ ≤ a₂ ≤ ... ≤ a_n. Definiálunk két halmazsorozatot:
   • L₀ = {0}
   • L_i' = {l+a_i | l∈L_i}
   • L_i+1 = L_i ∪ L_i'
   Röviden: L_i+1 = L_i ∪ (L_i+a_i+1) Például:
   • a₁=3, a₂=5, a₃=7
   • L₀ = {0}
   • L₀' = {3}, L₁ = {0,3}
   • L₁' = {5,8}, L₂ = {0,3,5,8}
   • L₂' = {7,10,12,15}, L₃ = {0,3,5,7,8,10,12,15}
   Az optimális részletösszeg max{l|l∈L_n ∧ l≤t} lesz.
2. Polinomiális közelítő algoritmus: Egyrészt vegyük észre, hogy az L_i' halmazokból nincs szükségünk a t-nél nagyobb elemekre. Képezzük a halmazokat a következő módon: L_i' = (L_i+a_i) ∩ [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ő: |L_ritkított ≤ log_1+δ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.
   [math] \forall i \: |L_i| \le \log_{1+\frac{\epsilon}{2n}}t+2 = \frac{\ln t}{\ln (1+\frac{\epsilon}{2n})}+2 = O(\log t) [/math] 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: [math] \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 [/math] Az algoritmus során n db lista összefésülést kell végezni, aminek a komplexitása O(∑|L_i||) = O(n||L_i||). A fenti becslések alapján látszik, hogy O(n||L_i) 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.