NézetNyomtat

17. óra
Címkék > Óra

17. óra

Elmélet

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 $\mathcal{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\in I$ és $B\subset A$, akkor $B\in 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\in I$ és $B\in I$, továbbá $|A|\lt |B|$, akkor $\exists x \in B \ A: A\cup\{x\}\in 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

  1. $S$ = egy mátrix oszlopai, $I$ = lineárisan független oszlopokból álló halmazok
  2. $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:
:= ü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

Feladat