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

Szikszayl, 2014. március 13., 12:49-n

2014-03-13T12:49:34Z

← Régebbi változat		A lap 2014. március 13., 14:49-kori változata
75. sor:		75. sor:
	-- [[PallosPeter\|Peti]] - 2006.12.18.		-- [[PallosPeter\|Peti]] - 2006.12.18.

	[[~~Category~~:~~InfoMsc~~]]		[[Kategória:Mérnök informatikus MSc]]

Szikszayl, 2013. október 16., 12:43-n

2013-10-16T12:43:26Z

← Régebbi változat		A lap 2013. október 16., 14:43-kori változata
1. sor:		1. sor:
	~~{{GlobalTemplate\|Infoszak\|RopiTetel17}}~~		==Polinomiális approximációs séma a RÉSZÖSSZEG problémára==


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

	~~__TOC__~~

	~~===[http://info.sch.bme.hu/document.php?cmd=download_proc&tmp_page=&doc_id=17258 Szkennelt leírás és bizonyítás az infositeon]=~~==

	===Polinomiális approximációs séma===		===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ó.		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<sup>1/ε</sup>n<sup>4</sup>, még mindig exponenciálisan hosszú ideig fut. <br>		Ez nem mindig elég, mert ha a közelítő algoritmus lépésszáma 2<sup>1/ε</sup>n<sup>4</sup>, még mindig exponenciálisan hosszú ideig fut. <br>
16. sor:		7. sor:

	===Részösszeg problé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>		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 Σ<i>b<sub>i</sub></i> = _t_? <br>		Kérdés: létezik-e <i>B</i>&sube;<i>A</i> úgy, hogy Σ<i>b<sub>i</sub></i> = _t_? <br>
22. sor:		12. sor:

	===Részösszeg optimalizálási probléma===		===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>		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 Σ<i>b<sub>i</sub></i> maximális és Σ<i>b<sub>i</sub></i> ≤ _t_ legyen. <br>		Keressük <i>B</i>&sube;<i>A</i>-t úgy, hogy Σ<i>b<sub>i</sub></i> maximális és Σ<i>b<sub>i</sub></i> ≤ _t_ legyen. <br>
29. sor:		18. sor:

	===Közelítő algoritmus a részösszeg optimalizálási problémára===		===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ő.		Tétel: a probléma teljesen polinomiális sémával közelíthető.

87. sor:		75. sor:
	-- [[PallosPeter\|Peti]] - 2006.12.18.		-- [[PallosPeter\|Peti]] - 2006.12.18.

			[[Category:InfoMsc]]
	[[Category:~~Infoszak~~]]

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

2013-04-24T15:16:13Z

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

← Régebbi változat		A lap 2013. április 24., 17:16-kori változata
58. sor:		58. sor:
	Def.: δ-val ritkítás		Def.: δ-val ritkítás
	<pre><i>L</i> növekvő sorrendbe rendezett halmaz.		<pre><i>L</i> növekvő sorrendbe rendezett halmaz.
	foreach (~~<i>~~l~~</i><big>~~∈~~</big><i>~~L~~</i>~~) {		foreach (l'''∈L''') {
	~~<i>~~m~~</i>~~ az ~~<i>~~l~~</i>~~-et megelőző, halmazban hagyott elem, vagy ha nincs ilyen, 0.		''m'' az ''l''-et megelőző, halmazban hagyott elem, vagy ha nincs ilyen, 0.
	if (~~<i>~~l~~</i>&~~lt;m(1+~~<i>~~δ~~</i>~~)) ~~<i>~~l~~</i>~~-et kidobjuk.		if (''l''lt;m(1+''δ'')) ''l''-et kidobjuk.
	}</pre>		}</pre>

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel17}} ==!! Polinomiális approximációs séma a =RÉSZÖSSZEG= problémára.== TOC ===[http://info.sch.bme.hu/document.php?cm…”

2012-10-22T09:43:46Z

Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel17}} ==!! Polinomiális approximációs séma a =RÉSZÖSSZEG= problémára.== __TOC__ ===[http://info.sch.bme.hu/document.php?cm…”

Új lap

{{GlobalTemplate|Infoszak|RopiTetel17}}

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

__TOC__

===[http://info.sch.bme.hu/document.php?cmd=download_proc&tmp_page=&doc_id=17258 Szkennelt leírás és bizonyítás az infositeon]===

===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 B&sube;A ú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 B&sube;A-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:
<ol>
<li>Pontos megoldást adó algoritmus:

Tegyük fel, hogy a1 ≤ a2 ≤ ... ≤ an.
Definiálunk két halmazsorozatot:
* L0 = {0}
* Li' = {l+ai | l<big>∈</big>Li}
* Li+1 = Li ∪ Li'
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|l<big>∈</big>Ln <big>&and;</big> l≤t} lesz.

<li>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
<pre>L növekvő sorrendbe rendezett halmaz.
foreach (l<big>∈</big>L) {
m az l-et megelőző, halmazban hagyott elem, vagy ha nincs ilyen, 0.
if (l<m(1+δ)) l-et kidobjuk.
}</pre>

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.

<li> *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(∑|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%
</ol>

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

[[Category:Infoszak]]

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

Szikszayl, 2014. március 13., 12:49-n

Szikszayl, 2013. október 16., 12:43-n

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

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel17}} ==!! Polinomiális approximációs séma a =RÉSZÖSSZEG= problémára.== __TOC__ ===[http://info.sch.bme.hu/document.php?cm…”

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel17}} ==!! Polinomiális approximációs séma a =RÉSZÖSSZEG= problémára.== TOC ===[http://info.sch.bme.hu/document.php?cm…”