Rendszeroptimalizálás, 9. tétel

A VIK Wikiből
A lap korábbi változatát látod, amilyen (vitalap) 2012. október 22., 10:44-kor történt szerkesztése után volt. (Ú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…”)
(eltér) ← Régebbi változat | Aktuális változat (eltér) | Újabb változat→ (eltér)
Ugrás a navigációhoz Ugrás a kereséshez

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


<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.

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 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:


Ezen a helyen volt linkelve a greedyproof.png nevű kép a régi wiki ezen oldaláról. (Kérlek hozd át ezt a képet ide, különben idővel el fog tűnni a régi wikivel együtt)


[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:2EN egy matroid rangfüggvénye
  1. r(∅)=0
  2. 0≤r(X)≤|X ∀X⊆E-re
  3. Ha |X||⊆||Y, r(X)≤r(Y)
  4. r(X) szubmoduláris, azaz ∀A,B⊆E-re r(A)+r(B)≥r(A∪B)+r(A∩B)
  • Tétel*: ha r:2EN-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
  1. B≠∅
  2. Ha X,Y∈B, |X||=||Y

|}

  1. Ha X,Y∈B és x∈X-Y, akkor ∃y∈Y, hogy X∪{y}-{x}∈B
  • Tétel*: Ha B⊆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⊆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)

-- Peti - 2007.01.02.