Rendszeroptimalizálás, 17. tétel forrásának megtekintése

==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 &forall;&epsilon;>0-ra van rá (1+&epsilon;)-approximáció. 
Ez nem mindig elég, mert ha a közelítő algoritmus lépésszáma 2<sup>1/&epsilon;</sup>n<sup>4</sup>, még mindig exponenciálisan hosszú ideig fut. <br>
*Def.*: egy probléma teljesen polinomiális approximációs sémával közelíthető, ha &forall;&epsilon;>0-ra van rá (1+&epsilon;)-approximáció, ami 1/&epsilon;-ban is polinomiális. <br>
*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_ = {<i>a</i><sub>1</sub>, <i>a</i><sub>2</sub>, ..., <i>a<sub>n</sub></i>} és _t_. <br>
Kérdés: létezik-e <i>B</i>&sube;<i>A</i> úgy, hogy &Sigma;<i>b<sub>i</sub></i> = _t_? <br>
Speciális eset: partíció probléma, amikor _t_ = &Sigma;<i>a<sub>i</sub></i>/2, még ez is NP-teljes.

===Részösszeg optimalizálási probléma===
Adott _A_ = {<i>a</i><sub>1</sub>, <i>a</i><sub>2</sub>, ..., <i>a<sub>n</sub></i>} és _t_. <br>
Keressük <i>B</i>&sube;<i>A</i>-t úgy, hogy &Sigma;<i>b<sub>i</sub></i> maximális és &Sigma;<i>b<sub>i</sub></i> &le; _t_ legyen. <br>
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 &Sigma;<i>b<sub>i</sub></i> = _t_, akkor igen a válasz a részösszeg problémára, különben nem. <br>
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:
<ol>
<li>Pontos megoldást adó algoritmus:

Tegyük fel, hogy <i>a</i><sub>1</sub> &le; <i>a</i><sub>2</sub> &le; ... &le; <i>a<sub>n</sub></i>.
Definiálunk két halmazsorozatot:
* <i>L</i><sub>0</sub> = {0}
* <i>L<sub>i</sub></i>' = {<i>l</i>+<i>a<sub>i</sub></i> | <i>l</i><big>&isin;</big><i>L<sub>i</sub></i>}
* <i>L</i><sub><i>i</i>+1</sub> = <i>L<sub>i</sub></i> &cup; <i>L<sub>i</sub></i>'
Röviden: <i>L</i><sub><i>i</i>+1</sub> = <i>L<sub>i</sub></i> &cup; (<i>L<sub>i</sub></i>+<i>a</i><sub><i>i</i>+1</sub>)

Például:
* <i>a</i><sub>1</sub>=3, <i>a</i><sub>2</sub>=5, <i>a</i><sub>3</sub>=7
* <i>L</i><sub>0</sub> = {0}
* <i>L</i><sub>0</sub>' = {3}, <i>L</i><sub>1</sub> = {0,3}
* <i>L</i><sub>1</sub>' = {5,8}, <i>L</i><sub>2</sub> = {0,3,5,8}
* <i>L</i><sub>2</sub>' = {7,10,12,15}, <i>L</i><sub>3</sub> = {0,3,5,7,8,10,12,15}

Az optimális részletösszeg max{<i>l</i>|<i>l</i><big>&isin;</big><i>L<sub>n</sub></i> <big>&and;</big> <i>l</i>&le;<i>t</i>} lesz.

<li>Polinomiális közelítő algoritmus:

Egyrészt vegyük észre, hogy az <i>L<sub>i</sub></i>' halmazokból nincs szükségünk a <i>t</i>-nél nagyobb elemekre. Képezzük a halmazokat a következő módon: <i>L<sub>i</sub></i>' = (<i>L<sub>i</sub></i>+<i>a<sub>i</sub></i>) &cap; [0..<i>t</i>].

Def.: &delta;-val ritkítás
<pre><i>L</i> növekvő sorrendbe rendezett halmaz.
foreach (l'''&isin;L''') {
	''m'' az ''l''-et megelőző, halmazban hagyott elem, vagy ha nincs ilyen, 0.
	if (''l''lt;m(1+''&delta;'')) ''l''-et kidobjuk.
}</pre>

A ritkítás után bármely két szomszédos elem hányadosa legalább 1+<i>&delta;</i>. A ritkított halmaz mérete felülről becsülhető: |<i>L</i><sub>ritkított</sub> &le; log<sub>1+<i>&delta;</i></sub><i>t</i>+2.

<li> *Tétel*: ha az algoritmus során a halmazok <i>t</i>-nél nagyobb elemeit minden lépésben levágjuk és az eredményt <i>&delta;</i>=<i>&epsilon;</i>/2<i>n</i>-vel ritkítjuk, (1+<i>&epsilon;</i>)-approximációt kapunk a problémára, és a lépésszám <i>n</i>-ben, log <i>t</i>-ben és 1/<i>&epsilon;</i>-ban is polinomiális lesz.

*Biz.*: az algoritmus (1+<i>&epsilon;</i>)-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&ge;-1-re érvényes x/(1+x) &le; ln(1+x) összefüggést kihasználva x=&epsilon;/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(&sum;|L<sub>i</sub>||) = O(n||L<sub>i</sub>||). A fenti becslések alapján látszik, hogy O(n||L<sub>i</sub>) n-ben négyzetes, log(t)-ben lineáris, tehát mindkettőben polinomiális. Az 1/&epsilon; szerinti becslést órán lenyeltük. %P%
</ol>

-- [[PallosPeter|Peti]] - 2006.12.18.

[[Category:InfoMsc]]