Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel9}} ==!! Mohó algoritmus matroidon. Matroid megadása rangfüggvényével, bázisaival (bi…”

2012-10-22T09:44:44Z

Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel9}} <style> ol { margin-top:0px; } </style> ==!! Mohó algoritmus matroidon. Matroid megadása rangfüggvényével, bázisaival (bi…”

Új lap

{{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→R+ 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 Bmohó={a1, ..., ar} halmazt találta, míg az optimális megoldás Bopt={b1, ..., br}. Mivel mindkét halmaz maximális független, a 3. függetlenségi axióma miatt |Bmohó||=||Bopt. További információink a halmazok elemeiről:
* ∑k(ai) < ∑k(bi).
* Feltehetjük, hogy k(a1) ≥ k(a2) ≥ ... ≥ k(ar)
* és hogy k(b1) ≥ k(b2) ≥ ... ≥ k(br).
* Tudjuk, hogy a mohó algoritmus a legnagyobb elemmel kezd, azaz k(a1) ≥ k(b1).
Legyen i+1 a legkisebb index, amire k(ai+1)<k(bi+1). 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 = {b1, ..., bi, bi+1}
* Y = {a1, ..., ai}
* ∃bj∈X-Y: Y∪bj∈F. Mivel bj∈X, j≤i+1 <big>⇒</big> k(bj)≥k(bi+1)>k(ai+1), azaz a mohó algoritmus bj-t választotta volna, nem ai+1-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→R+ költségfüggvényre megtalálja ∑x∈X k(x) maximumát X∈F halmazon, akkor igaz a 3. axióma is.

*Biz.*: tegyük fel, hogy nem igaz a 3. axióma, ∃X,Y∈F, |X||>||Y hogy ∀x∈X-Y-ra Y∪{x}∉F. Konstruáljunk egy költségfüggvényt:

{{InLineImageLink|Infoszak|RopiTetel9|greedyproof.png}}
 
<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>
 

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

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

*Tétel*: r:2E→N egy matroid rangfüggvénye <big>⇒</big>
# r(∅)=0
# 0≤r(X)≤|X ∀X&sube;E-re
# Ha |X||&sube;||Y, r(X)≤r(Y)
# r(X) szubmoduláris, azaz ∀A,B&sube;E-re r(A)+r(B)≥r(A∪B)+r(A∩B)

*Tétel*: ha r:2E→N-re teljesül a 3 rangaxióma, akkor ∃! 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≠∅
# Ha X,Y∈B, |X||=||Y
|}
# Ha X,Y∈B és x∈X-Y, akkor ∃y∈Y, hogy X∪{y}-{x}∈B

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

===Matroid duálisa===

*Tétel*: M(E,F) matroid bázisai B1, B2, ... Az E-B1, E-B2, ... 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). 
*Biz.*: r*(X) = max(|Y∩X||:Y∈F*) = max(||Y∩X||:Y∈B*) = max(||(E-Z)∩X||:Z∈B) = max(||X-Z∩X||:Z∈B) = ||X||-min(||Z∩X||:Z∈B) = ||X||-(r(E)-max(||W∩(E-X)||:W∈B)) = ||X-r(E)+r(E-X)

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

[[Category:Infoszak]]

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

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel9}} ol { margin-top:0px; } ==!! Mohó algoritmus matroidon. Matroid megadása rangfüggvényével, bázisaival (bi…”

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel9}} ==!! Mohó algoritmus matroidon. Matroid megadása rangfüggvényével, bázisaival (bi…”