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:
- $I$ nem üres
- ö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.
- 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
- $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
Feladat
