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

{{GlobalTemplate|Infoszak|RopiTetel9}}

<style> ol { margin-top:0px; } </style>

==!! Mohó algoritmus matroidon. Matroid megadása rangfüggvényével, bázisaival (biz. nélkül). Matroid duálisa, a duális matroid rangfüggvénye.==

__TOC__

===Mohó algoritmus===

*Tétel*: Legyen (E,F) egy matroid és k:E&rarr;<b>R</b><sup>+</sup> költségfüggvény. Keressük <math> \max\limits_{X \in F} \sum\limits_{x \in X} k(x) </math> értékét. A mohó algoritmus tetszőleges matroidra és költségfüggvényre maximális összeget ad.

*Biz.*: tegyük fel, hogy a mohó algoritmus a B<sub>mohó</sub>={a<sub>1</sub>, ..., a<sub>r</sub>} halmazt találta, míg az optimális megoldás B<sub>opt</sub>={b<sub>1</sub>, ..., b<sub>r</sub>}. Mivel mindkét halmaz maximális független, a 3. függetlenségi axióma miatt |B<sub>mohó</sub>||=||B<sub>opt</sub>. További információink a halmazok elemeiről:
* &sum;k(a<sub>i</sub>) &lt; &sum;k(b<sub>i</sub>).
* Feltehetjük, hogy k(a<sub>1</sub>) &ge; k(a<sub>2</sub>) &ge; ... &ge; k(a<sub>r</sub>)
* és hogy k(b<sub>1</sub>) &ge; k(b<sub>2</sub>) &ge; ... &ge; k(b<sub>r</sub>).
* Tudjuk, hogy a mohó algoritmus a legnagyobb elemmel kezd, azaz k(a<sub>1</sub>) &ge; k(b<sub>1</sub>).
Legyen i+1 a legkisebb index, amire k(a<sub>i+1</sub>)&lt;k(b<sub>i+1</sub>). Ilyen index mindenképp létezik, különben a mohó algoritmus optimális eredményt adott volna. Alkalmazzuk a 3. függetlenségi axiómát:
* X = {b<sub>1</sub>, ..., b<sub>i</sub>, b<sub>i+1</sub>}
* Y = {a<sub>1</sub>, ..., a<sub>i</sub>}
* &exist;b<sub>j</sub>&isin;X-Y: Y&cup;b<sub>j</sub>&isin;F. Mivel b<sub>j</sub>&isin;X, j&le;i+1 <big>&rArr;</big> k(b<sub>j</sub>)&ge;k(b<sub>i+1</sub>)&gt;k(a<sub>i+1</sub>), azaz a mohó algoritmus b<sub>j</sub>-t választotta volna, nem a<sub>i+1</sub>-et.

*Tétel*: Ha egy (E,F) struktúrára teljesül az első két függetlenségi axióma és a mohó algoritmus tetszőleges k:E&rarr;<b>R</b><sup>+</sup> költségfüggvényre megtalálja &sum;<sub>x&isin;X</sub> k(x) maximumát X&isin;F halmazon, akkor igaz a 3. axióma is.

*Biz.*: tegyük fel, hogy nem igaz a 3. axióma, &exist;X,Y&isin;F, |X||&gt;||Y hogy &forall;x&isin;X-Y-ra Y&cup;{x}&notin;F. Konstruáljunk egy költségfüggvényt:

{{InLineImageLink|Infoszak|RopiTetel9|greedyproof.png}}
<br>
<math> k(x) = \left\{ \begin{array}{l} \mbox{1, ha $x \in Y$} \\ \mbox{-\epsilon$, ha $x \in X-Y$} \\ \mbox{0 k\"ul\"onben} \end{array} \right. </math>
<br clear="all">

* A mohó algoritmus megtalálja Y-t, a célfüggvény értéke (k+m)&middot;1.
* Ennél lehet nagyobb összeget is elérni, ha X-et választjuk. Ekkor a célfüggvény értéke k&middot;1+l&middot;(1-&epsilon;).
* A k&middot;1+l&middot;(1-&epsilon;) &gt; (k+m)&middot;1 egyenlőtlenségnek van megoldása: 0&lt;&epsilon;&lt;1-m/l, (m&lt;l), tehát a mohó algoritmus nem adott optimális eredményt.

===Matroid megadása rangfüggvénnyel===

*Tétel*: r:2<sup>E</sup>&rarr;<b>N</b> egy matroid rangfüggvénye <big>&rArr;</big>
# r(&empty;)=0
# 0&le;r(X)&le;|X &forall;X&sube;E-re
# Ha |X||&sube;||Y, r(X)&le;r(Y)
# r(X) szubmoduláris, azaz &forall;A,B&sube;E-re r(A)+r(B)&ge;r(A&cup;B)+r(A&cap;B)

*Tétel*: ha r:2<sup>E</sup>&rarr;<b>N</b>-re teljesül a 3 rangaxióma, akkor &exist;! olyan matroid, aminek ez a rangfüggvénye, mégpedig F={X:r(X)=|X}.

===Matroid megadása bázissal===

*Tétel*: ha B egy matroid bázisainak halmazát jelöli, akkor
# B&ne;&empty;
# Ha X,Y&isin;B, |X||=||Y
|}
# Ha X,Y&isin;B és x&isin;X-Y, akkor &exist;y&isin;Y, hogy X&cup;{y}-{x}&isin;B

*Tétel*: Ha B&sube;2<sup>E</sup> egy olyan halmazrendszer, amire teljesül a három bázisaxióma, akkor &exist;! olyan matroid, aminek bázisai B elemei, mégpedig F={X:X&sube;B<sub>0</sub> valamely B<sub>0</sub>&isin;B-re}

===Matroid duálisa===

*Tétel*: M(E,F) matroid bázisai B<sub>1</sub>, B<sub>2</sub>, ... <br> Az E-B<sub>1</sub>, E-B<sub>2</sub>, ... bázisok is matroidot határoznak meg. Ezt az M* matroidot nevezzük M duális matroidjának.

===Duális matroid rangfüggvénye===

*Tétel*: M(E,F) és M*(E,F*) duális matroidok. Ekkor r*(X) = |X-r(E)+r(E-X). <br>
*Biz.*: r*(X) = max(|Y&cap;X||:Y&isin;F*) = max(||Y&cap;X||:Y&isin;B*) = max(||(E-Z)&cap;X||:Z&isin;B) = max(||X-Z&cap;X||:Z&isin;B) = ||X||-min(||Z&cap;X||:Z&isin;B) = ||X||-(r(E)-max(||W&cap;(E-X)||:W&isin;B)) = ||X-r(E)+r(E-X)

-- [[PallosPeter|Peti]] - 2007.01.02.


[[Category:Infoszak]]