Rendszeroptimalizálás, 9. tétel

Ez az oldal a korábbi SCH wikiről lett áthozva.

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 $\max \limits _{X\in F}\sum \limits _{x\in X}k(x)$ é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_mohó={a₁, ..., a_r} halmazt találta, míg az optimális megoldás B_opt={b₁, ..., b_r}. Mivel mindkét halmaz maximális független, a 3. függetlenségi axióma miatt |B_mohó||=||B_opt. További információink a halmazok elemeiről:
• ∑k(a_i) < ∑k(b_i).
• Feltehetjük, hogy k(a₁) ≥ k(a₂) ≥ ... ≥ k(a_r)
• és hogy k(b₁) ≥ k(b₂) ≥ ... ≥ k(b_r).
• Tudjuk, hogy a mohó algoritmus a legnagyobb elemmel kezd, azaz k(a₁) ≥ k(b₁).

Legyen i+1 a legkisebb index, amire k(a_i+1)<k(b_i+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 = {b₁, ..., b_i, b_i+1}
• Y = {a₁, ..., a_i}
• ∃b_j∈X-Y: Y∪b_j∈F. Mivel b_j∈X, j≤i+1 ⇒ k(b_j)≥k(b_i+1)>k(a_i+1), azaz a mohó algoritmus b_j-t választotta volna, nem a_i+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)

Értelmezés sikertelen (ismeretlen „\begin{array}” függvény): {\displaystyle 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. }

• 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:2^E→N 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:2^E→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

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⊆2^E 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⊆B₀ valamely B₀∈B-re}

Matroid duálisa

• Tétel*: M(E,F) matroid bázisai B₁, B₂, ...
  Az E-B₁, E-B₂, ... 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.