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
véges halmazra az
rendezett pár matroid, ha
(az úgynevezett
független halmazok halmaza) az
részhalmazainak olyan halmaza, amelyre teljesül a következő három tulajdonság:
- nem üres
- öröklődés: Ha és , akkor . 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 és , továbbá
, akkor . 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
- = egy mátrix oszlopai, = lineárisan független oszlopokból álló halmazok
- = egy gráf élei, = é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
