Szakkörök‎ > ‎Algoritmus szakkör‎ > ‎2011-2012‎ > ‎

10. óra

2011.11.28.

Feladat


Megjegyzések:
  • ez a feladat már szerepelt 3 éve a szakkörön, az akkori megoldások is itt fognak megjelenni;
  • az idei Nemes Tihamér verseny 9-10.-es korcsoportjának írásbeli fordulójában ez volt a 4. feladat, 10-nél kevesebb munkával.

Elmélet

Egy kis áttekintés a mohó algoritmusokról ( forrás: Cormen-Rivest-Leiserson-Stein: Új algoritmusok ).

Problémák egy általános csoportjáról egységesen bizonyítható, hogy mohó algoritmussal optimális megoldás adható rájuk. Ezt az általános probléma osztályt az úgynevezett matroid struktúrával szokás modellezni. (Az elnevezés a mátrixok elméletéből származik.)

A matroid fogalma

Adott S véges halmazra az M=(S,I) rendezett pár matroid, ha I (az úgynevezett független halmazok halmaza) az S részhalmazainak olyan halmaza, amelyre teljesül a következő három tulajdonság:
  1. I nem üres
  2. öröklődés: Ha A ∈ I és B ⊂ A, akkor B ∈ I. Szavakkal: ha adott elemek egy független halmaza, akkor ezekből elhagyva néhány elemet, továbbra is független halmazt kapunk.
  3. bővíthetőség: Ha A ∈ I és B ∈ I, továbbá ∣A∣<∣B∣, akkor ∃x ∈ B \ A: A ∪ {x} ∈ I. Szavakkal: ha két független halmaz számossága eltérő, akkor a nagyobból (a több elemet tartalmazóból) ki tudunk választani egy, a kisebb halmazban nem szereplő elemet úgy, hogy azt a kisebbe téve az így „bővített kisebb” halmaz is független.
Az axiómák következménye, hogy a matroid nem bővíthető független halmazainak elemszáma azonos. (Ellenkező esetben a kisebb bővíthető lenne 3. miatt úgy, hogy továbbra is független marad.)

Példák matroidra

S = egy mátrix oszlopai, I = lineárisan független oszlopokból álló halmazok
S = egy gráf élei, I = élek körmentes halmazai

Mohó algoritmus súlyozott matroidra

Ha az alaphalmaz elemeihez pozitív súlyokat rendelünk, akkor tipikus optimalizálási feladat a következő: határozzuk meg a maximális összsúlyú független halmazt. Bizonyítható, hogy matroid esetén a következő (mohó) algoritmus helyes megoldást ad:

H := üres halmaz
Az elemek rendezése súly szerint csökkenően
Ciklus minden x elemre a csökkenő sorrend szerint
    Ha H unió x független akkor
        H := H unió x
    Elágazás vége
Ciklus vége
eredmény := H

Az algoritmus helyessége

Indirekt tegyük fel, hogy algoritmusunk nem a maximális függetlent H halmazt adta meg, és legyen  H* egy optimális független halmaz.  A bővíthetőségi tulajdonság miatt H és H* elemszáma azonos kell, hogy legyen. Rendezzük az elemeket súly szerint csökkenően a két halmazban:

H ={h1, h2, ..., hn}
H*={u1, u2, ..., un}

Az indirekt feltevés miatt kell lennie egy első i indexnek, amire ui > hi, különben H* nem lehetne "jobb" H-nál. De ezzel ellentmondásra jutunk, hiszen megint csak a bővíthetőség miatt {h1,..,hi-1} ∪ uis független, de akkor a mohó algoritmus nem hi-t választotta volna az i. lépésben.